RSA 只给 e,d,c:ed−1=k(p−1)(q−1) 按位数差缩小 k 枚举,iroot + prevprime/nextprime 恢复相邻素数
crypto/rsa · verified
一句话结论
当题目只给 e, d, c(p、q 由 getPrime(1024) + nextPrime(p) 生成)时,由 e·d − 1 = k(p−1)(q−1) 出发:bit_length(e·d)=2064、(p−1)(q−1) 为 2048 位,故 k 是 16 位整数(2^15 ≤ k < 2^16);枚举 k 整除 e·d−1,对商开方得中点,用 sympy.prevprime/nextprime 取相邻素数 p、q,再用题给 d 直接解 c。
原理
- 核心等式:
ed ≡ 1 (mod φ(n))⇒ed − 1 = k·φ(n) = k(p−1)(q−1),k 为正整数。 - 用位数差缩小 k:e=65537(17 位二进制)、d 约 2048 位,
ed−1约 2064 位;而(p−1)(q−1)约 2048 位(两个 1024 位素数相乘,减一不减位数)。因此 k 的位长 ≈ 2064 − 2048 = 16 位,即2^15 ≤ k < 2^16,最多 32768 个候选。 - 相邻素数的结构:题中
q = nextPrime(p),p、q 非常接近,(p−1)(q−1) ≈ p²;对(ed−1)/k开平方得到中点附近的值,再用prevprime/nextprime取相邻素数即可还原 p、q。 - 验证:对每个 k,若
(ed−1) % k == 0,计算mid = iroot((ed−1)//k, 2)[0],取p=prevprime(mid)、q=nextprime(p),检查(p−1)(q−1) == (ed−1)//k即命中。 - 为什么不用分解 n:题目没给 n(或 n 未给),只能从 ed−1 的结构反推;这是“已知私钥指数反推模数”的典型题型。
- 边界:p、q 不相邻时
prevprime(mid)不能直接得到 p,需要换 Fermat 分解或已知 n;k 的位数差也依赖题目具体参数,需要按bit_length动态计算范围。
触发条件
- 题目给出 e、d、c,未给 n;或给 n 但无法直接分解。
- p、q 由相近的素数生成(如
q = nextPrime(p)),φ 接近平方数。 bit_length(e*d)与预期 φ 位数的差值很小(如 16 位),使 k 可枚举。
利用步骤
- 计算
bd = bit_length(e*d),估计 φ 的位长(两个素数的位数之和),得到 k 的位长范围。 - 对
k in range(2^(bd-phi_bits-1), 2^(bd-phi_bits)):若(e*d-1) % k == 0,令S = (e*d-1)//k。 mid = int(iroot(S, 2)[0]);p = prevprime(mid)、q = nextprime(p)(sympy 1.13 对 gmpy2 的 mpz 参数会报 OverflowError,需先转 int)。- 若
(p-1)*(q-1) == S,命中;n = p*q。 m = pow(c, d, n),long_to_bytes得 flag。
PoC
import gmpy2, sympy
from Crypto.Util.number import long_to_bytes
e = 65537
d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
for k in range(2**15, 2**16):
if (e * d - 1) % k == 0:
S = (e * d - 1) // k
p = sympy.prevprime(int(gmpy2.iroot(S, 2)[0]))
q = sympy.nextprime(p)
if (p - 1) * (q - 1) == S:
break
n = p * q
print(long_to_bytes(pow(c, d, n)))
# b'NCTF{70u2_nn47h_14_v3ry_gOO0000000d}'(原文注释漏了 NCTF 前缀,复算明文以 b'NCTF{...}' 为准)
变体与关联
- 变体:k 的位数范围按题目位数差调整(如 1024 位模数、e 很大时 k 的范围不同)。
- 变体:p、q 不相邻但 n 已知时用 Fermat 分解(
a=isqrt(n)附近搜索)或直接 factordb。 - 关联:[[ctf-crypto-rsa-dp-leak-enumerate-x-factor]](同样从 ed 关系/部分私钥信息枚举小因子恢复 n)、[[ctf-crypto-rsa-unknown-e-rail-fence-filter]](参数缺失时的枚举思路)。
- 边界:
e*d−1的因数分解若不理想、或 φ 位长估计错误,可能错过 k;需要先用bit_length精确核对。
检测与防御
- 题目识别:只给 e、d、c;题干源码出现
getPrime(1024)与nextPrime(p);ed 位长比 2048 多十几位——考虑本方法。 - 真实系统防御:私钥指数 d 不应泄露(本方法因此成立);RSA 素数应独立随机生成,避免相邻素数(Fermat 易分解);模数 ≥2048 位。
- 加固:密钥生成使用 CSPRNG 并校验 p、q 差值足够大;私钥参数不出安全边界。