📑 本页目录（点开跳转）
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
因果链
💀 二、教科书 RSA 为什么不能直接用
问题 ① 它是确定性的
操作步骤
问题 ② 乘法同态性可被滥用
对照
⭐ 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 ⭐
💥 这个攻击有个名字叫"盲化攻击"，它也说明了 为什么绝对不能用同一个密钥对既加密又签名。
问题 ③ 小指数攻击
结果对照
问题 ④ 共模 / 共因子
结果对照
🔧 三、正确用法：必须填充
加密用 OAEP
结果对照
💥 它取代的 PKCS#1 v1.5 有著名的 Bleichenbacher 攻击（1998）： 服务器对"填充格式错误"返回不同响应 → 又是一个预言机 → 约百万次查询就能解密任意密文。 2017 年的 ROBOT 攻击发现，20 年后仍有大量主流网站没修好。
签名用 PSS
结果对照
🔗 第 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 的模幂关系解释了正确性，不等于裸公式已经是安全协议。
- 教科书形式的确定性与代数结构会带来攻击，需要配套的编码与用途区分。
- 密钥生成、填充处理和侧信道防护都应交给经过审查的实现。
下一节 👉 15-DH与ElGamal.md ⭐