2. RSA算法回顾
说实话，RSA 的数学基础并不复杂，但当年我刚接触时，也被那几个概念绕晕过。今天咱们把这块彻底说透。你想想看，一个算法能运行三十多年还稳稳当当，背后一定有它的硬道理。下面我带你从数学地基开始，一步步搭起 RSA 的整栋楼。
2.1 数学基础
RSA 的核心靠的是整数分解难题——两个大素数相乘容易，但把乘积质因数分解回去极难。要吃透这个，必须搞明白三个基础概念：大素数、欧拉函数、模逆元。
大素数
所谓大素数，就是位数至少 1024 比特（约 308 位十进制）的素数。我见过不少新手直接拿 random.getrandbits(1024) 去试，结果一跑就是几分钟——因为随机数大概率是合数。正确的做法是用 Miller–Rabin 素性检测，迭代次数取 20 轮以上。我自己习惯在工程里先筛掉小质因子，再用 Miller–Rabin，速度能快一倍。
欧拉函数 φ(n)
对于 RSA 最关键的形态是：n = p × q（p 和 q 都是素数）。此时 φ(n) = (p-1)(q-1)。为什么要算这个？因为它直接决定了私钥 d 的存在性。我记得有一次做密钥生成优化，把 (p-1) 和 (q-1) 分别与 e 互质的检查漏了，导致生成的私钥无法解密——排查了一天，最后才发现问题出在这儿。
模逆元
给定整数 e 和模数 φ(n)，若 gcd(e, φ(n)) = 1，则存在整数 d 使得 e × d ≡ 1 (mod φ(n))。这个 d 就是私钥。计算模逆元的算法叫扩展欧几里得算法，速度快得很，O(log n) 就搞定。代码实现也就十几行，但千万别手写一个循环去暴力试——我当时第一天学 RSA 就干过这蠢事，p 和 q 取 128 位，迭代次数直接爆表。
# 扩展欧几里得求模逆元（Python 示例）
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError('模逆不存在')
return x % mn = p × q
φ(n) = (p-1)(q-1)
e × d ≡ 1 (mod φ(n))
2.2 密钥生成流程
搞清楚数学基础，生成密钥就是按步骤填数。下面是完整的 5 步流程，我建议用表格记下来，实际写代码时对照着查不容易漏。
| 步骤 | 操作 | 说明 |
|---|---|---|
| 1 | 随机选择两个大素数 p, q | 通常 p 和 q 位数相同，且不能太接近，否则易被 Fermat 分解 |
| 2 | 计算 n = p × q | n 的比特长度就是 RSA 的密钥长度（如 2048 bit） |
| 3 | 计算 φ(n) = (p-1)(q-1) | 必须保密，因为知道 φ(n) 就能反推私钥 |
| 4 | 选择公钥指数 e | 常用 65537 (0x10001)，既能保证安全，又有至少 2 个 1 比特利于快速幂 |
| 5 | 计算 d ≡ e⁻¹ mod φ(n) | d 为私钥指数，必须满足 e×d ≡ 1 (mod φ(n)) |
为什么要对 e 有 gcd(e, φ(n)) = 1 的要求？说白了，如果 gcd 不等于 1，扩展欧几里得算法就找不到整数 d，私钥就生成不了。我曾在玩票项目里试探性地用了 e=3，结果 φ(n) 恰好被 3 整除，生成密钥直接抛异常——算是踩了个常见的坑。
2.3 签名与加密原理
RSA 的加密和签名在数学上是对称的，只是密钥使用顺序不同。
加密与解密
- 加密：c = m^e mod n（用公钥 (n, e)）
- 解密：m = c^d mod n（用私钥 (n, d)）
注意这里 m 必须小于 n，而且一般不能直接加密原始明文，要先做 OAEP 填充。我早期做产品时没加填充，直接传个 "Y" 文本，结果加密后密文长度跟明文一样——这种模式很容易被选择明文攻击。
签名与验签
- 签名：s = hash(m)^d mod n（用私钥签名消息的哈希值）
- 验签：hash(m) ≡ s^e mod n（用公钥验证）
签名过程本质上就是“反向加密”——用私钥做指数运算生成签名，公钥做指数运算验签。但是哈希这一步不能省。我曾经见过一个 demo 直接对整条消息签名，结果消息长度超过 n 时程序崩溃。
下面这张图把 RSA 从数学到应用的逻辑串了一遍，你可以用它快速回顾。