📑 本页目录（点开跳转）
14 · RSA
⏱ 30 分钟 ｜ ⭐ 第一个公钥密码，也是坑最多的一个
🎯 一句话
RSA 用一个漂亮的不对称：把两个大素数乘起来很容易，把乘积拆回去极难。 而教科书上写的那个 RSA，直接用是完全不安全的 —— 这一章会讲清楚差在哪。
🔑 一、算法
【密钥生成】
① 选两个大素数 p、q（各 1536 bit）
② n = p·q ← 公开
③ φ(n) = (p−1)(q−1) ← 保密！
④ 选 e，满足 gcd(e, φ(n)) = 1 ← 通常 e = 65537
⑤ d = e⁻¹ mod φ(n) ← 私钥（扩展欧几里得，第 13 章）
公钥 = (n, e) 私钥 = d（外加 p、q 用于 CRT 加速）
【加解密】
C = M^e mod n
M = C^d mod n
📐 为什么解密能还原（想看再点）
由 $d = e^{-1} \bmod \varphi(n)$，存在整数 k 使 $ed = 1 + k\varphi(n)$。
情况 1：$\gcd(M, n) = 1$。由欧拉定理 $M^{\varphi(n)} \equiv 1 \pmod n$：
$$C^d = M^{ed} = M^{1+k\varphi(n)} = M\cdot(M^{\varphi(n)})^k \equiv M\cdot 1^k = M \pmod n$$
情况 2：$\gcd(M,n) \ne 1$（M 被 p 或 q 整除）—— 用中国剩余定理分别在 mod p 和 mod q 下验证，结论同样成立。∎
💡 核心就一句：e 和 d 在指数上互为逆元，一乘一除正好回到原点。
💡 为什么 e = 65537
e = 65537 = 2¹⁶ + 1 = 二进制 10000000000000001
⭐ 只有两个 1 → 平方-乘算法只需 17 次操作 → 加密极快
⭐ 又足够大 → 避免小指数攻击（见下）
⚠️ 历史上用过 e = 3，导致了真实的攻击
💀 二、教科书 RSA 为什么不能直接用
问题 ① 它是确定性的
相同明文 → 相同密文
⭐ 直接违反 IND-CPA（第 8 章的第一个推论）
💥 实际攻击：如果明文空间小（比如"是"/"否"、一个 4 位数验证码），
攻击者把所有可能的明文都加密一遍，查表即可 💀
问题 ② 乘法同态性可被滥用
⭐ RSA 有一个"意外"的性质：
Enc(M₁) · Enc(M₂) = M₁^e · M₂^e = (M₁·M₂)^e = Enc(M₁ · M₂) mod n
💥 攻击：攻击者想让你解密 C，但你拒绝
他改为让你解密 C' = C · 2^e mod n（看起来是无关的密文）
你返回 M' = 2M
他除以 2 就得到 M ⭐
💥 这个攻击有个名字叫"盲化攻击"，它也说明了 为什么绝对不能用同一个密钥对既加密又签名。
问题 ③ 小指数攻击
若 e = 3 且消息很短（M³ < n）：
→ C = M³ 根本没有发生模运算
→ 攻击者直接开【三次方根】就还原了 💀
⭐ Håstad 广播攻击：同一条消息用 e=3 发给 3 个不同的人
→ 用中国剩余定理合并 3 个密文 → 直接解出 M
问题 ④ 共模 / 共因子
💥 共模攻击：两个人用相同的 n、不同的 e
→ 任一方都能算出对方的私钥
💥 共因子：如果两个 RSA 公钥的 n 恰好共享一个素数因子
→ gcd(n₁, n₂) 直接给出那个素数 → 两个密钥全废
⭐ 这不是理论：2012 年有研究扫描全网 TLS 证书，
发现【数万个】RSA 公钥可以被这样直接分解 ——
根因是嵌入式设备开机时熵不足（第 4 章）
✅ 三、正确用法：必须填充
加密用 OAEP
OAEP = Optimal Asymmetric Encryption Padding
把消息 + 【随机数】+ 结构化填充，经过两轮哈希混合，再做 RSA
✅ 引入随机性 → 满足 IND-CPA
✅ 结构化 → 破坏乘法同态
✅ 在随机预言机模型下可证 IND-CCA
💥 它取代的 PKCS#1 v1.5 有著名的 Bleichenbacher 攻击（1998）： 服务器对"填充格式错误"返回不同响应 → 又是一个预言机 → 约百万次查询就能解密任意密文。 2017 年的 ROBOT 攻击发现，20 年后仍有大量主流网站没修好。
签名用 PSS
❌ 直接 σ = M^d mod n（教科书签名）
→ 攻击者可以：σ₁·σ₂ 是 M₁·M₂ 的合法签名 💀（同态性）
→ 也可以先选 σ，反算 M = σ^e，得到一个"合法"的签名 💀
✅ 先哈希再填充：σ = PSS(H(M))^d mod n
🔗 第 17 章会详细讲签名，包括 FDH 和 PSS 的区别。
# ✅ 正确用法
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
ct = key.public_key().encrypt(
b"secret",
padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), # ⭐ 必须 OAEP
algorithm=hashes.SHA256(), label=None))
sig = key.sign(b"message",
padding.PSS(mgf=padding.MGF1(hashes.SHA256()), # ⭐ 必须 PSS
salt_length=padding.PSS.MAX_LENGTH),
hashes.SHA256())
⏱️ 四、侧信道：私钥能被"听"出来
| 攻击 | 原理 |
|---|---|
| 计时攻击 | 模幂的时间取决于 d 的比特 → 测时间恢复 d ⭐ |
| 功耗分析 | 平方和乘法的功耗曲线不同，肉眼可辨 |
| Bellcore 故障攻击 | CRT 解密中制造一次错误 → 一次错误签名就能分解 n ⭐ |
| 缓存攻击 | 窗口法的查表访问模式泄露指数位 |
✅ 防御：
├─ 恒定时间实现（不要写自己的 powmod）
├─ 【盲化】：算 (C·r^e)^d 再除以 r，让每次运算的输入随机化 ⭐
└─ CRT 后验证签名（防 Bellcore）
🔑 这是第 1 章那条建议的具体理由： 不要自己实现密码算法 —— 数学写对了，实现照样能漏。
📉 五、RSA 今天的地位
✅ 仍然广泛存在：TLS 证书、代码签名、SSH、JWT
⚠️ 但新系统正在离开它：
├─ 密钥太大（3072 bit vs 椭圆曲线的 256 bit）⭐
├─ 签名/密钥生成慢
├─ 坑太多（填充、参数、侧信道）
└─ 量子威胁：Shor 算法直接摧毁（第 23 章）
✅ 新项目的推荐：
├─ 签名 → Ed25519（第 16 章）
├─ 密钥交换 → X25519
└─ 需要抗量子 → ML-KEM / ML-DSA（第 23 章）
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 13 章 φ(pq)=(p−1)(q−1) | RSA 的全部秘密 ⭐ |
| 第 13 章 欧拉定理 | 正确性证明 |
| 第 13 章 模逆元 | d 的计算 |
| 第 8 章 确定性⟹不安全 | 教科书 RSA 的第一宗罪 ⭐ |
| 第 4 章 熵不足 | 共因子攻击的根因 |
| 第 7 章 padding oracle | Bleichenbacher 是它的公钥版 |
| AI 基础设施 · GPU 到底是什么 | 计时侧信道的来源就是那边讲 CPU 时列的那几样：分支预测、乱序执行、缓存——正因为执行时间随数据变化，私钥才能被"听"出来 ⭐ |
| Claude 资料库 · 触达生产系统 | 你给生产 Agent 配的 OAuth / token 签名，底下跑的就是本章的 RSA（或 ECDSA）；⚠️ 那一节的结论也一样：认证用标准件，别自己拼填充 |
✅ 检查点
- RSA 的密钥生成五步是什么？哪些必须保密？
- 为什么解密能还原明文？核心是哪一句？
- 为什么 e 通常取 65537？
- 教科书 RSA 的四个问题分别是什么？
- 乘法同态性怎么被用来攻击？这说明了什么设计原则？
- Håstad 广播攻击是怎么回事？
- 共因子攻击的根因是什么？它和第 4 章什么内容有关？
- OAEP 提供了哪三样东西？它取代的 PKCS#1 v1.5 有什么问题？
- Bellcore 故障攻击有多严重？怎么防？
- 新项目该用什么代替 RSA？
👀 答案
- ①选大素数 p、q ②n=pq ③φ(n)=(p−1)(q−1) ④选 e 与 φ(n) 互质 ⑤d=e⁻¹ mod φ(n)。p、q、φ(n)、d 都必须保密（知道 φ 就能算出 d）。
- 因为 ed = 1 + kφ(n)，由欧拉定理 M^φ(n) ≡ 1，所以 C^d = M^(1+kφ(n)) = M·(M^φ(n))^k ≡ M。核心：e 和 d 在指数上互为逆元，一乘一除回到原点。
- 65537 = 2¹⁶+1，二进制只有两个 1 → 平方-乘只需 17 次操作，加密极快；同时足够大，避免小指数攻击。
- ①确定性（违反 IND-CPA，明文空间小时可枚举）②乘法同态性可被滥用 ③小指数攻击 ④共模/共因子。
- Enc(M₁)·Enc(M₂) = Enc(M₁·M₂)。攻击者让你解密 C·2^e，拿到 2M 后除以 2 得到 M（盲化攻击）。说明：绝对不能用同一个密钥既加密又签名。
- 同一条消息用 e=3 发给 3 个不同的人，攻击者收集 3 个密文，用中国剩余定理合并后直接开三次方根解出 M。
- 嵌入式设备开机时熵不足，导致不同设备生成的 RSA 素数重复。gcd(n₁,n₂) 直接给出共享素数 → 两个密钥全废。和第 4 章的随机数失效是同一根因。2012 年扫描全网发现数万个这样的公钥。
- ①随机性（满足 IND-CPA）②结构化填充（破坏乘法同态）③ROM 下可证 IND-CCA。PKCS#1 v1.5 有 Bleichenbacher 攻击：填充错误的不同响应构成预言机，约百万次查询解密任意密文；2017 年 ROBOT 攻击发现 20 年后仍有大量主流网站没修好。
- 在 CRT 解密中制造一次错误，仅凭一次错误签名就能分解 n。防御：CRT 后验证签名结果再输出。
- 签名用 Ed25519，密钥交换用 X25519，需要抗量子用 ML-KEM / ML-DSA。
🛑 可以停在这里
⚡ 走神救援
RSA：n=pq，φ(n)=(p−1)(q−1)，选 e 互质于 φ，d=e⁻¹ mod φ(n)；C=M^e，M=C^d。正确性靠欧拉定理（ed=1+kφ(n) ⟹ e 和 d 在指数上互为逆元）。e=65537=2¹⁶+1：二进制只两个 1 → 17 次操作，又够大避免小指数攻击。⭐教科书 RSA 四宗罪：①确定性 ⟹ 违反 IND-CPA（明文空间小就直接枚举查表）②⭐乘法同态 Enc(M₁)·Enc(M₂)=Enc(M₁M₂) → 盲化攻击：让你解密 C·2^e 拿到 2M 再除以 2；说明绝不能同一密钥既加密又签名 ③小指数攻击（e=3 且 M³<n 直接开三次方根；Håstad 广播攻击：同消息发给 3 人，CRT 合并即解）④共模/共因子（💥2012 年扫全网发现数万个 RSA 公钥可被 gcd 直接分解，根因是嵌入式设备开机熵不足）。✅必须填充：加密用 OAEP（随机性→IND-CPA、结构化→破坏同态、ROM下可证IND-CCA），它取代的 PKCS#1 v1.5 有💥Bleichenbacher 攻击（填充错误的不同响应=预言机，百万次查询解密任意密文；2017 ROBOT 发现 20 年后大量网站仍没修好）；签名用 PSS（教科书签名可被 σ₁·σ₂ 伪造，也能先选 σ 反算 M）。侧信道：计时/功耗/缓存，⭐Bellcore 故障攻击——CRT 解密中一次错误就能分解 n，防御靠恒定时间实现 + 盲化 + CRT 后验签。现状：仍广泛存在但新系统在离开（密钥 3072 vs ECC 256、慢、坑多、Shor 直接摧毁）→ 新项目用 Ed25519 / X25519 / ML-KEM。
下一节 👉 15-DH与ElGamal.md ⭐