Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

Archer's blog

Blog

Categories

Tags

Archievs

Friends

About

LakeCTF Quals 25-26 Writeup

CTF比赛Writeup

LWE

sage

writeup

lattice

numpy

Last UpdatedDec 12, 2025

次浏览

Crypto

Guess Flag

题目

image-20251129224448956

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
#!/usr/bin/env -S python3 -u
flag = "00000000000000000000000000000000"

print("Don't even think to guess the flag by brute force, it is 32 digits long!")

user_input = input()



if not user_input.isdigit():
    print("Flag only contains digits!")
    exit()



index = 0

for char in user_input:
    if char != flag[index]:
        print("Wrong flag!")
        exit()
    index += 1

print("Correct flag!")

print("flag is : EPFL{" +user_input + "}")

分析

可以发现程序只会检查我们给的内容是否为flag的前缀，只要是就会返回Correct：

1
2
3
4
5
6
for char in user_input:
    if char != flag[index]:
        print("Wrong flag!")
        exit()
    index += 1
print("Correct flag!")

所以本质上就是一个Oracle的题，我们只需要一位一位爆破就好。

代码

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
from pwn import *
import string

host = 'chall.polygl0ts.ch'
port = 6001
context.log_level = 'error'

known_flag = ""
charset = string.digits

# flag is 32 digits long
for i in range(32):
    found_char = False
    
    for char in charset:
        r = remote(host, port)
        
        test_payload = known_flag + char
        
        r.sendlineafter(b"digits long!", test_payload.encode())
        
        response = r.recvall(timeout=2).decode()
        
        if "Correct flag!" in response:
            known_flag += char
            print(f"index : {i}, current flag: {known_flag}")
            found_char = True
            r.close()
            break
        
        r.close()
    
    if not found_char:
        break

print(f"Flag: EPFL{{{known_flag}}}")


# index : 0, current flag: 1
# index : 1, current flag: 15
# index : 2, current flag: 153
# index : 3, current flag: 1539
# index : 4, current flag: 15392
# index : 5, current flag: 153929
# index : 6, current flag: 1539294
# index : 7, current flag: 15392948
# index : 8, current flag: 153929482
# index : 9, current flag: 1539294829
# index : 10, current flag: 15392948299
# index : 11, current flag: 153929482999
# index : 12, current flag: 1539294829992
# index : 13, current flag: 15392948299929
# index : 14, current flag: 153929482999293
# index : 15, current flag: 1539294829992932
# index : 16, current flag: 15392948299929328
# index : 17, current flag: 153929482999293283
# index : 18, current flag: 1539294829992932838
# index : 19, current flag: 15392948299929328383
# index : 20, current flag: 153929482999293283838
# index : 21, current flag: 1539294829992932838382
# index : 22, current flag: 15392948299929328383828
# index : 23, current flag: 153929482999293283838283
# index : 24, current flag: 1539294829992932838382839
# index : 25, current flag: 15392948299929328383828399
# index : 26, current flag: 153929482999293283838283999
# index : 27, current flag: 1539294829992932838382839992
# index : 28, current flag: 15392948299929328383828399923
# index : 29, current flag: 153929482999293283838283999239
# index : 30, current flag: 1539294829992932838382839992399
# index : 31, current flag: 15392948299929328383828399923990
# Flag: EPFL{15392948299929328383828399923990}

The Phantom Menace

题目

image-20251129224539229

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
import numpy as np
import json

try:
    from flag import flag
except:
    flag = "redacted_this_is_just_so_that_it_works_and_you_can_test_locally."

m_b = np.array([int(c) for char in flag for c in format(ord(char), '08b')])

# Parameters
q = 3329
n = 512
k = 4
f = np.array([1] + [0]*(n-1) + [1])

assert len(m_b)==n

# ---------- Helper functions ----------
def _small_noise(n, weight=2):
    coeffs = np.zeros(n, dtype=int)
    idx = np.random.choice(n, size=weight, replace=False)
    signs = np.random.choice([-1, 1], size=weight)
    coeffs[idx] = signs
    return coeffs

def _vec_poly_mul(v0, v1):
    def _poly_mul(a, b):
        res = np.convolve(a, b)
        for i in range(n, len(res)):
            res[i - n] = (res[i - n] - res[i]) % q 
        return res[:n] % q
    return sum((_poly_mul(a, b) for a, b in zip(v0, v1))) % q

