Misay's blog

Back
14 min
ctf

LILCTF2025

LILCTF2025CryptoWP

题目比较友好适中，成功AK了，鸡块师傅出的Space_Travel很有意思

ez_math#

模pp环下A  BA\;B两个矩阵给出

A=(v11v12v21v22)A=\begin{pmatrix}v_{11}&v_{12}\\v_{21}&v_{22}\end{pmatrix} B=(λ1v11λ1v12λ2v21λ2v22)B=\begin{pmatrix}\lambda_1v_{11}&\lambda_1v_{12}\\\lambda_2v_{21}&\lambda_2v_{22}\end{pmatrix}

给出

C=A−1BC=A^{-1}B

也就是

B=A⋅CB=A\cdot C

知道

C′=(λ100λ2)C^{'}=\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}

是一定符合要求的 那么可知CC和C′C^{'}是相似矩阵，计算特征值即可还原

exp

linear#

生成一个16×3216\times32的矩阵AA,一个32×132\times1列向量xx ，然后计算

b=Axb=Ax

把A  bA\;b告诉你，让你去解xx

这里因为方程组是缺省的，无法直接求逆解出来xx，但这边xx相对A  bA\;b是相对小的量，考虑格基归约，我们知道

(b0,b1,⋯ ,b31)=(a11a12⋯a132a21a22⋯a232⋮⋮⋮a151a152⋯a1532)(x1x2⋮x32)(b_0,b_1,\cdots,b_{31})=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{132}\\a_{21}&a_{22}&\cdots&a_{232}\\\vdots&\vdots&&\vdots\\a_{151}&a_{152}&\cdots&a_{1532}\end{pmatrix}\begin{pmatrix}x_1\\x_2\\\vdots\\x_{32}\end{pmatrix}

不难造格子

(x0,x1⋯ ,x31,1)(10⋯0C⋅a[0][0]C⋅a[1][0]⋯C⋅a[15][0]01⋯0C⋅a[0][1]C⋅a[1][1]⋯C⋅a[15][1]⋮⋮⋱⋮⋮⋮⋱⋮00⋯1C⋅a[0][31]C⋅a[1][31]⋯C⋅a[15][31]00⋯0−C⋅b[0]−C⋅b[1]⋯−C⋅b[15])33×48=(x0,x1⋯ ,x31,0,0,⋯ ,0)(x_0,x_1\cdots,x_{31},1)\begin{pmatrix} 1 & 0 & \cdots & 0 & C \cdot a[0][0] & C \cdot a[1][0] & \cdots & C \cdot a[15][0] \\ 0 & 1 & \cdots & 0 & C \cdot a[0][1] & C \cdot a[1][1] & \cdots & C \cdot a[15][1] \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & C \cdot a[0][31] & C \cdot a[1][31] & \cdots & C \cdot a[15][31] \\ 0 & 0 & \cdots & 0 & -C \cdot b[0] & -C \cdot b[1] & \cdots & -C \cdot b[15] \\ \end{pmatrix}_{33\times48}=(x_0,x_1\cdots,x_{31},0,0,\cdots,0)

同时乘上一个大的常数CC来保证我们的后面基全部取0

exp

mid_math#

与ez_math类似，给出

A=(v11v12v13v14v15v21v22v23v24v25v31v32v33v34v35v41v42v43v44v45v51v52v53v54v55)A = \begin{pmatrix} v_{11} & v_{12} & v_{13} & v_{14} & v_{15} \\ v_{21} & v_{22} & v_{23} & v_{24} & v_{25} \\ v_{31} & v_{32} & v_{33} & v_{34} & v_{35} \\ v_{41} & v_{42} & v_{43} & v_{44} & v_{45} \\ v_{51} & v_{52} & v_{53} & v_{54} & v_{55} \\ \end{pmatrix} B=(a⋅v11a⋅v12a⋅v13a⋅v14a⋅v15b⋅v21b⋅v22b⋅v23b⋅v24b⋅v25c⋅v31c⋅v32c⋅v33c⋅v34c⋅v35d⋅v41d⋅v42d⋅v43d⋅v44d⋅v4500000)B = \begin{pmatrix} a \cdot v_{11} & a \cdot v_{12} & a \cdot v_{13} & a \cdot v_{14} & a \cdot v_{15} \\ b \cdot v_{21} & b \cdot v_{22} & b \cdot v_{23} & b \cdot v_{24} & b \cdot v_{25} \\ c \cdot v_{31} & c \cdot v_{32} & c \cdot v_{33} & c \cdot v_{34} & c \cdot v_{35} \\ d \cdot v_{41} & d \cdot v_{42} & d \cdot v_{43} & d \cdot v_{44} & d \cdot v_{45} \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}

同上CC和

C′=(abcd0)C^{'}=\begin{pmatrix}a&&&&&\\&b&&&&\\&&c&&&\\&&&d&&\\&&&&0\end{pmatrix}

相似，而且满足

B=AC′B=AC^{'}

再给出

D=CkD=C^{k}

相似矩阵的幂乘是一样算的，直接用C′C^{'}即可，也就是说计算DD的特征矩阵就能得到

D′=(akbkckdk0)D^{'}=\begin{pmatrix}a^k&&&&&\\&b^k&&&&\\&&c^k&&&\\&&&d^k&&\\&&&&0\end{pmatrix}

然后解离散对数去求kk即可，而且这里pp还挺光滑，直接解即可 exp

SpaceTravel#

from Crypto.Cipher import AES
from hashlib import md5
from params import vecs
from os import urandom

key = int("".join([vecs[int.from_bytes(urandom(2)) & 0xfff] for _ in range(50)]), 2)

print(len(set(vecs)))

# print("🎁 :", [[nonce := int(urandom(50*2).hex(), 16), (bin(nonce & key).count("1")) % 2] for _ in range(600)])
# print("🚩 :", AES.new(key=md5(str(key).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(open("flag.txt", "rb").read()))
py

给定一个16位的线性空间vecs,vecs中有2122^{12}组数据，随后我们选50个向量，拼接组合出key，然后题目给你600组800比特的nonce，计算

nonce⊕keynonce\oplus key

的01比特和，给出了模2的结果，相当于一组模方程

∑i=1800njiki≡bimod  2\sum^{800}_{i=1}n_{ji}k_i\equiv b_i\mod 2

有600组 肯定没法考虑解方程了，而且维度过高也很难去考虑做格基归约

我们来观察这个线性空间，16位的向量应该有2162^{16}种可能，为什么只有2122^{12}组数据？，这就说明在16位的向量里面不是所有信息都是独立有效的，存在冗余，

我们先尝试找到线性空间的基，比如就取v0v_0，随后对剩下的212−12^{12}-1组别的viv_i,去进行异或回来

li=v0⊕vil0=000000000000000l_i=v_0\oplus v_i\\l_0=000000000000000

直到我们集齐12组线性无关向量即可组成一组基l0,l1,⋯ ,l11{l_0,l_1,\cdots,l_{11}}

看上面的构造可能有点诡异，我们从构造来说构造一个12×1212\times12的线性01空间，然后按照某种规律去计算后四位的冗余位，造就了我们16位但是个数是2122^{12}的vecs，也就是说，看似是800位，但是实际上200位都是冗余计算出来的，给了我们600组同余方程实际上是刚刚好，我们接下来的工作就是如何从这里的600组方程拓展出剩下的200组

首先我们先准确描述这个冗余拓展的过程

h1×12⋅M12×16=l1×16h_{1\times12}\cdot M_{12\times16}=l_{1\times16}

基MM就是我们这边收集12个向量组成的，收集到这个基MM之后，我们能利用这个线性空间的延展构造出一个校验方程H4×16H_{4\times16},那对于所有的vecs中的向量，有

H4×16l16×1=04×1H_{4\times16}l_{16\times1}=0_{4\times1}

这样就构造出了新的方程，exp思路如下

第一部分 从vecs中获得空间基

第二部分 从基构造出检验矩阵H

第三部分 从检验矩阵中构造出剩下的200个方程

第四部分 解方程 求出密钥key

第五部分 由key解密AES恢复flag

baaaaaaaag#

一个背包格子问题，给出72位的pp，给出

∑i=071piai=b        pi∈{0 , 1}\sum^{71}_{i=0}p_ia_i=b\;\;\;\;p_i\in\{0\,,\,1\}

同时我们的p71=1p_{71}=1是已知的，可以用这个手法给降低一下格的维度，我们设新方程为

∑i=070piai=B        pi∈{0 , 1}\sum^{70}_{i=0}p_ia_i=B\;\;\;\;p_i\in\{0\,,\,1\}

一般来说是造格子

(p0,p1,p2,⋯ ,p70,1)(1Ca01Ca1⋱⋮1Ca70−Cb)=(p0,p1,p2,⋯ ,p70,0)(p_0,p_1,p_2,\cdots,p_{70},1)\begin{pmatrix}1&&&&Ca_0\\&1&&&Ca_1\\&&\ddots&&\vdots\\&&&1&Ca_{70}\\&&&&-Cb\end{pmatrix}=(p_0,p_1,p_2,\cdots,p_{70},0)

但是格的效果很差，参考鸡块师傅的博客思路，可以对背包格进行如下优化

M=(2Ca02Ca1⋱⋮2Ca70−1−1⋯−1−Cb)M=\begin{pmatrix}2&&&&Ca_0\\&2&&&Ca_1\\&&\ddots&&\vdots\\&&&2&Ca_{70}\\-1&-1&\cdots&-1&-Cb\end{pmatrix} (p0,p1,p2,⋯ ,p70,1)(2Ca02Ca1⋱⋮2Ca70−1−1⋯−1−Cb)=(2p0−1,2p1−1,2p2−1,⋯ ,2p70−1,0)(p_0,p_1,p_2,\cdots,p_{70},1)\begin{pmatrix}2&&&&Ca_0\\&2&&&Ca_1\\&&\ddots&&\vdots\\&&&2&Ca_{70}\\-1&-1&\cdots&-1&-Cb\end{pmatrix}=(2p_0-1,2p_1-1,2p_2-1,\cdots,2p_{70}-1,0)

这样我们格出来的目标向量就是1，-1 数量级很接近，使用24格维度的BKZ就能解决了,exp

LILCTF2025
https://www.zt2misay2.cn/blog/lilctf2025
Author Misay
Published at 2025年8月18日
Copyright CC BY-NC-SA 4.0
Buy me a cup of coffee ☕.

WMCTF2025

羊城杯2024