RSA 公钥加密

不对称加密：钥匙不是一把

传统加密（“对称加密”）：发送和接收方用同一把钥匙。问题：怎么把钥匙安全地告诉对方？

1977 年 Rivest、Shamir、Adleman 提出 RSA，开创了公钥加密：

• 每个人有两把钥匙：公钥（公开发布给所有人）和 私钥（只有自己知道）
• 别人用你的公钥加密消息给你
• 只有你的私钥能解密
• 即使所有人都知道你的公钥，也无法推出你的私钥

这听起来像魔术。它建立在一个数学不对称性上：

乘两个大素数 = 几毫秒；分解它们的乘积 = 上亿年

五步生成密钥

① 选两个素数 p、q

实际中要 1024 位以上的素数（300 多位十进制数）。这里我们用 11 和 13 演示。

② 计算 n = p × q 和 φ(n) = (p−1)(q−1)

• $n$ = 11 × 13 = 143
• $\phi(n)$ = 10 × 12 = 120

n 是公开的。φ(n) 必须保密 —— 知道了它就等于知道了私钥。

注意 φ(n) 的公式 (p−1)(q−1) 只在 n 是两个素数乘积时成立，所以保密 p、q 也就保密了 φ(n)。

③ 选公钥指数 e

要求：1 < e < φ(n) 且 gcd(e, φ(n)) = 1（e 和 φ 互质）。

实际中几乎总是用 e = 65537（=2¹⁶ + 1）：它是素数、二进制 10000000000000001 只有两个 1 位，所以快速取幂特别快。

④ 求私钥 d

d 是 e 在模 φ 下的乘法逆元：

$$e \cdot d \equiv 1 \pmod{\phi(n)}$$

意思是 e × d 比 φ 大的部分恰好是 1。用扩展欧几里得算法几行代码就能算出来。

e = 7, φ = 120 → d = 103（因为 7 × 103 = 721 = 6 × 120 + 1）。

⑤ 公开 (n, e)，保密 (n, d)

加解密

要把明文消息 m（0 ≤ m < n 的整数）加密：

$$c = m^e \bmod n$$

要解密密文 c：

$$m = c^d \bmod n$$

为什么有效

数学魔法：欧拉定理保证

$$(m^e)^d = m^{ed} \equiv m \pmod n$$

只要 ed ≡ 1 (mod φ(n))，加密然后解密会还原 m。这是公钥加密能”互逆”的根本。

为什么安全

要从公钥 (n, e) 推出私钥 d，必须先算出 φ(n)。而算 φ(n) 等价于分解 n 找到 p 和 q：

• n = 100 位十进制：现代算法 ~几小时
• n = 200 位：~几年
• n = 300 位（约 1024 位二进制）：目前没有算法能在合理时间内分解
• n = 600 位（2048 位）：100 年也算不出来

至今没有数学家证明”分解一定难”。但 50 年攻击没找到捷径，工业界当作真理用着。

实际中的细节

这个演示极度简化。真实 RSA 还包括：

• 填充（padding）：直接加密 m^e mod n 不安全，要先把消息 m 和随机串拼接（OAEP 填充）
• 分块：消息太长就分段加密
• 签名：私钥加密、公钥验证 → 可以”证明”消息来自你
• 混合加密：RSA 太慢，实际上用它加密一个对称密钥，对称密钥再加密大数据

量子威胁

1994 年 Peter Shor 证明：有了量子计算机，分解大数只需多项式时间。RSA 在量子计算机面前直接崩溃。

目前量子计算机还不够大（2024 年公开能分解 21、35 这种小数）。但 NIST 已经在标准化后量子密码学（PQC），基于格、码、哈希等不依赖大数分解的难题。

未来 10-20 年，RSA 大概会被 PQC 替代。但它在密码学历史上的地位不会变 —— 它是第一个把”非对称加密”从理论变成现实的方案。