RSA 是一种非对称加密算法，用“公钥”加密，用“私钥”解密，保证数据传输安全。
比喻理解：锁和钥匙
想象一下：
-
公钥是“上锁的锁”，别人可以用它锁住箱子（加密），但打不开。
-
私钥是“钥匙”，只有你自己有，可以打开锁（解密）。
所以：
-
我给你一个“锁”（公钥），你用它锁住一个箱子（加密数据）送回来。
-
只有我有钥匙（私钥），我能打开箱子（解密数据）。
注意事项
-
明文必须小于 n，也就是 m<n 否则需分块加密
-
实际使用中，RSA 通常只加密 对称密钥（比如 AES），而不是大量数据
-
使用填充算法（如 OAEP）防止加密攻击
第一步：选两个质数
我们先选两个质数（不能被整除的整数）：
p = 3
q = 11
第二步：计算 n 和 φ(n)
n = p × q = 3 × 11 = 33
φ(n) = (p - 1) × (q - 1) = 2 × 10 = 20
其中 φ(n) 是一种叫“欧拉函数”的东西，是 RSA 算法的核心之一。
第三步：选一个公钥 e
我们要选一个跟 φ(n) = 20 互质的整数 e，通常选一个小的质数。
e = 7 （因为 7 跟 20 没有公因数，合法）
第四步：求私钥 d（让它能反过来解密）
找一个整数 d，让它满足：
(e × d) % φ(n) = 1
(7 × d) % 20 = 1
试试：
7 × 3 = 21，21 % 20 = 1
所以：
d = 3
总结密钥对：
公钥 (e, n) = (7, 33)
私钥 (d, n) = (3, 33)
加密过程
假设明文 m = 4，我们用公钥 (7, 33) 加密：
c = m^e % n = 4^7 % 33= 16384 % 33= 16
得到密文：c = 16
解密过程
我们收到密文 16，用私钥 (3, 33) 解密：
m = c^d % n = 16^3 % 33 = 4096 % 33 = 4
恢复出原文：m = 4
欧拉定理
欧拉定理（非常关键）
如果：
-
n是两个大质数p * q -
m与n互质（也就是说 m 不能被 n 的质因子整除）
那么一定成立：m^φ(n) mod n = 1 （其中 φ(n) 是欧拉函数）
φ(n)：如果 n 是两个质数 p 和 q 的乘积：n = p * q，那么欧拉函数就是：φ(n)=(p−1)(q−1) ，这表示从 1 到 n−1 里面，有多少个数跟 n 互质。
假设：
-
p=7 ，q=11
-
那么 n=p ⋅ q=7
*11 = 77 -
则：
φ(77) = (7 − 1)(11 − 1) = 6*10 = 60
所以如果 m 与 77 互质，那：m ^ 60 mod 77 = 1
深入理解
我们选 d 的时候，是专门选出来能“抵消” e 的效果的。
所以：
-
加密是：
先做 e 次方 -
解密是：
再做 d 次方 -
e 和 d 是互相“取消”的
就像是这样理解（m是需要用rsa加密的数据）
m^e 再 ^d 就等于 m^(e*d) 而我们生成 d 的时候，保证 e*d 刚好变成 “1 + φ(n) 的倍数”这个时候 m^(e*d) 就刚好又变回 m 本人。
解释：
如果：e * d = 1 mod φ(n) ⇒ e * d = 1 + k * φ(n)
所以：m ^ (e * d) = m ^ (1+k * φ(n)) = m * m ^ (k * φ(n))
然后根据欧拉定理：m ^ φ(n) mod n = 1 ⇒ m ^ (k * φ(n)) mod n = 1
所以：m^(e * d) mod n = m mod n = m 数据被解密（rsa要求被加密的数据满足 m < n）
总结
| 步骤 | 操作 |
|---|---|
| 选质数 | p = 3, q = 11 |
| 计算 n | n = 33 |
| 计算 φ(n) | φ(n) = 20 |
| 选公钥 e | e = 7 |
| 求私钥 d | d = 3 |
| 加密 | m = 4 → c = 16（用公钥） |
| 解密 | c = 16 → m = 4（用私钥） |
)
