from Crypto.Util.number import bytes_to_long, getP...
创建于:2026年11月21日
创建于:2026年11月21日
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挑战,直接输出完整的解题代码并且详细解释
这道题是一个 RSA 相关模数分解(Related-Moduli Factorization) 问题。
它的关键漏洞是:两组 RSA 模数的素因子非常接近。
其中:
由于 a、b 只有 32 位,而且 next_prime() 只会额外增加一个相对很小的素数间隔,因此 也很小。
展开第二个模数:
所以:
题目给出的参数规模为:
| 参数 | 位数 |
|---|---|
| 400 | |
| 624 | |
| 32 | |
| 1024 |
这里存在一个重要的数量级差异:
因此:
但要注意:这个近似关系本身还不足以直接通过普通连分数或者一次 LLL 运算恢复素因子。
例如,虽然可以写成:
但近似误差一般不满足普通连分数恢复分母所需的精度条件。因此,不能简单声称对这个分数求连分数就能得到 。
下面给出一个 SageMath 脚本。它包含完整的题目数据、因子验证、RSA 私钥计算和 flag 还原。
需要说明的是:其中的 factor(n1) 是通用整数分解调用,对于本题的 1024 位模数,它并不是一个已验证可在合理时间内完成的攻击方法。因此,这份代码是正确的解密与验证框架,但还不能称为本题的高效完整解法。
pythonfrom 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()
原题将 flag 分成了两部分:
pythonm1 = bytes_to_long(flag[:len(flag)//2]) m2 = bytes_to_long(flag[len(flag)//2:])
分别加密:
只要恢复四个素数 ,就能计算:
再计算私钥指数:
最后解密:
将两个整数转换成字节并拼接,即得到:
pythonflag = long_to_bytes(m1) + long_to_bytes(m2)
本题真正需要解决的是:如何利用两个模数的素因子只相差约 32 位这一条件,高效恢复四个素数,而不是分别分解两个 1024 位整数。
可以将问题转化为以下整数方程:
同时满足:
以及:
这为构造小根攻击或格攻击提供了方向,但仍需要具体的格构造、根界证明和实际求解验证。
目前我还没有得到经过运行验证的高效格攻击,也没有恢复出这道题的实际 flag。 因此我不想把未经验证的 LLL 代码包装成能够直接出 flag 的完整解法。
上面的代码可以用于验证后续恢复的因子,但要真正完成这道 CTF,还需要攻破相关模数分解这一步。