2025-AliyunCTF-crypto

复现一下，还是太菜了😩

LinearCasino

题目：

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}")

题目描述：

${B_0}_{(d_1+d_2) \times 2n}随机矩阵$

$B_1 = \left( \begin{matrix} {D_1}_{d_1\times n} & {D_1}_{d_1\times n}\\ 0 & {D_2}_{d_2\times n} \end{matrix}\right)$

分别计算两个$GF(2)$矩阵$c_0$和$c_1$：

$enc_0 = AB_0C$

$enc_1 = AB_1C$

靶机发来一段密文，判断这个密文是$enc_0$还是$enc_1$
参考2025-阿里云CTF-wp-crypto|糖醋小鸡块的blog
这道题主要从矩阵的秩入手
C是一个置换矩阵(每一行有一个随机位置为1，其余位置都是0，并且一列不会同时出现两个1)
举例：

$\left( \begin{matrix} 0&1&0\\ 1 & 0&0\\ 0&0&1 \end{matrix}\right)$

那么就有：

$CC^T = E$

并且对于$enc_1$有：

$AB_1C(AB_1C)^T = AB_1(CC^T)B_1^TA^T = AB_1B_1^TA^T$

计算$B_1B_1^T$:

$B_1B_1^T = \left( \begin{matrix} {D_1} & {D_1}\\ 0 & {D_2} \end{matrix}\right) \left(\begin{matrix} {D_1}^T & 0\\ {D_1}^T & {D_2}^T \end{matrix}\right) = \left(\begin{matrix} 2D_1{D_1}^T & D_1D_2^T\\ D_2{D_1}^T & D_2{D_2}^T \end{matrix}\right)$

$GF(2)$下，那么就有

$B_1B_1^T = \left(\begin{matrix} 0 & {D_1D_2^T}_{d_1\times d_2}\\ {D_2{D_1}^T}_{d_2\times d_1} & {D_2{D_2}^T}_{d_2\times d_2} \end{matrix}\right)_{(d_1+d_2)\times (d_1+d_2)}$

复习一下矩阵的秩的重要性质：

通过性质1可以推出左半矩阵的秩不大于$d_2$，右半矩阵的秩也不大于$d_2$
再通过性质5，得到$B_1B_1^T$ 的秩不大于$2d_2$
最后通过性质7，得到结论：$AB_1B_1^TA^T$一定小于$2d_2$
exp：

from tqdm import *
from pwn import *

sh = remote('121.41.238.106','16938')
sh.recvuntil(b"LinearCasino is the Game 4 Super Guesser.")

n, d1, d2 = 100, 60, 50
for _ in trange(100):
    sh.recvuntil(b"\xf0\x9f\x8e\xa9 ")
    enc = Matrix(GF(2), d1+d2, 2*n, list(map(int, bin(int(sh.recvline().strip().decode()))[2:].zfill((d1+d2)*(2*n)))))
    if((enc*enc.T).rank() <= 100):
        sh.sendline(b"1")
    else:
        sh.sendline(b"0")
print(sh.recvline())