WEEK1-CRYPTO
Classic
给的那段密文非常像维吉尼亚密码
非预期：我直接去盲了一波密钥是 HGAME 竟然给我猜对了。
接下来是预期解法：
给了一个RSA问题，大概是解出之后能得到密钥
# Copy this to SageMath
# 模拟 Crypto 库的功能，避免在线环境报错
def long_to_bytes(val):
return int(val).to_bytes((int(val).bit_length() + 7) // 8, byteorder='big')
# 题目数据 [2]
n = 103581608824736882681702548494306557458428217716535853516637603198588994047254920265300207713666564839896694140347335581147943392868972670366375164657970346843271269181099927135708348654216625303445930822821038674590817017773788412711991032701431127674068750986033616138121464799190131518444610260228947206957
leak = 6614588561261434084424582030267010885893931492438594708489233399180372535747474192128
c = 38164947954316044802514640871285562707869793354907165622336840432488893861610651450862702262363481097538127040490478908756416851240578677195459996252755566510786486707340107057971217557295217072867673485369358370289506549932119879791474279677563080377456592139035501163534305008864900509896586230830001710243
e = 65537
# 1. 构造多项式
# leak 是 p 右移 230 位，因此 p_high = leak * 2^230
p_high = leak << 230
PR.<x> = PolynomialRing(Zmod(n))
f = p_high + x
# 2. 调用 small_roots
# beta=0.4: 我们寻找模 n 的因子的根，该因子大小约为 n^0.4 (实际上是0.5，但放宽到0.4更稳)
# epsilon=0.01: 调整 LLL 算法的参数
# X=2^231: 稍微放宽上界，确保包含真实根
print("[*] Running Coppersmith attack...")
roots = f.small_roots(X=2^231, beta=0.4, epsilon=0.01)
if roots:
x0 = roots[0]
p = p_high + Integer(x0)
print(f"[+] Recovered p: {p}")
# 3. 标准 RSA 解密
if n % p == 0:
q = n // p
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = power_mod(c, d, n)
flag = long_to_bytes(m)
print(f"[+] Flag: {flag}")
try:
print(f"[+] Decoded: {flag.decode()}")
except:
print("[!] Could not decode bytes to utf-8 directly")
else:
print("[-] Calculated p is not a factor of n. Check parameters.")
else:
print("[-] Roots still not found. Try increasing epsilon slightly (e.g., 0.02).")
[*] Running Coppersmith attack...
[+] Recovered p: 11413053109552188507052666630091285760873067504449985234054655694908075994350969330957385458253490012573212730089010386220127731924243642741330801109560321
[+] Flag: b'Vigenere,key=hgame'
[+] Decoded: Vigenere,key=hgame
Flux
这是一个典型的CTF密码学题目，主要考察对非线性同余生成器（LCG的变体）的破解以及对混合运算哈希函数的逆向。
解决这个问题的步骤如下：
1. 恢复 Flux 生成器的参数 (a, b, c)
根据代码中的 Flux 类，生成器的状态更新公式为二次同余方程：
$x_{next} = (a \cdot x^2 + b \cdot x + c) \pmod n$ [2]
题目在 data.txt 中提供了模数 $n$ 以及连续生成的4个数值列表 data（设为 $x_1, x_2, x_3, x_4$）[1]。我们可以利用这些已知数值建立方程组：
- $x_2 \equiv a \cdot x_1^2 + b \cdot x_1 + c \pmod n$
- $x_3 \equiv a \cdot x_2^2 + b \cdot x_2 + c \pmod n$
- $x_4 \equiv a \cdot x_3^2 + b \cdot x_3 + c \pmod n$
通过联立方程组（例如两两相减消去 $c$），利用线性代数的方法或高斯消元法在模 $n$ 的有限域下解出参数 $a, b$，最后代回求出 $c$。
2. 逆推初始种子 h
Flux 生成器的初始状态 x 是由 h = shash(value, key) 得到的 [2]。在已知 $a, b, c$ 和第一个输出值 $x_1$ 的情况下，我们需要求解关于初始种子 $h$ 的一元二次方程：
$a \cdot h^2 + b \cdot h + (c – x_1) \equiv 0 \pmod n$
由于 $n$ 是素数（代码中使用 getPrime(260) 生成）[2]，可以使用 Tonelli-Shanks 算法或 SageMath 的 solve_mod 函数求出 $h$ 的值。
3. 破解 Key
题目中提到 h = shash(value, key)，其中 value 是固定字符串 "Welcome to HGAME 2026!"，且 key 的长度小于 70 位 [2]。
shash 函数包含乘法和异或（XOR）的混合运算：
x = (key * x) & mask ^ ord(c) [2]
由于我们已经求出了 h（即 shash 的输出结果），且 key 的位数较短（< 70 bits），我们可以使用 SMT 求解器（如 Z3）来求解 key。将 shash 的逻辑用 Z3 的 BitVec 约束表达出来，设定 key 为未知变量，约束最终计算结果等于步骤2中得到的 h。
4. 生成 Flag
一旦得到了正确的 key，就可以使用代码中给出的最后一步逻辑来获取 Flag：
使用 magic_word = "I get the key now!" 和解出的 key 运行 shash 函数，并将结果转换为十六进制填入格式中 [2]。
总结脚本思路：
- 读取
data.txt获取 $n$ 和 $x_1…x_4$。 - 求解线性方程组得到 $a, b, c$。
- 解二次方程得到 $h$。
- 使用 Z3 求解器根据 $h$ 和明文逆推
key。 - 计算并打印最终 Flag。
from z3 import *
from Crypto.Util.number import inverse
# 1. 加载数据 [1]
data = [259574080588277578527410299002867735023798216356763871244908783144610527451187,
954408432127642232121971189554605898975195279656270435479524132958262607464595,
902461413507524665418054778947872375987908929501605791883614896110219051835312,
92554599789649828855418140915311664257163346975111310560999959858873425332254]
n = 1000081851369905197391900354119969103949357074708517572641608490670646955240669
# 2. 求解 Flux 参数 (a, b, c)
# 建立方程组消元求解
x1, x2, x3, x4 = data
# M * [a, b]^T = R
# (x2 - x3) = a(x1^2 - x2^2) + b(x1 - x2)
# (x3 - x4) = a(x2^2 - x3^2) + b(x2 - x3)
A1 = (x1**2 - x2**2) % n
B1 = (x1 - x2) % n
C1 = (x2 - x3) % n
A2 = (x2**2 - x3**2) % n
B2 = (x2 - x3) % n
C2 = (x3 - x4) % n
# 克拉默法则求解 a, b
det = (A1 * B2 - A2 * B1) % n
det_inv = inverse(det, n)
a = (C1 * B2 - C2 * B1) * det_inv % n
b = (A1 * C2 - A2 * C1) * det_inv % n
c = (x2 - a * x1**2 - b * x1) % n
print(f"[+] Flux Parameters Recovered:\na={a}\nb={b}\nc={c}")
# 3. 求解初始种子 h
# 方程: a*h^2 + b*h + (c - x1) = 0 (mod n)
# 这是一个二次方程，使用 Tonelli-Shanks 算法求解
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
def tonelli(n, p):
if legendre(n, p) != 1: return None
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return pow(n, (p + 4) // 4, p)
for z in range(2, p):
if p - 1 == legendre(z, p):
c = pow(z, q, p)
break
r = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s
while (t - 1) % p != 0:
t2 = (t * t) % p
for i in range(1, m):
if (t2 - 1) % p == 0:
break
t2 = (t2 * t2) % p
b = pow(c, 1 << (m - i - 1), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
return r
# 二次方程求根公式
val = (c - x1) % n
delta = (b**2 - 4*a*val) % n
sqrt_delta = tonelli(delta, n)
if sqrt_delta is None:
print("[-] No solution for h")
exit()
inv_2a = inverse(2 * a, n)
h_candidates = [
(-b + sqrt_delta) * inv_2a % n,
(-b - sqrt_delta) * inv_2a % n
]
print(f"[+] Candidates for h: {h_candidates}")
# 4. 使用 Z3 求解 Key 并计算 Flag
mask = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
def shash_native(value: str, key: int) -> int:
length = len(value)
if length == 0: return 0
x = (ord(value[0]) << 7) & mask
for c in value:
x = (key * x) & mask ^ ord(c)
x ^= length & mask
return x
def solve_key(target_h):
s = Solver()
# key 长度限制为 70 位 [2]
key = BitVec('key', 256)
s.add(key > 0)
s.add(key < (1 << 70))
value = "Welcome to HGAME 2026!"
# 模拟 shash 逻辑
x = (ord(value[0]) << 7) & mask
for char in value:
# Z3 BitVec 乘法会自动处理模 2^256，对应 & mask
x = (key * x) ^ ord(char)
length = len(value)
x = x ^ (length & mask)
s.add(x == target_h)
if s.check() == sat:
return s.model()[key].as_long()
return None
real_key = None
for h in h_candidates:
print(f"[*] Trying to recover key for h = {h}...")
k = solve_key(h)
if k:
real_key = k
print(f"[+] Key found: {real_key}")
break
if real_key:
# 5. 生成 Flag [2]
magic_word = "I get the key now!"
flag_hash = shash_native(magic_word, real_key)
flag = "VIDAR{" + hex(flag_hash)[2:] + "}"
print(f"\n[SUCCESS] FLAG: {flag}")
else:
print("[-] Failed to recover key.")
正文完