LilCTF2025
owo
打这个比赛也学到了蛮多东西，这里仅记录Linear,Space Travel，baaaaaag三道题
Linear
1 | import os |
审一下代码，本题的大概意思就是求解Ax = b这个线性方程组。已知的是一个(16$$32)的矩阵A和(16$$1)的向量b，我们需要求解这个（32$*$1)的向量x。
而且这个特定的解 x 是由较小的整数（1 到 114514）组成的(恶臭的x)
显然这道题要用格去做。首先，将方程变形为 Ax - b = 0，显然我们就得到了这个格的等式，我们首先构造一个矩阵，M = [A | -b]即把-b作为新的一列拼接到A的最右边得到这个增广矩阵。然后我们求这个矩阵的右核。即找到一个向量v满足 M * v = 0这个v向量的格式为v = [x_1, x_2, …, x_32, 1]^T，这是一个33$*$1的列向量。这个核空间的一组基就是我们格的初始基。这个基由 17 个 33 维的向量组成。我们对这个基进行规约然后找到最后一个元素为1的那一个向量。这就是我们要求的x啦。
1 | from pwn import remote |
Space Travel
1 | from Crypto.Cipher import AES |
鸡块的题，经典代码越短题目越难
还是来看看题目大意，首先是做 50 次int.from_bytes(urandom(2)) & 0xfff 产生一个 0到4095 的随机索引。然后取对应的vecs[idx]，顺序拼接50个得到一个800bit的。最后转成十进制数得到key。
然后是🎁和🚩的生成，首先我们来看🎁，生成了600组样本，对于每一组样本，先是urandom(50$*$2)得到100字节，也就是800bit，然后bin(nonce & key).count(“1”)) % 2这一段是计算(nonce & key)中1的个数mod 2.
然后用key的十进制转MD5做密钥加密明文得到🚩
虽然直觉是直接造格打，但是600 800的格好像不太行，遂放弃。不过后来发现了一个奇妙东西-仿射子空间，因为我们知道vecs的是4096个16bits的向量。刚好是2的12次方个，这里我们首先大概了解一下什么是仿射子空间
“仿射子空间”（Affine Subspace）= “线性子空间的一个平移”。 形式： A = b ⊕ L （或写 A = b + L）
- L 是一个线性子空间
- b 是某个固定向量（称为平移向量、偏移、锚点）
- A 中所有元素都可以表示成 b + ℓ，其中 ℓ ∈ L
- 如果 b = 0，那么 A = L，本质上就是线性子空间本身
仿射子空间不要求包含零向量（除非恰好 b ∈ L，使 A = L）。
那么对于本题来说我们可以认为vecs的结构就是一个仿射子空间 b ⊕ L。
我们任取 vecs[0] = b。构造集合 { vecs[i] ⊕ b } 得到纯线性空间 L 的元素。那么这个L的维度应该就是12.
得到 L 的一组基行向量后形成矩阵 G：
把 12 个基行向量转置为列向量 ⇒ G 是 16×12 矩阵。这里的16是因为vecs 里，每个元素是16位二进制字符串。也就是说，每个向量是 16维的 0/1 向量。
然后遍历600条样本，把800bit的nonce分为50个16bit的块 a_{t,j}与key对应
累加 <a_{t,j}, b> 得 K_t；计算 G^T a_{t,j} 填充矩阵行；得到 s’_t = s_t ⊕ K_t。
得到 M(600×600)、S’(600)。到这里，所有 600 条样本都被转化成了一个标准的 GF(2) 线性方程组：M⋅W=S′
其中：
M 是 600×600 的 GF(2) 矩阵，完全由 nonce、仿射空间结构 G 和偏移 b 决定；
W 是 600 维的变量向量（50个w_j拼起来，每个12位）；
S’ 是右侧的常数向量。
这样我们就可以将问题降维为 600 未知 + 600 方程 的线性系统，然后我们计算M的秩，当然理想状态下我们希望他是满秩的，其对应的零空间的维度就为0，这样就能得到一个唯一解。
M 是 600×600 的 GF(2) 系数矩阵
nullity=600−rank(M)
如果 nullity=0：唯一解
如果 nullity=1：所有解是“某个特解 + 1 个方向的线性组合”，即 2 个可能解
如果 nullity=d：共有 2$^{d} $个可能解
这道题我们算出来发现秩是599，也就是说有两个可能解，我们都打印出来看一下就能判断了。为了便于理解让ai生成了一个很详细的脚本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184from Crypto.Cipher import AES
from hashlib import md5
import itertools
import ast # 用于安全地将字符串解析为 Python 对象
# --- 数据加载模块 ---
print("[*] 正在从文件加载数据...")
# 1. 从 params.py 导入 vecs
try:
from params import vecs
print(" - `vecs` 从 params.py 加载成功。")
except ImportError:
print(" - 错误: 无法找到或导入 'params.py'。请确保该文件在同一目录下。")
vecs = [] # 定义一个空列表以避免后续代码崩溃
# 2. 从 output.txt 解析 oracle_data 和 ciphertext
oracle_data = []
ciphertext = b""
try:
with open("output.txt", 'r', encoding='utf-8') as f:
for line in f:
line = line.strip()
if line.startswith("🎁 :"):
# 提取 "🎁 : " 后面的列表字符串
list_str = line[len("🎁 :"):].strip()
oracle_data = ast.literal_eval(list_str)
print(" - `oracle_data` 从 output.txt 解析成功。")
elif line.startswith("🚩 :"):
# 提取 "🚩 : " 后面的字节串字符串
bytes_str = line[len("🚩 :"):].strip()
ciphertext = ast.literal_eval(bytes_str)
print(" - `ciphertext` 从 output.txt 解析成功。")
except FileNotFoundError:
print(" - 错误: 'output.txt' 文件未找到。")
except Exception as e:
print(f" - 错误: 解析 'output.txt' 时发生错误: {e}")
# --- 核心求解逻辑 (与原版基本一致) ---
# 定义 SageMath 域
F = GF(2)
def bits_to_vec(bitstr):
"""将二进制字符串转换为 GF(2) 向量"""
return vector(F, [int(c) for c in bitstr])
def printable_score(bs):
"""计算字节串中可打印 ASCII 字符的比例，用于评估解密结果"""
return sum(32 <= b <= 126 for b in bs) / max(1, len(bs))
def rebuild_key_from_W(W, b, G, BLOCKS=50, AFFINE_DIM=12, VEC_LEN=16):
"""根据 600-bit 的系数向量 W 重建 800-bit 的密钥"""
key_bits_parts = []
for j in range(BLOCKS):
w_j = W[j*AFFINE_DIM:(j+1)*AFFINE_DIM]
v_j = b + G * vector(F, w_j) # 在 GF(2) 中，v_j = b ⊕ (G * w_j)
key_bits_parts.append("".join(map(str, list(v_j))))
key_bitstring = "".join(key_bits_parts)
return key_bitstring
def decrypt_with_key_int(key_int, ciphertext):
"""使用给定的密钥整数解密密文"""
aes_key = md5(str(key_int).encode()).digest()
cipher = AES.new(aes_key, AES.MODE_CTR, nonce=b"Tiffany")
return cipher.decrypt(ciphertext)
def solve():
"""主求解函数"""
# 检查数据是否加载成功
if not vecs or not oracle_data or not ciphertext:
print("\n[!] 错误: 数据加载不完整，无法继续求解。请检查文件是否存在或内容是否正确。")
return
VEC_LEN = 16
BLOCKS = 50
AFFINE_DIM = 12
KEY_LEN = VEC_LEN * BLOCKS # 800
UNKNOWN_BITS = BLOCKS * AFFINE_DIM # 600
print("\n[1] 分析 `vecs` 结构，构造仿射子空间 b ⊕ L...")
vec_vectors = [bits_to_vec(v) for v in vecs]
b = vec_vectors[0]
L_vectors = [v + b for v in vec_vectors] # v - b 在 GF(2) 中就是 v + b
L_space = matrix(F, L_vectors).row_space()
dimL = L_space.dimension()
print(f" - 线性部分 L 的维度: {dimL}")
if dimL != AFFINE_DIM:
print(" - !!! 警告: 维度不等于预期的 12，结果可能不正确。")
return
# 将基行向量转换为列向量，构成矩阵 G
basis_rows = L_space.basis()
G = matrix(F, list(zip(*basis_rows)))
G_T = G.transpose()
print(" - 仿射空间的偏移 b 和基矩阵 G 构建完成。")
print("\n[2] 构建 600x600 的线性方程组 M * W = S'...")
eqn_count = min(600, len(oracle_data))
M_rows = []
S_prime = []
for t in range(eqn_count):
nonce_int, s_t = oracle_data[t]
bits = bin(nonce_int)[2:].zfill(KEY_LEN)
K_t = F(0)
row = vector(F, UNKNOWN_BITS)
for j in range(BLOCKS):
seg = bits[j*VEC_LEN:(j+1)*VEC_LEN]
a = bits_to_vec(seg)
K_t += a.dot_product(b)
coeff_block = G_T * a
row[j*AFFINE_DIM:(j+1)*AFFINE_DIM] = coeff_block
S_prime.append(F(s_t) + K_t)
M_rows.append(row)
M = matrix(F, M_rows)
S_vec = vector(F, S_prime)
rk = M.rank()
nullity = UNKNOWN_BITS - rk
print(f" - 矩阵 M: {M.nrows()}x{M.ncols()}, 秩(rank)={rk}, 零度(nullity)={nullity}")
print("\n[3] 求解特解 W0 和零空间...")
try:
W0 = M.solve_right(S_vec)
except Exception as e:
print(f" - solve_right 失败，尝试 solution_space: {e}")
sol_space = M.solution_space(S_vec)
W0 = sol_space.representative()
print(" - 已获得一个特解 W0。")
kernel = M.right_kernel()
basis = kernel.basis()
print(f" - 零空间维度为 {len(basis)}。")
if nullity > 15:
print(" - 零空间维度过大 (2^{}), 无法暴力枚举。".format(nullity))
return
print(f"\n[4] 枚举 {2**nullity} 个候选解...")
candidates = []
if nullity == 0:
candidates.append(W0)
else:
for mask in range(1 << nullity):
W = W0
for i, vec in enumerate(basis):
if (mask >> i) & 1:
W = W + vec
candidates.append(W)
print("\n[5] 尝试解密并为候选解评分...")
scored = []
for idx, W in enumerate(candidates):
key_bits = rebuild_key_from_W(W, b, G, BLOCKS, AFFINE_DIM, VEC_LEN)
key_int = int(key_bits, 2)
pt = decrypt_with_key_int(key_int, ciphertext)
score = printable_score(pt)
heuristic = 0
low = pt.lower()
if b'flag{' in low or b'ctf{' in low or b'flag[' in low: heuristic += 5
if score > 0.85: heuristic += 1
scored.append((heuristic, score, idx, key_int, pt))
scored.sort(reverse=True)
print("\n[6] 评分最高的候选结果:")
show_k = min(5, len(scored))
for h, sc, idx, key_int, pt in scored[:show_k]:
snippet = ''.join(chr(b) if 32 <= b <= 126 else '.' for b in pt[:60])
print(f" - 候选#{idx}: 启发分={h}, 可打印分={sc:.3f}, 片段='{snippet}'")
best = scored[0]
h, sc, idx, key_int, pt = best
print(f"\n[+] 选定最优候选: cand#{idx} (启发分={h}, 可打印分={sc:.3f})")
print("[+] 解密得到的 Flag:")
try:
print(pt.decode())
except Exception as e:
print(f"(解码失败: {e}) -> 原始字节: {pt}")
print("\n[7] 校验前 5 条 oracle:")
for i in range(min(5, len(oracle_data))):
nonce_int, sbit = oracle_data[i]
calc = bin(nonce_int & key_int).count("1") & 1
print(f" - 样本#{i}: 题目给出={sbit}, 计算得到={calc} -> {'OK' if calc==sbit else '不匹配'}")
# 运行主函数
solve()
baaaaaag
一个背包密码，用bkz调一下blocksize就能出不过好像是非预期哈哈哈
为了方便理解博客上的脚本还是用ai注释详细的
1 | from sageall import * |