第一个能同时做加密和签名的公钥算法。我们用小素数把它从生成到签名完整跑一遍,再看它满地的坑。
1977 年,Rivest、Shamir、Adleman 三人把第 14 章的欧拉定理和大数分解难题拼成了一个惊人的系统:一把公钥人人可用来加密,一把私钥只有你能解密;反过来,私钥能签名,公钥能验证。一个算法,两种能力。这一章,我们用你能手算的小数字,把它彻底拆开。
RSA 的全部秘密,始于两个素数。步骤如下(右边是能手算的迷你例子):
| 步骤 | 做什么 | 迷你例子 |
|---|---|---|
| 1. 选两个素数 | 私密选 p、q | p=61, q=53 |
| 2. 算模数 n | n = p·q(公开) | n = 3233 |
| 3. 算 φ(n) | φ = (p−1)(q−1)(私密) | φ = 60·52 = 3120 |
| 4. 选公钥指数 e | 与 φ 互质,常用 65537 | e = 17 |
| 5. 算私钥指数 d | d = e⁻¹ mod φ | d = 2753 |
公钥 = (n, e),公开给全世界;私钥 = d,你死死藏好。而 p, q, φ 用完就该销毁——因为谁知道 p、q,谁就能重算出 φ 进而算出 d。这就是 RSA 的命门:攻击者拿到公开的 n,只要能把它分解回 p·q,私钥就完了。而分解一个 2048 位的 n,是第 14 章说的那个"没人会做"的大数分解难题。
把消息编码成一个数字 m(要求 m < n)。加密是"m 的 e 次方",解密是"c 的 d 次方",全都 mod n:
为什么绕一圈能回到原点?因为 e·d ≡ 1 (mod φ),所以 c^d = m^{ed} = m^{kφ+1},由欧拉定理 m^φ ≡ 1,整个式子塌回 m。这正是第 14 章埋的伏笔在此兑现。e、d 是一对能互相抵消的指数,而只有知道 φ 的人才能配出 d。
RSA 最漂亮的地方:加密的两把钥匙可以反着用。用私钥做"解密操作"得到的东西,任何人都能用公钥做"加密操作"验证——这就是数字签名:
因为只有你有 d,能产出对得上的 s 的就只有你——这同时给了认证(确实是你)和不可否认(你抵赖不了),正好是第 1 章四大目标里的后两个。(实务中签的不是消息本身,而是它的哈希,原因见第 18 章。)
下面的计算器用真正的 BigInt 跑完整 RSA。改动 p、q、e 和消息 m,看密钥怎么生成、加密解密如何往返、签名验签如何成立。旁边还有一个"分解攻击"按钮:因为这里 n 很小,它能瞬间把 n 分解回 p、q 并重算出你的私钥——直观展示"n 一旦被分解,私钥即失守"。
刚才那套朴素的 c = m^e mod n 叫教科书 RSA(textbook RSA),它能讲清原理,但直接拿去用会漏成筛子。几个致命问题:
E(m₁)·E(m₂) = E(m₁·m₂)。攻击者不解密就能"运算"密文,篡改结果。m³ < n,那 mod n 根本没起作用,直接开三次方就还原了明文。真实 RSA 从不裸用,必须套填充方案,把消息随机化、结构化之后再求幂:
· 加密用 RSA-OAEP:加入随机性,让相同明文每次密文都不同,并破坏可延展性。
· 签名用 RSA-PSS(或至少 PKCS#1 v1.5):同样加盐、防伪造。
老旧的 PKCS#1 v1.5 加密填充还催生过著名的 Bleichenbacher padding oracle 攻击(第 8 章那个幽灵的公钥版)——服务器只要对填充错误给出可区分的响应,攻击者就能逐步解出密文。规矩:永远用带 OAEP/PSS 的库函数,绝不自己拼 m^e mod n。
RSA 依然广泛存在(尤其是老证书、老系统),但新系统正在离开它,原因很现实:
主要在非对称场景:APK v2 签名可选 RSA、老服务器证书、JWT 的 RS256、以及 Android Keystore 里生成的 RSA 密钥对(常用于"用生物识别解锁一把私钥")。用法上永远选带填充的变体:加密用 RSA/ECB/OAEPWithSHA-256AndMGF1Padding(名字里的 ECB 在这里是历史遗留噪音,别慌),签名用 SHA256withRSA/PSS。但如果你在设计新系统,优先考虑椭圆曲线(EC / Ed25519)——更小、更快、坑更少。这正是下一章的主角。
c=mᵉ mod n、解密 m=c^d mod n;反过来用私钥即数字签名。安全靠大数分解难题。