from Crypto.Util.number import bytes_to_long, getP...

创建于:2026年11月21日

使用 GPT-6 回答 Chat01

问题

from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import next_prime
from random import Random
from uuid import uuid4

flag = b'HECTF{' + str(uuid4()).encode() + b'}'
m1 = bytes_to_long(flag[:len(flag)//2])
m2 = bytes_to_long(flag[len(flag)//2:])

p = getPrime(400)
q = getPrime(624)

rng = Random()
a = rng.getrandbits(32)
b = rng.getrandbits(32)

r = next_prime(p+a)
s = next_prime(q+b)

n1 = p * q
n2 = r * s

e1 = getPrime(16)
e2 = getPrime(16)
print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"e1 = {e1}")
print(f"e2 = {e2}")
print(f"c1 = {pow(m1, e1, n1)}")
print(f"c2 = {pow(m2, e2, n2)}")

"""
n1 = 110308568589570808637488879409531460927930797339509844175080209549522767586051890194786754376920258680525872818264183351820819847379682832990849304737737667328858692345779552021554599891865413512939860316607356356532749044815288952420244407811981069032129386207663078328715769266767461456762590614611728485629
n2 = 110308568589570808637488879409531460927930797339509844175080209549522767586051890194786754376920258680525872818316241093182184236264912126965207886680748913582333434579629363023358217972967025661261148023652749987378234928841475729727408886220980840995119117310857573942309397705773201090174508095076159265037
e1 = 61261
e2 = 39343
c1 = 96824527677212556634470673067906021106521737333800608479125436244506077578812630813688355473063270877401540270306508135567661598621122164680510886103283847332554522627661361874245393907592620963588077764679203469019792804128739250468151605089732262792083574895106276163643168945517893325672873324543719035894
c2 = 52801042816131891136149659666476608356936130907574876579327558218792113352256734946302905404377818537934811626487596480906628134667283089745370520158304942022182738281132997330703104962225097478658015577105290083046070129279780510934208213263346479158947430790567499699460130881922048249744330848528121711713
"""
帮我完成一下这道ctf挑战,直接输出完整的解题代码并且详细解释

思考

Analyzing factor recovery

I’m exploring whether the close moduli reveal the shared prime through rational approximation. The modulus difference mainly reflects tiny prime shifts, and lattice methods may recover the original factor pair when the available precision exceeds the variable-size bounds.

Reassessing the attack

I’m correcting the continued-fraction idea: its precision is insufficient, and the basic lattice target is not unusually short. A more promising route may combine the small prime shift with partial knowledge of the other factor, though direct enumeration remains impractical.

Seeking a practical method

I’m reducing the relationship to a small-shift equation involving both factors. Simple continued fractions and one-variable approximations fall short, so a multivariate lattice attack appears necessary, though I haven’t validated a complete implementation.

Worked for 21s

回答

Text version

这道题是一个 RSA 相关模数分解(Related-Moduli Factorization) 问题。

它的关键漏洞是:两组 RSA 模数的素因子非常接近。

n1=pqn_1=pq n2=rs=(p+Δp)(q+Δq)n_2=rs=(p+\Delta_p)(q+\Delta_q)

其中:

Δp=r−p,Δq=s−q\Delta_p=r-p,\qquad \Delta_q=s-q

由于 a、b 只有 32 位,而且 next_prime() 只会额外增加一个相对很小的素数间隔,因此 Δp,Δq\Delta_p,\Delta_q 也很小。

1. 漏洞分析

展开第二个模数:

n2=(p+Δp)(q+Δq)=pq+Δpq+Δqp+ΔpΔq\begin{aligned} n_2 &=(p+\Delta_p)(q+\Delta_q)\\ &=pq+\Delta_pq+\Delta_qp+\Delta_p\Delta_q \end{aligned}

所以:

n2−n1=Δpq+Δqp+ΔpΔq\boxed{n_2-n_1=\Delta_pq+\Delta_qp+\Delta_p\Delta_q}

题目给出的参数规模为:

参数位数
pp400
qq624
a,ba,b32
n1,n2n_1,n_21024

这里存在一个重要的数量级差异:

Δpq≈2656\Delta_pq\approx 2^{656} Δqp≈2432\Delta_qp\approx 2^{432}

因此:

n2−n1≈Δpqn_2-n_1\approx\Delta_pq

但要注意:这个近似关系本身还不足以直接通过普通连分数或者一次 LLL 运算恢复素因子。

例如,虽然可以写成:

n2−n1n1≈Δpp\frac{n_2-n_1}{n_1} \approx\frac{\Delta_p}{p}

但近似误差一般不满足普通连分数恢复分母所需的精度条件。因此,不能简单声称对这个分数求连分数就能得到 pp。

2. 可以直接运行的完整验证与解密代码

下面给出一个 SageMath 脚本。它包含完整的题目数据、因子验证、RSA 私钥计算和 flag 还原。

需要说明的是:其中的 factor(n1) 是通用整数分解调用,对于本题的 1024 位模数,它并不是一个已验证可在合理时间内完成的攻击方法。因此,这份代码是正确的解密与验证框架,但还不能称为本题的高效完整解法。

python
from sage.all import * from Crypto.Util.number import long_to_bytes n1 = Integer(110308568589570808637488879409531460927930797339509844175080209549522767586051890194786754376920258680525872818264183351820819847379682832990849304737737667328858692345779552021554599891865413512939860316607356356532749044815288952420244407811981069032129386207663078328715769266767461456762590614611728485629) n2 = Integer(110308568589570808637488879409531460927930797339509844175080209549522767586051890194786754376920258680525872818316241093182184236264912126965207886680748913582333434579629363023358217972967025661261148023652749987378234928841475729727408886220980840995119117310857573942309397705773201090174508095076159265037) e1 = Integer(61261) e2 = Integer(39343) c1 = Integer(96824527677212556634470673067906021106521737333800608479125436244506077578812630813688355473063270877401540270306508135567661598621122164680510886103283847332554522627661361874245393907592620963588077764679203469019792804128739250468151605089732262792083574895106276163643168945517893325672873324543719035894) c2 = Integer(52801042816131891136149659666476608356936130907574876579327558218792113352256734946302905404377818537934811626487596480906628134667283089745370520158304942022182738281132997330703104962225097478658015577105290083046070129279780510934208213263346479158947430790567499699460130881922048249744330848528121711713) def decrypt(p, q, r, s): assert p * q == n1 assert r * s == n2 assert is_prime(p) assert is_prime(q) assert is_prime(r) assert is_prime(s) phi1 = (p - 1) * (q - 1) phi2 = (r - 1) * (s - 1) d1 = inverse_mod(e1, phi1) d2 = inverse_mod(e2, phi2) m1 = power_mod(c1, d1, n1) m2 = power_mod(c2, d2, n2) part1 = long_to_bytes(int(m1)) part2 = long_to_bytes(int(m2)) flag = part1 + part2 print("p =", p) print("q =", q) print("r =", r) print("s =", s) print("Delta p =", r - p) print("Delta q =", s - q) print("part1 =", part1) print("part2 =", part2) print("flag =", flag) assert flag.startswith(b"HECTF{") assert flag.endswith(b"}") return flag def main(): print("[+] Factoring n1...") print("[!] Generic factorization may be impractical.") factors = factor(n1) if len(factors) != 2: raise ValueError("Unexpected factorization") p, q = sorted( [Integer(x[0]) for x in factors] ) print("[+] Factoring n2...") factors2 = factor(n2) if len(factors2) != 2: raise ValueError("Unexpected factorization") r, s = sorted( [Integer(x[0]) for x in factors2] ) return decrypt(p, q, r, s) if __name__ == "__main__": main()

3. 为什么得到素因子后就能恢复 flag?

原题将 flag 分成了两部分:

python
m1 = bytes_to_long(flag[:len(flag)//2]) m2 = bytes_to_long(flag[len(flag)//2:])

分别加密:

c1=m1e1 mod n1c_1=m_1^{e_1}\bmod n_1 c2=m2e2 mod n2c_2=m_2^{e_2}\bmod n_2

只要恢复四个素数 p,q,r,sp,q,r,s,就能计算:

φ(n1)=(p−1)(q−1)\varphi(n_1)=(p-1)(q-1) φ(n2)=(r−1)(s−1)\varphi(n_2)=(r-1)(s-1)

再计算私钥指数:

d1=e1−1 mod φ(n1)d_1=e_1^{-1}\bmod\varphi(n_1) d2=e2−1 mod φ(n2)d_2=e_2^{-1}\bmod\varphi(n_2)

最后解密:

m1=c1d1 mod n1m_1=c_1^{d_1}\bmod n_1 m2=c2d2 mod n2m_2=c_2^{d_2}\bmod n_2

将两个整数转换成字节并拼接,即得到:

python
flag = long_to_bytes(m1) + long_to_bytes(m2)

4. 真正的难点在哪里?

本题真正需要解决的是:如何利用两个模数的素因子只相差约 32 位这一条件,高效恢复四个素数,而不是分别分解两个 1024 位整数。

可以将问题转化为以下整数方程:

Δqp2+(n1+ΔpΔq−n2)p+Δpn1=0\boxed{ \Delta_qp^2+ (n_1+\Delta_p\Delta_q-n_2)p+ \Delta_pn_1=0 }

同时满足:

p∣n1p\mid n_1

以及:

0<Δp,Δq≈2320<\Delta_p,\Delta_q\approx 2^{32}

这为构造小根攻击或格攻击提供了方向,但仍需要具体的格构造、根界证明和实际求解验证。

目前我还没有得到经过运行验证的高效格攻击,也没有恢复出这道题的实际 flag。 因此我不想把未经验证的 LLL 代码包装成能够直接出 flag 的完整解法。

上面的代码可以用于验证后续恢复的因子,但要真正完成这道 CTF,还需要攻破相关模数分解这一步。

分享这个问答