XSWCTF 题解
输入“/”快速插入内容
XSWCTF 题解
XSWCTF 题解
用户3187用户3187
用户4696用户46962025年12月29日修改
初赛
AI 爆了 34 题，笑嘻了。
XSWC CTF 2025 初赛.pdf
19.90MB
复赛
candlest
Loss N-4
没一血有点可惜。
RSA，给了 e, c, d
由于 q = next_prime(p) ，可以看作
,
那么我们怎么枚举 k 呢？
GPT 告诉我
也就是说
，我们枚举
区间即可。
我们取 B=5000 的一个小半径，对
为中心的附近进行因数的搜索。
找到一个就能找到另外一个，恢复 n，然后正常的 RSA 解密。
代码块
from Crypto.Util.number import *
from math import isqrt
# 已知的参数（替换成你题目里的数）
c = 17267007548350134211446534538562532393987607956398472220551618753087082023879735062442545398431870403872077195818978989886709629866990217347439170223507808164879731729759157752461662209938291986405423704335805393839979165773499714878470151278415094133786535946476503084049717463486099847254665931743627071610
d = 15752258185352337654082846377897348689758687031968786034503680876894166455217514255597901688908424136052403746641807704787562349822148913951970347309546537765183467045213301168433455090131147662630933001405065553783578099091001885819766898162581045129599564003306979636805994413087552852437577804628737608073
e = 0x10001
A = e * d - 1
# 扫描的 a 附近半径，可以按需要调大/调小
B = 5000
def next_prime(n):
"""找到大于 n 的下一个素数"""
if n % 2 == 0:
n += 1
else:
n += 2
while not isPrime(n):
n += 2
return n
def recover_n_from_ed(e, d, B=5000):
A = e * d - 1
for k in range(1, e):
# φ(n) 必须是整数
if A % k != 0:
continue
phi = A // k
# φ(n) 至少应该是 1023~1024 bit，可以做一些粗略过滤
if phi.bit_length() < 1000:
continue
# 在 sqrt(phi) 附近找因子 a ≈ p-1
x = isqrt(phi)
for delta in range(-B, B + 1):
a = x + delta
if a <= 0:
continue
if phi % a != 0:
continue
b = phi // a
p = a + 1
q = b + 1
# 粗略过滤：p,q bit 长度应该接近 512
if not (510 <= p.bit_length() <= 514):
continue
if not (510 <= q.bit_length() <= 514):
continue
# 检查 p,q 为素数
if not isPrime(p) or not isPrime(q):
continue
# 检查 q 确实是 next_prime(p)
if next_prime(p) != q:
continue
n = p * q
return n, p, q, k, phi
return None, None, None, None, None
n, p, q, k, phi = recover_n_from_ed(e, d, B)
if n is None:
print("[-] 没找到合适的 n，可以考虑增大 B 或检查 d/e 是否正确。")
else:
print("[+] 找到 n!")
print("k =", k)
print("p =", p)
print("q =", q)
print("n =", n)
# 解密
m = pow(c, d, n)
flag = long_to_bytes(m)
print("flag =", flag)