AI摘要
RSA 共模攻击
1. 攻击场景
假设 Bob 和 Alice 共享同一个 RSA 模数 $n$，但各自持有不同的公钥对 $(e_1, n)$ 和 $(e_2, n)$，且 $\gcd(e_1, e_2) = 1$。攻击者 Eve 截获了用两把不同公钥加密的同一份明文 $m$ 所得到的密文 $c_1$ 与 $c_2$：
$$ c_1 \equiv m^{e_1} \pmod n,\qquad c_2 \equiv m^{e_2} \pmod n $$
此时，Eve 无需私钥即可恢复明文 $m$。
2. 数学原理
2.1 Bézout 恒等式
因为 $e_1$ 与 $e_2$ 互质，根据扩展欧几里得算法，存在整数 $s$ 和 $t$ 使得：
$$ s \cdot e_1 + t \cdot e_2 = 1 \tag{1} $$
其中 $s, t$ 一正一负（或两者符号相反）。不妨设 $s < 0, t > 0$（扩展欧几里得算法自然给出这样的结果）。
2.2 从 Bézout 到明文
将 $(1)$ 中的组合用在密文上：
$$ c_1^{s} \cdot c_2^{t} \equiv (m^{e_1})^{s} \cdot (m^{e_2})^{t} \equiv m^{\,s e_1 + t e_2} \equiv m^1 \equiv m \pmod n $$
这就是共模攻击的核心公式。无论 $s$ 是正是负，只要正确计算模逆元即可。
2.3 处理负指数
当 $s$ 为负数时，$c_1^{s}$ 在模 $n$ 意义下无法直接计算。解决办法：
$$ c_1^{s} \equiv \big(c_1^{-1}\big)^{-s} \pmod n $$
即先求 $c_1$ 的模逆元 $c_1^{-1} \pmod n$，再计算其 $(-s)$ 次幂。最终结果：
$$ m \equiv (c_1^{-1})^{-s} \cdot c_2^{t} \pmod n $$
gmpy2.powmod(c1, s, n) 在指数为负时会自动等价于 pow(gmpy2.invert(c1, n), -s, n)，因此代码层面无需手动处理。
3. 必要条件
- 同一模数 $n$：两份密文必须使用相同的 $n$ 加密。
- 同一明文 $m$：两份密文必须是同一份明文的加密结果。
- $\gcd(e_1, e_2) = 1$：两个公钥指数必须互质，否则 Bézout 恒等式只能凑出 $\gcd$ 而非 $1$，攻击退化为只能恢复 $m^{\gcd(e_1, e_2)}$。
- 密文 $c_i$ 在模 $n$ 下可逆：即 $\gcd(c_i, n) = 1$。若密文碰巧与 $n$ 不互质，则 $n$ 可被直接分解（此时攻击已无意义）。
4. 攻击流程
给定: n, e1, c1, e2, c2
要求: gcd(e1, e2) == 1
Step 1: 扩展欧几里得求 (g, s, t) 满足 s*e1 + t*e2 = 1
Step 2a: 若 s < 0, 计算 c1 的模逆: inv_c1 = c1^(-1) mod n
取 m1 = pow(inv_c1, -s, n)
Step 2b: 若 s >= 0, 取 m1 = pow(c1, s, n)
Step 3: 计算 m2 = pow(c2, t, n) (t 必为正, 否则同样求逆)
Step 4: m = (m1 * m2) % n
Step 5: 将 m 转为字节串, 得到明文5. 统一脚本
5.1 使用 gmpy2.gcdext 的简化写法
6. 防御措施
| 方法 | 说明 |
|---|---|
| 不用相同模数 | 为每个用户生成独立的$(n_i, e_i, d_i)$，这是正确的 RSA 实践 |
| 在加密时加入随机填充 | 即使同一明文，两次加密的密文也完全不同 (如 OAEP 填充) |
| 不重用密钥 | 同一份数据不应用不同公钥重复加密，避免泄漏关联 |
7. 例题解析
7.1 题目来源
某 CTF 赛题。题目给出 n, e1, c1, e2, c2，已知是同一消息的两份加密，要求解密。
7.2 解题过程
Step 1 — 检查指数互质性
>>> gmpy2.gcd(e1, e2)
mpz(1)$\gcd(11187289, 65537) = 1$，满足攻击条件。
Step 2 — 扩展欧几里得求系数
>>> s, t = gmpy2.gcdext(e1, e2)[1:]
>>> s, t
(mpz(15515395), mpz(-2646492))验证：$15515395 \times 11187289 + (-2646492) \times 65537 = 1$。
Step 3 — 计算明文
$s > 0$ 直接幂；$t < 0$ 需取逆后再幂。最终得到明文并 decode。
Step 4 — 获得 flag
解密得到的字节串即为 flag 字符串。
8. 进阶讨论
8.1 若 $\gcd(e_1, e_2) = g > 1$
此时攻击只能恢复到 $m^g$ 而非 $m$。若 $g$ 较小（如 $g=3$）且 $m^g < n$（即 $m$ 足够短），仍可在整数域开 $g$ 次方还原 $m$。但若 $m^g > n$，则需要额外信息或转向其他攻击手段。
8.2 共模攻击的变种
- 多密文场景：若同一消息用 $k$ 个不同指数加密，只要存在两个互质的指数即可攻击。
- 部分共模：当攻击者能控制加密的指数（如选择密文攻击），也可以主动构造共模条件。
- 加速技巧：当 $s$ 或 $t$ 的绝对值很大时，
powmod依然是 $O(\log s)$ 的，效率可接受。
8.3 为什么现实中会出现共模问题
最常见情况是：开发者误认为"模数一样没关系，指数不同就安全"。在一些简化实现、教学代码或管理混乱的 PKI 中，可能出现多个用户共享同一模数的错误配置，从而为共模攻击埋下隐患。
9. 总结
RSA 共模攻击利用了 Bézout 恒等式将两个密文组合还原为明文，其本质是模运算的指数线性性。攻击条件简单、实现方便，在所有 CTF 平台的 Crypto 初级题目中极具代表性。防御同样简单：绝不共享模数，这是 RSA 密钥生成的基本要求。
参考文献
- Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. Notices of the AMS, 46(2), 203–213.
- Simmons, G. J. (1983). A "Weak" Privacy Protocol Using the RSA Crypto Algorithm. Cryptologia, 7(2), 180–182.
- Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press. Chapter 8.
- Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
- CTF Wiki — RSA Common Modulus Attack: https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_module_attack/
