多素数 RSA 立方提示 p³ mod n + q=7p+i:直接开立方恢复 p 并分解 n
crypto/rsa · verified
一句话结论
当多素数 RSA 使用 n = p*q*r(p、r 各 1024 位,q = 7p + i 且 i 很小),并额外泄露 hint = p³ mod n 时,由于 p³ < n,pow(p,3,n) 不会回绕,直接对 hint 开整数立方根就得到 p;再枚举很小的 i 用 (n/p) % (7p+i) 找到 q,最后 r = n/(p*q),即可计算 φ(n)、私钥并解密。
原理
- 提示为何是精确立方:p 是 1024 位(p³ 为 3071 位);n = p·q·r 中 q≈7p(本题 1027 位)、r 是 1024 位,n 约 1024+1027+1024 = 3075 位(本题实测 3074 位)。p³ 与 n 仅差约 3 位(n/p³≈8),但 p³ < n,所以
pow(p, 3, n)不发生回绕,hint 就是 p³ 的精确值,gmpy2.iroot(hint, 3)可还原 p;边界是 p³ 必须严格小于 n,而不是“远小于”。 - q 的线性关系:题目构造 q = 7p + i,i 从 0 开始递增直到 q 为素数。i 只需在较小范围内枚举(本题实际 i=88),在已知 p 和 n/p 后,枚举 i 检查
n_p % (7*p + i) == 0即可恢复 q;随后 r = n/(p*q)。 - 为什么能解密:得到三个素因子后 φ(n) = (p-1)(q-1)(r-1),
d = e^{-1} mod φ(n),m = c^d mod n,long_to_bytes得到明文。整个攻击的根因是“泄露了素因子的幂,且另一素因子与它只差一个小偏移”。 - 与常规多素数 RSA 的区别:正常多素数 RSA 只要三个 1024 位独立随机素数就安全;本卡利用的是题目/实现的密钥生成缺陷(hint + 线性关系),不是 RSA 算法本身的通用弱点。
触发条件
- 多素数 RSA,n = p·q·r(或更多因子),且 p^k < n,hint = p^k mod n 被公开(k=2/3 等)。
- 至少一个素因子与其他因子存在小偏移线性关系(如 q = a·p + i,i 可枚举),或能通过其它方式验证候选因子。
- 攻击者拿到 n、e、c、hint,且 e 与 φ(n) 互素(常规情况)。
- 若 p^k > n,hint 只是模值,需要 Coppersmith/模根等更复杂方法;本卡不覆盖。
利用步骤
- 用
gmpy2.iroot(hint, k)对 hint 开 k 次整数根,验证pow(p, k) == hint(未取模的精确幂)。 - 计算
n_p = n // p,从 i=1 开始枚举候选q = a*p + i,检查n_p % q == 0;命中后验证 q 为素数、p*q 整除 n。 - 计算
r = n // (p*q),验证p*q*r == n且 r 为素数。 - 计算
phi = (p-1)*(q-1)*(r-1),d = inverse(e, phi),m = pow(c, d, n),long_to_bytes(m)得到明文/密码。 - 若开立方得到的 p 不整除 n,说明 p^k >= n 或 hint 有噪声,需换 Coppersmith/模根/枚举分支。
PoC
from Crypto.Util.number import long_to_bytes, inverse
from sympy import isprime
import gmpy2
c = <ciphertext>
n = <modulus>
e = 65537
hint = <hint>
# 1) 立方提示直接开根(p^3 < n)
p = gmpy2.iroot(hint, 3)[0]
assert pow(p, 3) == hint and n % p == 0
# 2) q = 7p + i,枚举小 i
n_p = n // p
i = 0
while True:
i += 1
q = 7 * p + i
if n_p % q == 0:
break
assert isprime(q)
# 3) 剩余因子 r
r = n // (p * q)
assert p * q * r == n
# 4) 解密
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
原文在 1024 位 p/r、q=7p+i 的实例上运行成功,输出解压密码 f8be83156f83438cb172651ec3c5e168。
变体与关联
- 指数变体:hint = p²、p⁴ 等;只要能开整数根并整除 n 即可。
- 关系变体:q = a·p + i(a 已知)、q = p + i、q = next_prime(p) 等;i 较大时改用 Coppersmith 小根或 Fermat 分解。
- 噪声变体:hint 带随机噪声/只给高位时,转到格攻击(Coppersmith/LLL)。
- 关联:[[crypto-rsa-hint-difference-gcd-factorization]](多组 hint 差值 GCD)、[[crypto-rsa-multiprime-partial-key-coppersmith]](三素数高位泄露)、[[crypto-rsa-fermat-close-prime-factorization]](近邻素数)。
- 边界:p^k >= n 时开根不再精确;i 很大或 q 与 p 无关系时枚举失效;e 与 φ 不互素时需特殊处理。
检测与防御
- 防御:不要公开任何素因子的幂/乘积等提示;多素数 RSA 的三个因子应独立均匀随机生成,禁止
q=a*p+i之类可预测关系。 - 防御:使用标准库生成 RSA 密钥,避免自实现密钥生成;对私钥材料做访问控制与审计。
- 检测:代码/题面中出现
pow(p, k, n)、hint、q = a*p + i等模式;密钥生成脚本中素因子存在线性关系。 - 加固:迁移到 RSA-OAEP/RSA-KEM 或 ECC;密钥长度满足当前标准;泄露 hint 后立即轮换密钥。