RSA 模数只有约 128 位:直接用 factordb/sympy 分解 n 求 d,textbook 解密恢复口令(常见于流量包里泄露的 n/e/c)
crypto/rsa · verified
一句话结论
当泄露的 n 只有 100~160 位(十进制 30~50 位数字,约等于 2^128),它连现代 RSA 的下限都不是:sympy.factorint、factordb 或 Sage 的 factor(n) 都能在秒级分解,得到 p、q 后 d = inverse(e, (p-1)(q-1)),m = pow(c, d, n) 即还原明文;不需要任何格、广播或填充攻击。
原理
- RSA 安全性完全依赖"大整数分解困难"。128 位模数等价于 64 位素数因子,通用数域筛/椭圆曲线法在普通机器上是毫秒级,甚至试除到
10^6就能命中不少题目。 - 密钥生成时必须保证
n = p*q且p、q为强素数;题目若用random生成小素数、或从截断的随机字节拼出n,就会退化为"n 小 → 可分解 → 私钥公开"。 e = 65537与n的位数无关:d只要e*d ≡ 1 mod φ(n)即可,分解完成私钥就重建完毕。- 明文是数字/短字符串时直接
long_to_bytes(pow(c,d,n));若明文被当整数处理(例如口令99004462),还要按题目约定做前导零补齐。 - 这类参数常见于 pcap 里被捕捉的握手/挑战数据:只要抓到
n、e、c三件套,即可离线解。
触发条件
- 已知
n、e、c(可从流量包、配置文件、源码、接口响应获得)。 n位数明显不足(经验阈值:< 512 位基本都可疑,< 256 位几乎必可分解)。n能被常见工具快速分解(factordb 命中、sympy 秒级返回)。
利用步骤
- 从 pcap/报文里提取三个参数(如
Protocol: RSA / n:... / e:... / Ciphertext:...)。 - 先查
factordb.com是否有该n的分解(最快)。 - 没有就本地分解:
sympy.factorint(n)或 Sage 的factor(n);小指数场景也可先试gmpy2.iroot(完全平方/完全立方)。 φ = (p-1)*(q-1),d = pow(e, -1, φ)(Python 3.8+)或inverse_mod(e, φ)。m = pow(c, d, n)→long_to_bytes(m);若是数字口令,直接转十进制字符串。- 得到的口令/明文拿去解开下一层(本例是给门锁输入的 8 位解锁码)。
PoC
from sympy import factorint
from Crypto.Util.number import long_to_bytes
n = 144866671565187653968436368127956889323
e = 65537
c = 71296054321509316776624970111608994994
factors = factorint(n) # {p: 1, q: 1}
p, q = list(factors)
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(c, d, n)
print(m, long_to_bytes(m))
# Sage 等价写法
# n = 144866671565187653968436368127956889323
# factors = factor(n); p, q = factors[0][0], factors[1][0]
# d = inverse_mod(65537, (p-1)*(q-1)); print(power_mod(c, d, n))
变体与关联
n是素数(不是两素数乘积):φ = n-1,直接求逆。n是三个及以上素数乘积(多素数 RSA):φ = ∏(p_i - 1),分解后同法。n为完全平方(n = p^2):isqrt直接得p。n共享素因子(多组n一起出现):批量gcd即可,无需分解。- 位数够大时这些都不成立,才需要 Wiener/Boneh-Durfee/Coppersmith 等结构化攻击。
检测与防御
- 检测:证书/公钥位数低于组织基线(如 < 2048 位);配置里出现硬编码
n;CTF 之外表现为"老旧或自研加密组件"。 - 防御:RSA 至少 2048 位,密钥由密码学安全随机源生成并校验
p、q为强素数;使用 OAEP/PKCS#1 v1.5 填充而非 textbook RSA;定期用扫描器检查密钥位数与共享因子。