Problem: [GHCTF 2025]baby_lattice
其实是一个HNP问题
\left\{
\begin{aligned}
g_1 &= t_1 \cdot key + z_1 \\
g_2 &= t_2 \cdot key + z_2 \\
&\vdots \\
g_n &= r_t \cdot key + z_t
\end{aligned}
\right.
\pmod{p}
转化为z_i=g_i-t_i*key+k_ip
K是z的上界key为常系数，进行LLL算法求出最短向量。
M = \begin{bmatrix}
p & & & & \\
& p & & & \\
& & \ddots & & \\
& & & p & \\
-t_1 & -t_2 & \cdots & -t_n & K/p \\
g_1 & g_2 & \cdots & g_n & &K
\end{bmatrix}
(k_1, k_2, \cdots, k_t, key, 1) M = (z_1, z_2, \cdots, z_t, K*key/p, K)
exp
from Crypto.Cipher import AES p = ... rs = [...] cs = [...] iv=b'\x88\x0c\x7f\x92\xd7\xb7\xaf4\xe4\xfb\xd1_\xab\xff)\xb8' ciphertext=b'\x94\x198\xd6\xa2mK\x00\x06\x7f\xad\xa0M\xf7\xadV;EO$\xee\xcdB0)\xfb!&8%,M' t = len(rs) kbits = 400 K = 2 ** kbits P = identity_matrix(t) * p RC = matrix([[-1, 0], [0, 1]]) * matrix([rs, cs]) KP = matrix([[K / p, 0], [0, K]]) M = block_matrix([[P, 0], [RC, KP]], subdivide=False) shortest_vector = M.LLL() x = shortest_vector[1, -2] / K * p % p print(x) cipher = AES.new(str(x).encode()[:16], AES.MODE_CBC,iv) flag=cipher.decrypt(ciphertext) print(flag)
加载中...