♧ Godown 安全知识树

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 可枚举。

利用步骤

  1. 计算 bd = bit_length(e*d),估计 φ 的位长(两个素数的位数之和),得到 k 的位长范围。
  2. 对 k in range(2^(bd-phi_bits-1), 2^(bd-phi_bits)):若 (e*d-1) % k == 0,令 S = (e*d-1)//k。
  3. mid = int(iroot(S, 2)[0]);p = prevprime(mid)、q = nextprime(p)(sympy 1.13 对 gmpy2 的 mpz 参数会报 OverflowError,需先转 int)。
  4. 若 (p-1)*(q-1) == S,命中;n = p*q。
  5. 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 差值足够大;私钥参数不出安全边界。