def encrypt(A, t, m_b, r, e_1, e_2):
    A_T = list(map(list, zip(*A)))
    u = np.array([(mat + err) % q for mat, err in 
         zip([_vec_poly_mul(row, r) for row in A_T], e_1)
         ])
    tr = _vec_poly_mul(t, r)
    m = (m_b * ((q + 1)//2)) % q
    v = (tr + e_2 + m) % q
    return u, v

# ---------- Key generation ----------
A = np.array([np.array([np.random.randint(0, q, n) for _ in range(k)]) for _ in range(k)])
s = np.array([_small_noise(n, n*2//3) for _ in range(k)])
e = np.array([_small_noise(n) for _ in range(k)])
t = np.array([(_vec_poly_mul(row, s) + err) % q for row, err in zip(A, e)])

# ---------- Encryption -------------
r = [_small_noise(n) for _ in range(k)]
e_1 = [_small_noise(n) for _ in range(k)]
e_2 = _small_noise(n)

u, v = encrypt(A, t, m_b, r, e_1, e_2)

# ---------- Saving key ---------------
keys = {
    "s":s.tolist(),
    "u":u.tolist(),
    "v":v.tolist()
}

with open("keys.json", "w") as f:
    f.write(json.dumps(keys))

分析

这道题是关于LWE (Learning With Errors)的，所有的运算都是在多项式环$R_q = \mathbb{Z}_q[x] / (x^n + 1)$ 里的运算。

我们先来看一下具体的加密流程：

  1. 生成密钥：

    • 生成一个随机的$k \times k$（这道题里是$k=4$）矩阵$A$，公钥。

    • 生成一个随机小系数（-1, 0, 1之类的）向量$s$，私钥

    • 计算公钥t：

      这里 $e$ 是一个误差向量(Error)，也是系数非常小的随机多项式。

  2. 加密：

    • 消息编码：

      将二进制消息转换成多项式$m$。需要尽量将0和1区分开。

      • 如果是0：编码为系数$0$。
      • 如果是1：编码为系数$\lceil q/2 \rceil \approx 1665$。

    • 生成一个一次性的小系数的随机向量 $r, e_1, e_2$。

    • 计算密文$u$ ：

    • 计算密文$v$：

因为这道题直接把密钥s也给我们了，所以我们直接考虑正常情况下该怎么解密就好。

注意到：

由于多余的部分$e^T r + e_2 - s^T e_1$是我们有意生成的系数很小的噪音向量，所以可以很轻易地还原明文$m$。

代码

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
import json
import numpy as np

q = 3329
n = 512

with open("keys.json", "r") as f:
        data = json.load(f)
        

s = np.array(data['s'])  # 私钥
u = np.array(data['u'])
v = np.array(data['v'])


# 直接从题里复制过来
def _vec_poly_mul(v0, v1):
    def _poly_mul(a, b):
        res = np.convolve(a, b)
        for i in range(n, len(res)):
            res[i - n] = (res[i - n] - res[i]) % q 
        return res[:n] % q
    return sum((_poly_mul(a, b) for a, b in zip(v0, v1))) % q


# v - (s * u)
s_dot_u = _vec_poly_mul(s, u)

message_poly = (v - s_dot_u) % q


# 将多项式系数解码为二进制位
bits = []
# 原始加密逻辑: 1 被缩放为 ~q/2 (约1664), 0 被缩放为 0
# 使用 q/4 和 3q/4 作为阈值来判断
lower_bound = q // 4
upper_bound = 3 * q // 4

for coeff in message_poly:
    if lower_bound < coeff < upper_bound:
        bits.append(1)
    else:
        bits.append(0)

flag = ""

for i in range(0, len(bits), 8):
    byte = bits[i:i+8]
    if len(byte) < 8:
        break
    
    # 将 [0, 1, 1, 0...] 列表转为字符串 "0110..." 再转为整数
    char_code = int("".join(map(str, byte)), 2)
    flag += chr(char_code)

print("flag:", flag)

# EPFL{y0u_w3r3_r1ght_m4a5t3r_th3_n3g0t14t410n5_w3r3_5h0rt_ot3zhe}

Revenge of the Sith

题目

image-20251129224638010

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
import numpy as np
import json

# message
try:
    from flag import flag
except:
    flag = "redacted_this_is_just_so_that_it_works_and_you_can_test_locally."

m_process = [int(c) for char in flag for c in format(ord(char), '08b')]

# Parameters
q = 251
n = 16
k = 2
f = np.array([1] + [0]*(n-1) + [1])

m_b = np.array([m_process[i:i+16] for i in range(0, len(m_process), n)])

assert len(m_b[0])%n == 0
batch_size = m_b.shape[0]

# ---------- Helper functions ----------
def _small_noise(n, weight=2):
    coeffs = np.zeros(n, dtype=int)
    idx = np.random.choice(n, size=weight, replace=False)
    signs = np.random.choice([-1, 1], size=weight)
    coeffs[idx] = signs
    return coeffs

def _vec_poly_mul(v0, v1):
    def _poly_mul(a, b):
        res = np.convolve(a, b)
        for i in range(n, len(res)):
            res[i - n] = (res[i - n] - res[i]) % q 
        return res[:n] % q    
    return sum((_poly_mul(a, b) for a, b in zip(v0, v1))) % q

def encrypt(A, t, m_b_batch, r_batch, e_1_batch, e_2_batch):
    A_T = list(map(list, zip(*A)))    
    u_list = []
    v_list = []
    for b in range(batch_size):
        r = r_batch[b]
        e_1 = e_1_batch[b]
        e_2 = e_2_batch[b]
        m_b = m_b_batch[b]        
        u = np.array([(mat + err) % q for mat, err in 
             zip([_vec_poly_mul(row, r) for row in A_T], e_1)
             ])
        tr = _vec_poly_mul(t, r)

        m = (m_b * ((q + 1)//2)) % q
        
        v = (tr + e_2 + m) % q
        
        u_list.append(u)
        v_list.append(v)
        
    return np.array(u_list), np.array(v_list)

# ---------- Key generation ----------
A = np.array([np.array([np.random.randint(0, q, n) for _ in range(k)]) for _ in range(k)])
s = np.array([_small_noise(n, n//2) for _ in range(k)])
e = np.array([_small_noise(n) for _ in range(k)])
t = np.array([(_vec_poly_mul(row, s) + err) % q for row, err in zip(A, e)])

# ---------- Encryption ----------
r_batch = np.array([[_small_noise(n) for _ in range(k)] for _ in range(batch_size)])
e_1_batch = np.array([[_small_noise(n) for _ in range(k)] for _ in range(batch_size)])
e_2_batch = np.array([_small_noise(n) for _ in range(batch_size)])

u, v = encrypt(A, t, m_b, r_batch, e_1_batch, e_2_batch)

# ---------- Saving key ---------------
keys = {
    "A": A.tolist(),
    "t": t.tolist(),
    "u": u.tolist(),
    "v": v.tolist()
}

with open("keys.json", "w") as f:
    f.write(json.dumps(keys))

分析

这道题也是LWE。只不过这次没有再给我们密钥了。

加密的流程和上一题是一样的：

由于参数$n, q, s, e$都很小，我们可以通过构造格来求出$s$。

注意到：

我们可以考虑这样的矩阵构造：

定义$k’:=-k$，则有：

（可以这样一步一步构造出来这个矩阵：

  1. 因为一定要把$A,t$塞进矩阵里（因为这是唯二和$s$真正相关的信息了），所以直接把上面那个式子都塞进矩阵，也就是说第一列里会有$q, A, t$。
  2. 从第一列推出来左乘的这个向量为$(k’, \ s, \ 1)$
  3. 因为我们最终的目的是求这个$s$，所以它一定需要出现在右边的目标向量里，所以矩阵的第二列就中间部分有一个单位矩阵$I$
  4. 最后因为没有什么额外的信息了，并且我们需要确保目标向量的norm尽量小，所以直接选1即可。

）

由于$s, e$都很小，所以用LLL大概率可以得到这个这个向量，从而得到$s$。得到$s$了之后就可以用上一题提到的方法求得明文了。

顺带一提，LLL算法旨在找到格的一组“几乎正交”的基，其中第一个基向量通常就是格里的最短向量（或近似最短）。LLL 是一个近似算法（Approximation Algorithm）。它不保证找到真正的最短向量（SVP），它只保证找到一个“相对短”的向量。LLL 输出的最短向量 $v_{LLL}$ 与真正的最短向量 $v_{shortest}$ 之间满足：

如果维度稍微大一点（比如 $n=120$），或者噪声 $e$ 稍微大一点，LLL 可能就找不到私钥了。这时候我们需要用更强的算法：BKZ (Block-Korkin-Zolotarev)：

BKZ是LLL的升级版。它不再一次性处理整个矩阵，而是把矩阵分成小块（Block），在每个小块里做穷举搜索（SVP）。

代码

用sage写的，因为需要用到LLL：

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
import json

q = 251
n = 16
k = 2

# ================= 辅助函数 =================
# 将多项式系数列表转换为负循环矩阵 (Negacyclic Matrix)
# 对应模 x^16 + 1 的乘法
def make_negacyclic_matrix(coeffs):
    mat = []
    # 填充第一列
    col = list(coeffs) + [0] * (n - len(coeffs))
    
    # 生成后续列
    current = col[:]
    cols = [current[:]]
    for _ in range(n - 1):
        # 旋转并取反: [c0, c1, ... c15] -> [-c15, c0, ... c14]
        last = current.pop()
        current.insert(0, -last)
        cols.append(current[:])
    
    # Sage中的Matrix是行向量形式，所以我们需要构造后再转置，
    # 或者直接按行构造。这里按列构造比较直观，最后转置。
    return matrix(ZZ, cols).transpose()



def solve():
    with open("keys.json", "r") as f:
        data = json.load(f)
    
    A_raw = data['A']
    t_raw = data['t']
    u_list = data['u']
    v_list = data['v']

    # 1. 构造大矩阵 A_big 和目标向量 t_vec
    # A_big 的结构: [[M(A00), M(A01)], [M(A10), M(A11)]]
    # 维度: (2*16) x (2*16) = 32 x 32
    blocks = []
    for r in range(k):
        row_blocks = []
        for c in range(k):
            row_blocks.append(make_negacyclic_matrix(A_raw[r][c]))
        blocks.append(row_blocks)
    A_big = block_matrix(blocks)

    # t_vec: 展平 t
    t_vec = []
    for poly in t_raw:
        t_vec.extend(poly)
    t_vec = vector(ZZ, t_vec)

    print("[-] Constructing Lattice...")
    # 2. 构造格基矩阵 L
    # 维度: 65 x 65
    # 结构:
    # [ qI   0   0 ]
    # [ A^T  I   0 ]
    # [ -t   0   1 ]
    
    dim_target = k * n # 32
    dim_secret = k * n # 32
    
    # 构造各部分
    M_q = q * identity_matrix(dim_target)
    M_zero_1 = zero_matrix(dim_target, dim_secret)
    M_zero_2 = zero_matrix(dim_target, 1)
    
    M_A = A_big.transpose() 
    M_I = identity_matrix(dim_secret)
    M_zero_3 = zero_matrix(dim_secret, 1)
    
    M_t = matrix(ZZ, -t_vec) # 1 x 32
    M_zero_4 = zero_matrix(1, dim_secret)
    M_one = matrix(ZZ, [1])
    
    # 拼合矩阵
    L = block_matrix([
        [M_q, M_zero_1, M_zero_2],
        [M_A, M_I,      M_zero_3],
        [M_t, M_zero_4, M_one]
    ])
    
    print("[-] Running LLL algorithm (this might take a second)...")
    L_reduced = L.LLL()
    
    # 3. 寻找短向量并恢复私钥 s
    # 理论上最短的非零向量应该是 (-e, s, 1) 或者其相反数
    # 我们检查最后一列是否为 1 或 -1
    
    s_recovered = None
    for row in L_reduced:
        if row[-1] == 1:
            # 向量格式可能是 (-e, s, 1)
            # s 位于中间的 32 位 (索引 32 到 63)
            s_vec = row[dim_target : dim_target + dim_secret]
            s_recovered = s_vec
            break
        elif row[-1] == -1:
            # 向量是 (e, -s, -1)，取反
            s_vec = -row[dim_target : dim_target + dim_secret]
            s_recovered = s_vec
            break
            
    if s_recovered is None:
        print("Failed to recover key.")
        return

    print(f"Secret key found!")
    
    s_polys = []
    for i in range(k):
        poly = list(s_recovered[i*n : (i+1)*n])
        s_polys.append(poly)

    
    # 定义多项式乘法 (模 x^16 + 1, 模 q)
    def poly_mul(p1, p2):
        res = [0] * (2 * n)
        for i, c1 in enumerate(p1):
            for j, c2 in enumerate(p2):
                res[i+j] += c1 * c2
        
        # 模 x^16 + 1 归约
        # x^16 = -1, x^17 = -x ...
        final = [0] * n
        for i in range(len(res)):
            if i < n:
                final[i] = (final[i] + res[i])
            else:
                final[i - n] = (final[i - n] - res[i])
        
        return [x % q for x in final]

    # 定义向量点积
    def vec_dot(v1_polys, v2_polys):
        sum_poly = [0] * n
        for p1, p2 in zip(v1_polys, v2_polys):
            prod = poly_mul(p1, p2)
            for i in range(n):
                sum_poly[i] = (sum_poly[i] + prod[i]) % q
        return sum_poly

    flag_bits = ""
    
    # 遍历每个密文块
    for i in range(len(u_list)):
        u_block = u_list[i]
        v_poly = v_list[i]
        
        shared_secret = vec_dot(s_polys, u_block)
        
        # v - s^T * u
        # 结果应该是 m * (q//2) + error
        noisy_m = [(v_val - s_val) % q for v_val, s_val in zip(v_poly, shared_secret)]
        
        # Phase 3: 解码 (判断距离 0 近还是 q/2 近)
        center = q // 2
        for val in noisy_m:
            dist_0 = min(val, q - val)
            dist_center = abs(val - center)
            
            if dist_0 < dist_center:
                flag_bits += "0"
            else:
                flag_bits += "1"
                
    flag = ""
    try:
        for i in range(0, len(flag_bits), 8):
            byte = flag_bits[i:i+8]
            if len(byte) == 8:
                flag += chr(int(byte, 2))
        print(f"Flag: {flag}")
    except Exception as e:
        print(f"Decoding error: {e}")

solve()

# EPFL{N07_0N1Y_7H3_m3n_BU7_7h3_w0M3N_4ND_CHILDR3N_7o0_T50nanWvW1}

Quantum vernam

题目

image-20251129224659370

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
#!/usr/bin/env -S python3 -u
import os
import numpy as np
from math import sqrt
# no need quantum libraries here, only linear algebra. 
from scipy.stats import unitary_group



def string_to_bits(s): 
    bits = []
    for byte in s:
        for i in range(8):
            bits.append((byte >> (7 - i)) & 1)
    return bits

def bit_to_qubit(bit):
    if bit == 0:
        return np.array([1,0])  # |0>
    else:
        return np.array([0, 1]) # |1>

def encryption(key, message,gate1,gate2,x):
    key_bits = string_to_bits(key)
    message_bits = string_to_bits(message)
    cipher = []
    


    encryption_matrix = np.array([])
    PauliX = np.array([(0,1), (1,0)])
    PauliZ = np.array([(1,0), (0,-1)])

    for k, m in zip(key_bits, message_bits):
        qubit = bit_to_qubit(m)
        qubit = gate1 @ qubit

        if k == 1:
            qubit =  x @ qubit

        qubit = gate2 @ qubit
        cipher.append(qubit)
    return cipher

def measurement(cipher):
    measured_bits = []
    for qubit in cipher:
        prob_0 = qubit[0]*qubit[0].conjugate()

        if np.random.rand() < prob_0:
            measured_bits.append(0)
        else:
            measured_bits.append(1)
    return measured_bits

def bits_to_string(bits):
    bytes_list = []
    for i in range(0, len(bits), 8):
        byte = 0
        for j in range(8):
            byte = (byte << 1) | bits[i + j]
        bytes_list.append(byte)
    return bytes(bytes_list)
    
####################################################################################


FLAG = b"EPFL{FAKEFLAAAAAAAG}}"
n = len(FLAG)
key = os.urandom(n)
x = unitary_group.rvs(2)


print("Welcome to the Quantum Vernam Cipher Encryption! Key and flag have same length, try to break perfect secrecy if you can.")
print("\n")
print('The qubits will be encrypted with the matrix x = ',x)
print("\n")
print("You can apply any gate you want to the qubits before and after measurement as a 2X2 matrix, choose your favorite one :)")
print("\n")
print("Also pls remember that in python, j is the imaginary unit, not i.")
print('\n')
print('Enter coefficients for the first matrix that will be applied BEFORE encryption:')
print('Enter first matrix element:') 
a1 = complex(input())
print('Enter second matrix element:')
b1 = complex(input())
print('Enter third matrix element:')
c1 = complex(input())
print('Enter fourth matrix element:')
d1 = complex(input())

gate1 = np.array([(a1,b1),(c1,d1)])



print('\n')
print('Enter coefficients for the second matrix that will be applied AFTER encryption:')
print('Enter first matrix element:') 
a2 = complex(input())
print('Enter second matrix element:')
b2 = complex(input())
print('Enter third matrix element:')
c2 = complex(input())
print('Enter fourth matrix element:')
d2 = complex(input())

gate2 = np.array([(a2,b2),(c2,d2)])



# vérifie que les matrices sont unitaires
def is_unitary(matrix):
    identity = np.eye(matrix.shape[0])
    return np.allclose(matrix.conj().T @ matrix, identity)


    
assert is_unitary(gate1), "Gate 1 is not unitary!"  
assert is_unitary(gate2), "Gate 2 is not unitary!"


cipher = encryption(key, FLAG,gate1,gate2,x)
measurement_result = measurement(cipher)


print("measurement:", measurement_result)
print(bits_to_string(measurement_result))

分析

这道题算是模拟了一个单量子比特的传输过程。

1
2
3
4
5
def bit_to_qubit(bit):
    if bit == 0:
        return np.array([1,0])  # |0>
    else:
        return np.array([0, 1]) # |1>

就是把普通的0和1转成了量子计算里的比特$|0\rangle$和$|1\rangle$（用矩阵表示的）。

1
x = unitary_group.rvs(2)

并且生成了一个$2 \times 2$的随机的unitary矩阵。

然后来看加密的部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def encryption(key, message,gate1,gate2,x):
    key_bits = string_to_bits(key)
    message_bits = string_to_bits(message)
    cipher = []
    
    for k, m in zip(key_bits, message_bits):
        qubit = bit_to_qubit(m)
        qubit = gate1 @ qubit

        if k == 1:
            qubit =  x @ qubit
		# 如果 k == 0就什么都不做，相当于乘单位矩阵I
        
        qubit = gate2 @ qubit
        cipher.append(qubit)
    return cipher

对于每一个比特$m$和密钥位 $k$，最终生成的向量$|\psi_{final}\rangle$为：

其中$X^k$指的是：

因为$k$是随机的，所以$X^k$也是随机的。不过$G_1, G_2$都是我们给的，可以自由选择。

测量部分：

1
2
3
4
5
6
7
8
9
10
def measurement(cipher):
    measured_bits = []
    for qubit in cipher:
        prob_0 = qubit[0] * qubit[0].conjugate()

        if np.random.rand() < prob_0:
            measured_bits.append(0)
        else:
            measured_bits.append(1)
    return measured_bits

同样模拟的是量子计算里的测量方法：假设最终向量是 $|\psi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$，那么

  • 测量得到0的概率是 $|\alpha|^2$。
  • 测量得到1的概率是 $|\beta|^2$。
  • 且 $|\alpha|^2 + |\beta|^2 = 1$。

而我们最终从服务器得到的内容就是加密步骤里的$|\psi_{final}\rangle$的测量结果。

所以为了能够”还原“原本的flag，我们只能构造特殊的$G_1, G_2$，使得最后的$|\psi_{final}\rangle$等于原本的$m$，或者严格来讲只要等于$\lambda \cdot m$即可。这样一来最后的测量结果也就等于原本的flag了。

那么最后剩下的就是纯线性代数的问题了。

因为$X$是unitary的，所以可以很轻易的将其对角化，也就是说设$V$是由$X$的特征向量组成的矩阵，那么就有：

其中$D = diag(\lambda_1, \lambda_2)$（X的特征值），并且$V^{-1} = V^H$。（共轭转置）

这样一来就有

由于$X$是unitary的，所以它的特征值的norm都等于1。所以依旧可以满足

不会影响到最后的测量。

代码

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
from pwn import *
import numpy as np
import re

# context.log_level = "debug"
r = remote('chall.polygl0ts.ch', 6002)

# 简单处理一下接收到的X
r.recvuntil(b'x =  ')
x_str = r.recvuntil(b'\n\n').decode().strip()

clean_str = x_str.replace('[', '').replace(']', '').replace('\n', ' ')
elements = clean_str.split()

matrix_elements = []
for el in elements:
    if el:
        matrix_elements.append(complex(el))
        
X = np.array(matrix_elements).reshape(2, 2)
print(f"Matrix X:\n{X}")

# 计算特征值和特征向量
# w 是特征值, v 是特征向量矩阵
w, v = np.linalg.eig(X)

# Gate 1 就是特征向量矩阵
G1 = v
# Gate 2 是 Gate 1 的逆矩阵 (对于酉矩阵，即共轭转置)
G2 = np.linalg.inv(G1)

print(f"[*] Calculated G1 (Eigenvectors):\n{G1}")
print(f"[*] Calculated G2 (Inverse):\n{G2}")

# 发送 Gate 1
# 分别输入 a1, b1, c1, d1
# 对应矩阵 [[a, b], [c, d]]

r.sendlineafter(b'first matrix element:', str(G1[0, 0]).encode())   # a1

r.sendlineafter(b'second matrix element:', str(G1[0, 1]).encode())  # b1

r.sendlineafter(b'third matrix element:', str(G1[1, 0]).encode())  # c1

r.sendlineafter(b'fourth matrix element:', str(G1[1, 1]).encode())  # d1


# 发送 Gate 2

r.sendlineafter(b'first matrix element:', str(G2[0, 0]).encode())   # a2

r.sendlineafter(b'second matrix element:', str(G2[0, 1]).encode())  # b2

r.sendlineafter(b'third matrix element:', str(G2[1, 0]).encode())  # c2

r.sendlineafter(b'fourth matrix element:', str(G2[1, 1]).encode())  # d2


r.recvuntil(b'measurement:')
result = r.recvall().decode()
print(result)


# EPFL{URE_3ITH3R_QU4NTUM_BOSSssss_OR_LINALG_BOSS}

Attack of the Clones

题目

image-20251129224721204

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
import numpy as np
import json

try:
    from flag import flag
except: 
    flag = "redacted_this_is_just_so_that_it_works_and_you_can_test_locally."

m_b = np.array([int(c) for char in flag for c in format(ord(char), '08b')])

# Parameters
q = 3329
n = 512
k = 4
f = np.array([1] + [0]*(n-1) + [1])

assert len(m_b)==n

# ---------- Helper functions ----------
def _small_noise(n, weight=2):
    coeffs = np.zeros(n, dtype=int)
    idx = np.random.choice(n, size=weight, replace=False)
    signs = np.random.choice([-1, 1], size=weight)
    coeffs[idx] = signs
    return coeffs

def _vec_poly_mul(v0, v1):
    def _poly_mul(a, b):
        res = np.convolve(a, b)
        for i in range(n, len(res)):
            res[i - n] = (res[i - n] - res[i]) % q 
        return res[:n] % q
    return sum((_poly_mul(a, b) for a, b in zip(v0, v1))) % q

def encrypt(A, t, m_b, r, e_1, e_2):
    u = np.array([(mat + err) % q for mat, err in 
         zip([_vec_poly_mul(row, r) for row in A.T], e_1)
         ])
    tr = _vec_poly_mul(t, r)
    m = (m_b * ((q + 1)//2)) % q
    v = (tr + e_2 + m) % q
    return u, v

# ---------- Key generation ----------
A_1 = np.array([np.array([np.random.randint(0, q, n) for _ in range(k)]) for _ in range(k)])
A_2 = np.array([np.array([np.random.randint(0, q, n) for _ in range(k)]) for _ in range(k)])
s_1 = np.array([_small_noise(n, n*2//3) for _ in range(k)])
s_2 = np.array([_small_noise(n, n*2//3) for _ in range(k)])
e = np.array([_small_noise(n) for _ in range(k)])
t_1 = np.array([(_vec_poly_mul(row, s_1) + err) % q for row, err in zip(A_1, e)])
t_2 = np.array([(_vec_poly_mul(row, s_2) + err) % q for row, err in zip(A_2, e)])

# ---------- Encryption ----------
r = [_small_noise(n) for _ in range(k)]
e_1 = [_small_noise(n) for _ in range(k)]
e_2 = _small_noise(n)

u_1, v_1 = encrypt(A_1, t_1, m_b, r, e_1, e_2)
u_2, v_2 = encrypt(A_2, t_2, m_b, r, e_1, e_2)

# ---------- Giving keys to user ---------------

keys = {
    "A_1" : A_1.tolist(),
    "t_1" : t_1.tolist(),
    "A_2" : A_2.tolist(),
    "t_2" : t_2.tolist(),
    "u_1" : u_1.tolist(),
    "u_2" : u_2.tolist(),
    "v_1" : v_1.tolist(),
    "v_2" : v_2.tolist() 
}

with open("keys.json", "w") as f:
    f.write(json.dumps(keys))

分析

这道题又是LWE。

加密的流程和之前的基本上一样，但是注意这里：

1
2
3
4
5
6
r = [_small_noise(n) for _ in range(k)]
e_1 = [_small_noise(n) for _ in range(k)]
e_2 = _small_noise(n)

u_1, v_1 = encrypt(A_1, t_1, m_b, r, e_1, e_2)
u_2, v_2 = encrypt(A_2, t_2, m_b, r, e_1, e_2)

2次加密用了相同的$r,e_1, e_2$。

也就是说我们现在有：

(1)减(3)就会得到：

因为$u_1,u_2,A_1,A_2$都是已知的，所以我们可以直接得到$r$。从而得到

并且由于$e_2$是系数很小的噪音向量，我们可以很轻松地还原明文。

代码

这道题的思路很简单，但是数据处理有亿点点麻烦（各种数据类型的转换）。

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
import json

n = 512
q = 3329
k = 4

F = GF(q)

def get_negacyclic_matrix(coeffs):
    """
    创建多项式的负循环矩阵。
    如果系数少于 n，则填充 0。
    """
    c = list(coeffs)
    if len(c) < n:
        c = c + [0]*(n - len(c))
    
    M = Matrix(F, n, n)
    current = vector(F, c)
    for i in range(n):
        M.set_column(i, current)
        # 计算下一列：右移，溢出部分取反移到头部
        last = current[n-1]
        current = vector(F, [-last] + list(current[:-1]))
    return M

print("[*] Loading data...")
with open("keys.json", "r") as f:
    data = json.load(f)

A1_data = data["A_1"]
A2_data = data["A_2"]
u1_data = data["u_1"]
u2_data = data["u_2"]
t1_data = data["t_1"]
v1_data = data["v_1"]

# 1. 构建线性方程组 M * r = b
# 方程来源: (u1[i] - u2[i]) = Sum_j ( P_A1_ij - P_A2_ij ) * r[j]
# 其中 P_A_ij 是由切片 A[0..3][j][i] 构成的“小”多项式

print("[*] Building the large linear system (2048x2048)...")
M_big = Matrix(F, k*n, k*n)
b_big = vector(F, k*n)

# 构建目标向量 b = u1 - u2
# 只需要前 k=4 个多项式 (因为 encrypt 只输出了前4个)
for i in range(k):
    poly_diff = vector(F, u1_data[i]) - vector(F, u2_data[i])
    for j in range(n):
        b_big[i*n + j] = poly_diff[j]

# 构建大矩阵 M
# i 是方程组的行块索引 (对应 u 的下标)
# j 是方程组的列块索引 (对应 r 的下标)
for i in range(k): 
    for j in range(k): 
        
        # 提取切片数据: A[x][j][i] for x in 0..3
        # 这对应于 keys.json 中的 A_1[x][j][i]
        # 注意: JSON 中的 A 是 list[row][col][coeff]
        slice1 = [A1_data[x][j][i] for x in range(k)]
        slice2 = [A2_data[x][j][i] for x in range(k)]
        
        poly1 = vector(F, slice1)
        poly2 = vector(F, slice2)
        diff_poly = poly1 - poly2
        
        # 将这个小多项式转换为 n*n 的负循环矩阵块
        block = get_negacyclic_matrix(list(diff_poly))
        M_big.set_block(i*n, j*n, block)

# 2. 求解 r
print("[*] Solving linear system...")
try:
    # M_big * r_vec = b_big
    r_solution_vec = M_big.solve_right(b_big)
    print("[+] System solved!")
except ValueError:
    print("[-] System is inconsistent or singular.")
    exit()

# 将解向量重组为多项式列表
r_polys = []
for i in range(k):
    r_polys.append(r_solution_vec[i*n : (i+1)*n])

# 3. 解密
# v1 = t1 . r + e2 + m
# m_approx = v1 - t1 . r
print("[*] Decrypting...")

# 计算点积 t1 . r
dot_product = vector(F, n)
for i in range(k):
    # t1 和 r 都是正常长度的多项式，正常相乘
    M_t = get_negacyclic_matrix(t1_data[i])
    r_vec = vector(F, r_polys[i])
    dot_product += M_t * r_vec

# 计算带噪声的明文
v1_vec = vector(F, v1_data)
# 确保 v1 长度对齐
if len(v1_vec) < n:
    v1_vec = vector(F, list(v1_vec) + [0]*(n-len(v1_vec)))

m_noisy = v1_vec - dot_product

# 4. 解码比特
flag_bits = ""
scale = (q + 1) // 2

for val in m_noisy:
    val = int(val)
    # 0 映射到 0, 1 映射到 q/2
    # 计算到 0 的距离 (考虑环绕)
    dist_0 = min(val, q - val)
    # 计算到 q/2 的距离
    dist_1 = abs(val - scale)
    
    if dist_0 < dist_1:
        flag_bits += "0"
    else:
        flag_bits += "1"

# 5. 转为 ASCII
print("[*] Converting to flag...")
flag = ""
for i in range(0, len(flag_bits), 8):
    byte = flag_bits[i:i+8]
    if len(byte) < 8: break
    char_code = int(byte, 2)
    if char_code == 0: break 
    flag += chr(char_code)

print(f"FLAG: {flag}")

# EPFL{2oo000_un1t5_r34dy_w1th_4_m1ll10n_m0r3_w3ll_0n_th3_w4y_i6o}

Ez Part

题目

image-20251129224608771

分析

代码

1

Misc

zipbomb

image-20251129224048558

给了份zip文件，每轮解压都能得到一份txt文件以及一份zip文件。所以直接写个自动化的脚本一直解压就好了。甚至每个压缩包连密码都没有，所以特别简单。

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
import zipfile
import os

def unzip_and_clean(start_filename):
    current_zip = start_filename
    round_count = 0

    while True:
        round_count += 1
        
        # 1. 解压当前文件
        try:
            with zipfile.ZipFile(current_zip, 'r') as zf:
                zf.extractall()
                # 获取当前包里包含的文件名列表
                files_in_zip = zf.namelist()
        except Exception as e:
            print(f"[-] 解压中断或出错: {e}")
            break

        # 2. 寻找下一层 zip 和当前的 txt
        next_zip = None
        current_txt = None

        for file in files_in_zip:
            if file.endswith('.zip'):
                next_zip = file
            elif file.endswith('.txt'):
                current_txt = file

        # 3. 分情况处理清理逻辑
        if next_zip:
            # --- 情况 A: 还有下一层 (这是中间层) ---
            print(f"[Round {round_count}] 正在处理，发现下一层: {next_zip}")
            
            if current_txt and os.path.exists(current_txt):
                os.remove(current_txt)
            
            if current_zip != start_filename and os.path.exists(current_zip):
                os.remove(current_zip)
            
            # 更新目标，继续循环
            current_zip = next_zip

        else:
            # --- 情况 B: 没有下一层了 (到底了) ---
            
            if current_zip != start_filename and os.path.exists(current_zip):
                os.remove(current_zip)
            
            if current_txt:
                try:
                    with open(current_txt, 'r') as f:
                        print(f"内容为: {f.read().strip()}")
                except:
                    print("无法读取最终文件内容")
            else:
                print("最后一层里没有txt文件。")
            
            break

start_file = "bomb.zip"
unzip_and_clean(start_file)

最后得到flag.txt：

1
EPFL{m4yb3_TH3_r3A1_r4M_15_th3_Fr13nd5_w3_m4d3_410ng_th3_w4y}

发布于：Nov 29, 2025