♧ Godown 安全知识树

RSA 三素数 + 威尔逊定理:p=nextprime((B!)%A),用 (A−1)!≡−1 mod A 反推 B! 后分解 n

crypto/rsa · verified

一句话结论

题目生成 p = nextprime((B!) % A)、n = p·q·r,其中 A 是 513 位素数、B = A − randint(1e3,1e5),并给出 A、B、n、e、c 时:用威尔逊定理 (A−1)! ≡ −1 (mod A) 得 B! ≡ −1 · (∏_{i=B+1}^{A−1} i)⁻¹ (mod A),据此还原 p、q,再由 r = n/(p·q) 得到三素数分解,标准 RSA 解密即得 flag。

原理

  • 威尔逊定理:p 为素数时 (p−1)! ≡ −1 (mod p)。A 是 513 位素数,所以 (A−1)! ≡ −1 (mod A)。
  • 把 B! 与 (A−1)! 关联:(A−1)! = B! · ∏_{i=B+1}^{A−1} i,于是 B! ≡ −1 · (∏_{i=B+1}^{A−1} i)⁻¹ (mod A)。
  • B 接近 A:B = A − randint(1e3,1e5),所以乘积只有 10³–10⁵ 项,可逐项 gmpy2.invert(i, A) 累乘求逆元积(或反过来算模逆),计算量很小。
  • p 的生成:p = sympy.nextPrime((B!)%A)——先算 (B!) % A,再取大于它的最近素数;q 同理由另一组 A2、B2 得到。由于 A 是素数且 B < A,(B!)%A 非零,p 是确定的。
  • 三素数分解:r = n // (p*q);φ(n) = (p−1)(q−1)(r−1),d = e⁻¹ mod φ,m = c^d mod n。
  • 为什么必须用威尔逊:B 本身有约 10^154 量级(513 位),B! 无法直接计算;威尔逊定理把“大阶乘”转成“10³–10⁵ 个小逆元的乘积”。
  • 边界:B 与 A 的差很大(如百万级以上)时逐项求逆成本上升,但仍可行;A 不是素数时威尔逊定理不成立,需要先验证 isprime(A)。

触发条件

  • 题目给出 A、B(多组)、e、c、n,源码显示 p=nextPrime((B!)%A)、n=p*q*r。
  • A 为素数,B < A 且差值为可枚举的小范围(1e3–1e5)。
  • e、c 与 n 位数匹配(e 常见 0x1001/65537)。

利用步骤

  1. 验证 A 为素数;计算 invprod = ∏_{i=B+1}^{A−1} i⁻¹ mod A(逐项 gmpy2.invert)。
  2. B_fact_mod_A = (−1 · invprod) % A。
  3. p = sympy.nextprime(B_fact_mod_A);对第二组 A2/B2 同样得到 q。
  4. r = n // (p*q),验证 p*q*r == n;φ=(p−1)(q−1)(r−1)。
  5. d = invert(e, phi),m = pow(c,d,n),long_to_bytes 得 flag。

PoC

import gmpy2, sympy, libnum

A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
e = 0x1001
c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428

def recover_p(A, B):
    invprod = 1
    for i in range(B + 1, A):
        invprod = (invprod * gmpy2.invert(i, A)) % A
    b_fact = (-invprod) % A
    return sympy.nextprime(b_fact)

p = recover_p(A1, B1)
q = recover_p(A2, B2)
r = n // (p * q)

phi = (p - 1) * (q - 1) * (r - 1)
d = gmpy2.invert(e, phi)
print(libnum.n2s(int(pow(c, d, n))))
# b'RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}'(原文注释漏了 RoarCTF 前缀,复算明文以 b'RoarCTF{...}' 为准)

变体与关联

  • 变体:B 与 A 差值较大时可先算 (A−1)! 的逆元关系再合并,或改用 Wilson 的推广形式;也可用 gmpy2.fac 不可行时坚持逆元积。
  • 变体:p 的生成换成 nextprime((B!)%A + k) 等变形时,先还原 (B!)%A 再按偏移找素数。
  • 关联:[[ctf-crypto-rsa-shared-prime-batch-gcd]](多素数/多模数的 gcd 分解)、[[ctf-crypto-rsa-ed-minus-one-bitlength-k-prevprime]](同样依赖素数生成结构的恢复)。
  • 边界:A 非素数、B ≥ A、或差值大到无法逐项求逆时方法失效;三素数中 r 未知时必须有 n 才能反推。

检测与防御

  • 题目识别:源码出现 getPrime(513)、B=A-random.randint(...)、nextPrime((B!)%A)、n=p*q*r——直接套威尔逊。
  • 真实系统防御:不要用这种“由公开可算量生成素数”的方案(p 可被任意人复算);RSA 素数必须来自 CSPRNG 独立生成;模数 ≥2048 位。
  • 加固:密钥生成后做素性、位长、差值检查;禁止在源码/题目中暴露足以复现素因子的中间量。