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)。
利用步骤
- 验证 A 为素数;计算
invprod = ∏_{i=B+1}^{A−1} i⁻¹ mod A(逐项gmpy2.invert)。 B_fact_mod_A = (−1 · invprod) % A。p = sympy.nextprime(B_fact_mod_A);对第二组 A2/B2 同样得到 q。r = n // (p*q),验证p*q*r == n;φ=(p−1)(q−1)(r−1)。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 位。
- 加固:密钥生成后做素性、位长、差值检查;禁止在源码/题目中暴露足以复现素因子的中间量。