2025 aliyunCTF crypto Writeup

LinearCasino

加密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

alarm(120)
n, d1, d2 = 100, 60, 50
FLAG = "aliyunctf{REDACTED}"
print("😊 LinearCasino is the Game 4 Super Guesser.")
for _ in range(100):
    D1 = random_matrix(GF(2), d1, n)
    D2 = random_matrix(GF(2), d2, n)
    A = random_matrix(GF(2), d1+d2, d1+d2)
    B = [random_matrix(GF(2), d1+d2, 2*n), block_matrix([[D1, D1],[0, D2]])]
    C = Permutations(2*n).random_element().to_matrix()
    ct = [A*B[0]*C, A*B[1]*C]
    decision = randint(0,1)
    a = int(''.join(map(str, ct[decision].list())),2)
    print("🎩", int(''.join(map(str, ct[decision].list())),2))
    assert input("🎲 ") == str(decision)
print(f"🚩 Real Super Guesser! {FLAG}")

这题显然是要根据每次输出的ct来判断decision的值

注意到C的生成方式

1

C = Permutations(2*n).random_element().to_matrix()

是一个置换矩阵，我们知道，置换矩阵是满足如下的性质的

$$C\cdot C^T = I$$

然后对于B，又有如下的特殊矩阵

$$\begin{bmatrix} D_1 & D_1\\ 0 & D_2 \end{bmatrix}$$

我们先利用上第一个性质，既然给了我们ABC，那么我们再乘上他的转置

$$A\cdot B \cdot C \cdot C^T \cdot B^T \cdot A^T = A\cdot (B \cdot B^T) \cdot A^T$$

因为B这个矩阵比较特殊，我们尝试计算一下$B\cdot B^T$，关于块矩阵的转置和运算大家可以自己去了解一下

$$\begin{bmatrix} D_1 & D_1\\ 0 & D_2 \end{bmatrix}\cdot \begin{bmatrix} D_1^T & 0\\ D_1^T & D_2^T \end{bmatrix}= \begin{bmatrix} 2D_1\cdot D_1^T& D_1\cdot D_2^T\\ D_2\cdot D_1^T & D_2\cdot D_2^T \end{bmatrix}$$

因为运算都是在$GF(2)$下运算的，所以$2D_1\cdot D_1^T$实际上就是$0$，也就是

$$B\cdot B^T = \begin{bmatrix} 0& D_1\cdot D_2^T\\ D_2\cdot D_1^T & D_2\cdot D_2^T \end{bmatrix}$$

$D_1$是一个$60\times 100$的矩阵，$D_2$是一个$50\times 100$的矩阵，那么$D_2\cdot D_1^T $就是一个$50\times 60$的矩阵，意味着他的秩最多是五十，那么也就是说$D_2\cdot D_1^T$其实可以通过初等列变换，变成一个前五十列都是线性无关，后面十列都是线性相关的矩阵，又因为$D_2\cdot D_1^T$上面是0，那么对于整个$B\cdot B^T$来说，通过初等列变换之后，就一定有10列可以都是其他所有列线性相关的组合，也就是都可以是0向量，那么整个$B\cdot B^T$的秩最多就是100

虽然说我们只能得到$A\cdot (B \cdot B^T) \cdot A^T$，但其实矩阵运算有如下的性质

也就是说，我们得到的$A\cdot (B \cdot B^T) \cdot A^T$的秩最多也就是100，如果$B$不是那种特殊的矩阵，就不会有这个性质

用这个作为决策即可

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from tqdm import trange
from pwn import *

io = remote('121.41.238.106', 60215)

io.recvline()

for _ in trange(100):
    a = int(io.recvline().replace(b'\xf0\x9f\x8e\xa9 ', b'').decode())
    a = bin(a)[2::].zfill(110 * 200)
    ct = []
    for i in range(0, 110 * 200, 200):
        ct.append(list(map(int, list(a[i:i + 200]))))
    ct = Matrix(GF(2), 110, 200, ct)
    test = ct * ct.T
    io.recv()
    if test.rank() <= 100:
        io.sendline(b'1')
    else:
        io.sendline(b'0')
print(io.recvline())  #b'\xf0\x9f\x9a\xa9 Real Super Guesser! aliyunctf{U_r_l1near_4lgebra_mast3r}\n'

大概一分钟能出