RSA 小指数广播攻击:三组 e=3 同明文 CRT 合成后开立方
ctf/crypto · verified
一句话结论
同一明文用相同的小公钥指数 e=3、不同且两两互素的模数分别加密时,把三组密文用 CRT 合成到 m^3 mod n1n2n3;若 m^3 < n1n2n3,合成值就是精确的 m^3,直接开立方即可恢复明文,无需分解任何模数。
原理
- 广播场景:同一消息
m用三个不同模数n1,n2,n3、同一e=3加密,得到c_i = m^3 mod n_i。 - CRT 合成:三组同余式可唯一确定
M = m^3 mod N,N = n1*n2*n3。 - 明文足够短:若
m^3 < N(示例三元组合成 1315 位,m^3未超过),则M = m^3是精确整数,不存在模回绕。 - 开立方即明文:
gmpy2.iroot(M, 3)若返回exact=True,根就是m;若不精确,说明m^3 >= N,需要 Coppersmith 等更复杂方法。 - 为什么成立:RSA 的安全性依赖模数分解,但广播场景下攻击者不需要分解;CRT 把三个同余式合并,指数小使明文幂次没有溢出模数。
触发条件
- 同一明文用相同小指数(常见
e=3)加密多次。 - 各模数两两互素(gcd 为 1),且数量满足
k >= e(示例 3 组)。 - 明文长度满足
m^e < ∏ n_i(无填充或填充较短)。 - 攻击者拿到所有密文与模数。
利用步骤
- 收集
e=3的多组(n_i, c_i),确认明文相同(题面提示/相同前缀/相同长度)。 - 验证模数两两互素;若存在共享因子,先走共享素因子路径。
- 用 CRT 合并
c_i得到M mod N,其中N=∏n_i。 - 对
M开e次整数根;exact=True则得到明文,否则考虑 Coppersmith/填充方案。 - 将根转字节,检查 flag 格式;用
pow(m,e,n_i)==c_i对每组回环验证。 - 与同题其他路径(如共享素因子)交叉比对,确认结果一致。
PoC
from sympy.ntheory.modular import crt
import gmpy2
ns = [n1, n2, n3]
cs = [c1, c2, c3]
M, N = crt(ns, cs)
assert M < N
root, exact = gmpy2.iroot(M, 3)
assert exact
plain = root.to_bytes((root.bit_length() + 7) // 8, "big")
print(plain)
# 回环校验
for n, c in zip(ns, cs):
assert pow(int(root), 3, n) == c
原文实测:三组合成模数 1315 位,开立方精确命中,明文与共享素因子路径完全一致,最终 flag{Sh4r3d_Pr1m3_0v3r_0TA_26}。
变体与关联
- 指数变体:
e=3/5/17等小指数;组数至少为e,更多组可提高∏n_i从而更容易满足无回绕。 - 填充变体:PKCS#1 v1.5/OAEP 会引入随机填充,破坏“同明文”条件;若填充线性相关,可用 Coppersmith 相关消息攻击。
- 混合路径:同题可同时存在共享素因子;两条路径互相验证。
- 关联卡片:[[crypto-rsa-common-modulus]](同一模数、不同指数)、[[ctf-crypto-rsa-shared-prime-batch-gcd]](共享素因子分解)、[[crypto-rsa-fermat-close-prime-factorization]](模数分解)。
- 边界:
m^3 >= ∏n_i时 CRT 值发生回绕,简单开立方失败;模数不互素时 CRT 不适用;明文不同则不能广播。
检测与防御
- CTF 验证:
iroot必须exact=True,并对每组密文回环校验;只得到“看起来像明文”的字节不足以确认。 - 工程防御:RSA 公钥指数使用 65537;加密必须使用随机化填充(OAEP);同一消息不要用同一小指数向多个接收方广播。
- 检测信号:批量公钥指数为 3/5;同一明文/相同长度密文对应多个模数;模数乘积远大于明文幂次。
- 复盘:看到“多个模数 + 小指数 + 同明文”先试 CRT 开根,再考虑分解类攻击。