Coppersmith p 高位攻击不满足界:按 unknown/p_bits≈0.44 判界,爆破邻近 8-10 位并下调 epsilon=0.015 强行求解
crypto/rsa · verified
一句话结论
已知 p 的高位但未知低位比例超过经验阈值(约 p_unknown_bits / p_bits > 0.44)时,默认参数 small_roots 会返回空;可先爆破已知高位紧邻的 8–10 位(把已知高位延长、未知低位缩短),再用 small_roots(X=2^kbits, beta=0.4, epsilon=0.015) 逐候选求根,原文用该法解出 512-bit p 只差 253 位未知的 HGAME 题。
原理
- 一元 Coppersmith 的界:
f(x) = p_high + x在Zmod(n)上有小根x = p - p_high;NTL 的small_roots返回|x| < X的根,X默认取ceil(1/2·N^{β²/δ-ε})。当p ≈ N^{1/2}、δ=1、β=0.4时,理论界约N^{0.16};未知位数超过界就不返回根。 - 经验比值:原文总结
p_unknown_bits / p_bits ≤ 0.44时(beta=0.4)可直接尝试;超过则需先缩短未知区间。 - 缩短未知区间的两种手段:
1. 爆破:在已知高位之后、未知低位之前猜若干位(等价于把
p_high右移g位后再左移并加上候选i),未知低位长度减少g; 2. 调小epsilon:epsilon越小,格维数/插值多项式次数越大,可行界越宽,但计算越慢。原文在爆破 10 位后把epsilon设为0.015(默认β/8=0.05),成功解出 243 位未知低位。 - 为什么能成功:爆破把真实
p固定到某个候选的“已知高位”上,剩余未知量是连续低位,仍是一元小根;epsilon调小使 LLL 构造的界覆盖该长度。失败时roots为空,循环继续下一个候选;一旦p*q==n即命中。 - 注意
leak_p的低位补零必须与位移位数严格对应;kbits = pbits - leak_p.nbits()动态计算,避免手工算错。
触发条件
- RSA 泄露
p的连续高位,但未知低位位数超过beta/epsilon默认能处理的范围(如 512-bit p 未知 253 位); - 未知低位紧接在已知高位之后,且可承受
2^8–2^12级别的爆破; - 能运行 Sage 的
small_roots(NTL 实现),可接受单次 LLL 数分钟级耗时。
利用步骤
- 由
leak_p = p >> k还原已知高位,计算p_bits、p_unknown_bits与比值,判断是否超过 ~0.44; - 选择爆破位数
g(原文 10 位,循环i=800..2共 799 个候选),把leak_p左移g位得到延长后的已知高位; - 对每个候选
i:leak_i = (leak_p << g) + i,kbits = pbits - leak_i.nbits(),p_high = leak_i << kbits; - 构造
f = p_high + x,调用f.small_roots(X=2^kbits, beta=0.4, epsilon=0.015); - 若返回根,
p = p_high + root[0],验证p*q == n; - 恢复
d = e^{-1} mod φ(n),解密密文;若所有候选都失败,增大g或进一步调小epsilon(如 0.01),并核对位数/位移是否正确。
PoC
# sage;原文示例:512-bit p,leak=p>>253
pbits = 512
base = leak << 10 # 先猜 p 高位之后紧邻的 10 位
for i in range(800, 1, -1): # 原文循环范围 800..2,也可扩到 2^10
leak_p = base + int(hex(i), 16)
kbits = pbits - leak_p.nbits()
p_high = leak_p << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = p_high + x
roots = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.015)
if roots:
p = p_high + int(roots[0])
q = n // int(p)
if p * q == n:
d = inverse(e, (p - 1) * (q - 1))
print(long_to_bytes(int(pow(c, d, n))))
break
变体与关联
- 爆破位置可以放在已知高位与未知低位之间(延长已知段),也可以先固定低位若干位再用
X=2^{k-g};关键是让剩余未知量连续且小于调参后的界; beta与epsilon可联合调整:beta更接近 0.5 能利用“p 是 n 的大因子”,epsilon更小则格更大;- 与库内
crypto-rsa-prime-bit-chunks-multivariate-coppersmith-tiered(缺一段连续比特的一元档)、crypto-rsa-crt-multi-modulus-high-bits-coppersmith-low-bits(高位分片+CRT,epsilon=0.02)互补:本卡专讲“未知位超界时如何用爆破+epsilon 把问题拉回可解范围”; - 若爆破空间过大(如原文若直接按公式补 28 位需 2^28),应优先调
epsilon/增大格维数,或寻找更多泄露比特。
检测与防御
- 防御侧:RSA 密钥生成/使用不得泄露素数高位、低位或任何部分比特;实现中避免把
p掩码后的值写入日志、报错或调试接口; - 使用 2048-bit 以上模数并确保随机填充(OAEP),使部分明文/密钥泄露不直接可行;
- 检测侧:CTF/审计中看到
p >> k << k、p & ((1<<k)-1)、leak_p等模式即按本卡评估 Coppersmith 可行性。