WMCTF 2025 复现

在团队的共同努力下，我们 DAWN 战队也是成功挤进了前十 σ ﾟ∀ ﾟ) ﾟ∀ﾟ)σ，记录一下有趣的题目，更新ing

Crypto

LW3

比赛时没有做出来，看了鸡块和 MNGA 的 wp 才开始复现。
题目：

from random import choice, sample
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

m, n = 90, 64
p = 1048583

E = sample(range(1, p), 3)
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(E) for i in range(m)])
b = A*s + e

print("🎁 :", E + A.list() + b.list())
print("🚩 :", AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

分析：
$$
b_{m\times1} = A_{m\times n}s_{n\times 1}+e_{m\times 1} \mod p
$$
这种形式应该很容易就联想到 LWE 容错学习问题，但是通常情况下， e 都是随机取值，而这道题虽然说也是随机取值，但是它的取值只能从长度为 3 的空间 E 中选取。
由于我们的目标就是要找到随机变量 s 的值，因此这是一个搜索型 LWE，我们通常使用 Primal Attack，也就是直接规约整个线性系统，有

$$
(s_1,s_2…s_n,1,k_1,k_2…k_m)
\begin{pmatrix}
1 & & & & -a_{11} & -a_{21} & \cdots & -a_{(m-1)1} & -a_{m1} \newline
& \ddots & & & \vdots & \vdots & \ddots & \vdots & \vdots \newline
& & & 1 & -a_{1n} & -a_{2n} & \cdots & -a_{(m-1)n} & -a_{mn} \newline
& & & & b_1 & b_2 & \cdots & b_{m-1} & b_m \newline
& & & & p & 0 & \cdots & 0 & 0 \newline
& & & & 0 & p & \cdots & 0 & 0 \newline
& & & & \vdots & \vdots & \ddots & \vdots & \vdots \newline
& & & & 0 & 0 & \cdots & p & 0 \newline
& & & & 0 & 0 & \cdots & 0 & p
\end{pmatrix}
=(s_1,s_2…s_n,e_1,e_2…e_m)
$$

简要地写就有：

$$
(s_{1\times n},1,k_{1\times m})
\begin{pmatrix}
I_{n\times n} & -A^T \newline
0 & b_{1\times m} \newline
0 & pI
\end{pmatrix}
=(s_{1\times n},e_{1\times m})
$$

但是这个格并不是很好，需要进行优化，我们可以通过消去目标向量中的 s 向量来进行降维处理

$$
(s_{1\times n},1,k_{1\times m})
\begin{pmatrix}
-A^T \newline
b_{1\times m} \newline
pI
\end{pmatrix}
= (e_{1\times m})
$$

在比赛过程中，我按照鸡块师傅的 easy_mod X 题目的步骤尝试复现，将 e 的取值空间 E 仿射到一个数值较小的空间 E’ 中，具体的仿射方法如下：

$$
E’ = kE + t(1,1,1) \mod p
$$

具体可以造格来求

$$
(k,t,r_1,r_2,r_3)

\begin{pmatrix}
E_1 & E_2 & E_3 \
1 & 1 & 1 \
p & 0 & 0 \
0 & p & 0 \
0 & 0 & p
\end{pmatrix}
\
=(E_1’,E_2’,E_3’)
$$

然鹅通过这种方法算出的 E’ 并不是很小，实测出来的 E’ 为[-298,582,-285]，这就导致仿射之后的 error’ 其实还是很大，我们还是不能直接求解这个 LWE 问题。
在比赛时的思路就到这儿了，当时也跟队友讨论过 k,t 是不是找的不好，导致 E’ 并不能很小，但是也没找到更好地仿射方法。比赛时也想过是否跟仿射子空间相关，毕竟之前在复现 LilCTF 2025 时鸡块师傅就出过 Space Travel 这类跟仿射子空间相关的题目，但是思路好像并不是很明了，也加上对仿射子空间的理解还不是很深，因此并没有深究，就这样无为到了比赛结束。。
赛后看了鸡块师傅的 wp 之后才明白过来，利用 LeetSpe4k 这道题的思路不论是多大的 E 都能映射到多个 01 组成的向量中，在本题中就有：
$$
e_i = (x_i,y_i,z_i)E_{3\times 1}
$$
其中，$x_i,y_i,z_i\in {0,1}$
这样也就可以将 $e_i$ 映射为三个 01 向量上，这三个向量分别为 $(1,0,0),(0,1,0),(0,0,1)$，明显存在仿射子空间。
即
$$
e_i = E_1+(x_i,y_i)
\begin{pmatrix}
E_2-E_1 \newline
E_3-E_1
\end{pmatrix}
$$
其中，$x_i,y_i\in {0,1}$,分别为 $(0,0),(1,0),(0,1)$
$$
b_{m\times1} = A_{m\times n}s_{n\times 1}+e_{m\times 1} \mod p
$$
后续就是造格了，具体代码暂时没写，有需要可以直接查看鸡块师傅的代码。