RSA e=3 明文过短:密文未模约减时直接整数立方根恢复
crypto/rsa · verified
一句话结论
RSA 使用 e=3 时,如果明文 m 很短、满足 m^3 < n,那么密文 c = m^3 mod n 实际上没有发生模约减,c 就是普通整数立方;对 c 求整数三次根即可恢复 m,不需要分解 n 或私钥。
原理
- RSA 加密:
c = m^e mod n。当m^e < n时,m^e本身小于模数,mod n不改变值,所以c = m^e是精确的整数幂。 - 低指数:
e=3时条件为m^3 < n。本题n约 1536 bit,flag 只有几十字节(约 300 bit),m^3约 900 bit,远小于n,因此没有模约减。 - 整数根:对
c做integer_nthroot(c, 3),若余数为 0(exact=True),得到精确的m;若有多个候选/填充,需要按明文格式(flag{...})验证。 - 为什么成立:这是“小明文/低指数”攻击的最简单形式;不需要 Coppersmith,也不需要知道
p/q。如果m^3 > n,密文会回绕,整数根不再精确,需要 Coppersmith/广播/Håstad 等方法。 - 边界:
m的长度必须满足m^3 < n(约n^(1/3));e越大条件越严格;若使用了随机填充,m变长/随机,攻击失效。
触发条件
- RSA 公钥指数
e很小(常见 3),且明文很短/结构化(如短 flag)。 - 加密时没有填充,或填充后仍满足
m^e < n。 - 拿到
n、e、c;c的整数e次根精确(余数为 0)。 - 明文格式可验证(
flag{...}、固定前缀)。
利用步骤
- 确认
e=3(或小指数)、n的位长、c的大小;估算c的立方根是否约等于明文长度。 - 用
sympy.integer_nthroot(c, 3)或gmpy2.iroot(c, 3)求整数根,检查exact/余数。 - 把根转大端字节,检查是否以
flag{开头、以}结尾;若有多余填充,按格式截取。 - 用
pow(m, 3, n) == c回代验证;本题得到flag{women_yaozenyangshuochu_zaijianne}。 - 若根不精确,说明
m^3 > n,改用 Coppersmith 小根/广播攻击/相关消息攻击。
PoC
from sympy import integer_nthroot
c = 37200871830677789908396551249543062637188978192630580181459724500444997949046932604271895351388763870279778575053912860012758908346269536765620259753461261401130192826626734845716857635735893923996366934581919022064045623345585748996968570735079180805789002573008815409176075596901
m, exact = integer_nthroot(c, 3)
assert exact, "c is not a perfect cube"
plain = m.to_bytes((m.bit_length() + 7) // 8, "big")
print(plain.decode()) # flag{women_yaozenyangshuochu_zaijianne}
变体与关联
- 变体(m^e > n):用 Coppersmith 小根(已知部分明文/填充)、Håstad 广播(同一明文多组低指数)、相关消息攻击。
- 变体(e=3 + 多接收方):中国剩余定理合成
m^3后再开立方;见广播攻击。 - 变体(填充):PKCS#1 v1.5 填充下
m变长,需 Bleichenbacher 类攻击;OAEP 通常使小明文攻击失效。 - 关联卡片:[[crypto-rsa-common-modulus]](共模攻击)、[[crypto-rsa-multiprime-partial-key-coppersmith]](Coppersmith 小根)、[[ctf-crypto-rsa-hastad-broadcast-e3-crt]](Håstad 广播)。
- 边界:
m^3<n是硬条件;c不是完全立方时不能用;填充/随机化会让明文变长;n太小可能被直接分解。
检测与防御
- 填充:使用 OAEP(RSA-OAEP)或至少 PKCS#1 v1.5,避免无填充 RSA;随机填充使明文变长且不可预测。
- 指数/密钥:
e=65537是常见安全选择;e=3本身不是漏洞,但必须配合正确填充和足够长的明文。 - 检测:CTF/审计中看到
e=3、短 flag、c远小于n,先试整数立方根;生产环境检查 RSA 实现是否使用无填充/短明文。 - 响应:不要把短秘密直接作为 RSA 明文;密钥/消息长度遵循标准。