NSSCTFMatrix

NSSCTF Matrix 系列EXP

0.Introduction

最近在NSSCTF上看到了格密码的相关题目，准备对相关知识点进行一个巩固，因此来看一看！这一期是Matrix系列。

1.Matrix Warmup

第一题，很简单！

from Crypto.Util.number import *
from random import randint
from secret import flag

p = getPrime(256)

print("p =", p)
print("c =", randint(1,p)*vector(Zmod(p), [i*getPrime(128) for i in flag]))

题目给出了一个模数 $p$，和密文向量 $\vec c$ ，其中 $c_i$ 的表达式为：
$$
c_i=rqm_i
$$
其中 $q_i$ 是随机的 $128$ 位素数，$r$ 是固定的随机数，$m_i$ 是 flag 的比特，我们的目标是求出 $\vec m$。

反推 $m$，那就是：
$$
m_iq_i\equiv \frac{c_i}{r} \pmod p
$$
由于 $m_i$ 是八位，$q_i$ 是 $128$ 位，那么 $m_iq_i$ 仍然只有 $136$ 位，因此可以直接规约（为展示方便，仅以 $n=3$ 为例展示矩阵构造，更高维度可以直接模仿，本文中其他题目也会这样）：

很显然 $136$ 位是能够规约出来的，因为 $p$ 占满了所有列。

EXP:

p=
c=
C=matrix(c)
M=block_matrix(ZZ,[C,p*identity_matrix(len(c))],nrows=2)
M3L=M.LLL()
vec=M3L[1]
if(vec[0]<0):
    vec=-vec
s=[]
for i in range(len(vec)):
    flist=list(factor(vec[i]))
    s.append(vec[i]//flist[-1][0])
print(bytes(s))
#b'NSSCTF{F1nd_@_s3cR3t_NUMBER_1s_eAsy_4_U}'

2.Matrix 1

看看题：

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

n = 10
p = getPrime(256)
M1 = Matrix(Zmod(p), n, n, pad(flag[:len(flag)//2],n^2))
M2 = Matrix(Zmod(p), n, n, pad(flag[len(flag)//2:],n^2))

A = random_matrix(Zmod(p), n, n)
B = M1*A*M2^(-1)

print("p =", p)
print("A =", A.list())
print("B =", B.list())

题目的关系式也很明显：$B=M_1AM_2^{-1}$。也就是 $BM_2=M_1A$，设 $C=M_1A-BM_2$，$A,B,M_1,M_2$ 中元素分别用 $a,b,x,y$ 表示，那么我们可以得到：
$$
c_{uv}\equiv \sum_{i=0}^9 (x_{ui}a_{iv})-\sum_{i=0}^9 (b_{ui}y_{iv})\pmod p
$$

$n=10$，那就是 $200$ 个未知数，在要考虑模 $p$ 单独增 $100$ 维，那就是 $300\times 300$ 的矩阵，其线性关系如下：
$$
(x_{00},…,x_{99},y_{00},…,y_{99},k_0,…,k_{99})\mathbf M=(x_{00},…,x_{99},y_{00},…,y_{99},0,…,0)
$$

其中：

这里 $A’=\mathrm{diag}(A,A,…,A)$，$B’$ 是将 $B^T=[b_{ji}]$ 中每个元素替换为 $b_{ji}E_{10}$ 得到的分块矩阵。

300 规模的矩阵，直接flatter吧。。。最后一部分列乘个大数 $2^{2000}$，保证规约出来是 $0$。

EXP:

from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
p=
A=
B=
A=matrix(GF(p),10,10,A)
B=matrix(GF(p),10,10,B)
A10=block_matrix(GF(p),[[zero_matrix(10) if(i!=j) else A for j in range(10)] for i in range(10)])
Bv=[[B[j][i]*identity_matrix(10) for j in range(10)]for i in range(10)]
B10=block_matrix(GF(p),Bv)
M=block_matrix(ZZ,
               [[identity_matrix(100),zero_matrix(100,100),A10],
                [zero_matrix(100,100),identity_matrix(100),-B10],
                [zero_matrix(100,100),zero_matrix(100,100),-p*identity_matrix(100)]])

Mb=diagonal_matrix([1]*200+[2**2000]*100)
M=M*Mb
from datetime import *
print(datetime.now())
M3L=flatter(M)
print(datetime.now())
print(M3L[0])
#2025-03-31 09:41:54.930319
#2025-03-31 09:46:08.335148
#(-78, -83, -83, -67, -84, -70, -123, -76, -76, -76, -49, -49, -49, -108, -108, -108, -164, -118, -29, -77, -131, -183, -224, -168, -164, -111, -124, -94, -178, -231, -157, -228, -203, -94, -55, -119, -128, -47, -166, -21, -77, -95, -46, -188, -25, -47, -114, -99, -155, -76, -202, -174, -107, -110, -135, -206, -126, -225, -86, -132, -255, -32, -190, -45, -59, -159, -119, -59, -141, -8, -97, -8, -158, -245, -25, -174, -67, -74, -67, -80, -211, -40, -181, -101, -188, -104, -99, -179, -53, -227, -30, -124, -75, -1, -67, -219, -245, -5, -111, -229, -95, -49, -110, -95, -116, -104, -51, -95, -107, -51, -114, -110, -51, -76, -33, -125, -15, -169, -236, -109, -175, -27, -232, -69, -255, -79, -140, -61, -94, -5, -64, -10, -29, -96, -9, -11, -237, -51, -98, -221, -42, -250, -40, -89, -237, -118, -251, -105, -99, -236, -71, -182, -25, -12, -58, -121, -88, -79, -65, -24, -22, -236, -27, -243, -251, -192, -72, -58, -107, -21, -216, -93, -125, -123, -86, -96, -79, -219, -205, -252, -205, -182, -40, -76, -138, -39, -178, -195, -242, -207, -218, -73, -26, -34, -131, -40, -186, -228, -136, -106, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
#NSSCTF{LLL111lll_1n_th3_k3rn3L!}

补一句：像上面这个，三分之一的列有 $p$，那么可规约出向量的规模上界就是 $p^{1/3}$。

3.Matrix1-2

题目将 $B=M_1AM_2^{-1}$ 改成了 $B=M_1AM_2$，但是维度减少到了 $5\times5$。

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

n = 5
p = getPrime(512)
M1 = Matrix(Zmod(p), n, n, pad(flag[:len(flag)//2],n^2))
M2 = Matrix(Zmod(p), n, n, pad(flag[len(flag)//2:],n^2))

A = random_matrix(Zmod(p), n, n)
B = M1*A*M2

print("p =", p)
print("A =", A.list())
print("B =", B.list())

那这样肯定不能直接求逆矩阵了，但根据 $B=M_1AM_2$ 可以得到下面的式子：
$$
b_{uv}\equiv\sum_{i=0}^4\sum_{j=0}^4 a_{ij}x_{ui}y_{jv}\pmod p
$$

由于 $x,y$ 均不超过 $255$，因此 $xy$ 不会超过 $16$ 位，和 $512$ 位相比仍然是很小的。那这样， 就会有 $625$ 个式子，勉强够跑。

对应的关系式为：
$$
(x_{00}y_{00},x_{00}y_{01},…,x_{44}y_{44},1,k_{0000},k_{0001},…,k_{4444})\mathbf M=(x_{00}y_{00},x_{00}y_{01},…,x_{44}y_{44},0,…0)
$$
其中：

这里 $C$ 的定义如下，对应着上面 $b_{uv}$ 的系数：

C=[[0 for _ in range(25)]for __  in range(625)]
tot=0
for i in range(25):
    xrow,ycol=i//5,i%5
    for xcol in range(5):
        for yrow in range(5):
            C[xrow*125+xcol*25+yrow*5+ycol][tot]=A[xcol][yrow]
    tot+=1
C=matrix(C)

EXP:

from subprocess import check_output
from re import findall
from sage.all import *
p=
A=
B=
A=matrix(ZZ,5,5,A)
C=[[0 for _ in range(25)]for __  in range(625)]
tot=0
for i in range(25):
    xrow,ycol=i//5,i%5
    for xcol in range(5):
        for yrow in range(5):
            C[xrow*125+xcol*25+yrow*5+ycol][tot]=A[xcol][yrow]
    tot+=1
C=matrix(C)
M=block_matrix(ZZ,
    [
        [identity_matrix(625),C],
        [zero_matrix(1,625),matrix([-i for i in B])],
        [zero_matrix(25,625),-p*identity_matrix(25)]
    ]
)
Mb=diagonal_matrix([1]*625+[65536]+[2**8000]*25)
from datetime import *
print(datetime.now())
M3L=M.LLL()
print(datetime.now())
#About 5 minutes.
vec=M3L[1]
X=[]
Y=[]
if(vec[0]<0):
    vec=-vec
from Crypto.Util.number import *
Y=[]
for i in range(25):
    xi=vec[i*25]
    for j in range(25):
        xi=GCD(xi,vec[i*25+j])
    X.append(xi)
    for j in range(25):
        Y.append(vec[i*25+j]//xi)
print(bytes(X))
print(bytes(Y[:25]))
#NSSCTF{M@k3_N0n_L1ne@r_L1ne@r!}

4.Matrix 3

题目：

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

n = 10
p = getPrime(256)
M = Matrix(Zmod(p), n, n, pad(flag,n^2))
e = Matrix(Zmod(p), n, n, pad(b"",n^2))
W = random_matrix(Zmod(p), n, n)
X = random_matrix(Zmod(p), n, n)
Y = random_matrix(Zmod(p), n, n)
Z = random_matrix(Zmod(p), n, n)

C = W*X*M*Y*Z+e

print("p =", p)
print("W =", W.list())
print("X =", X.list())
print("Y =", Y.list())
print("Z =", Z.list())
print("C =", C.list())

这个题目拿到，很自然地就能想到 $WX=A,YZ=B$，误差矩阵为 $R$ （和单位矩阵 $E$ 冲突了所以换个字母），那么最后的结果就是 $C=AMB+R$。这里 $M,R$ 的每个元素均不超过 $256$。

在草稿纸上推个式子（其实是拿个 $2\times 2$ 的例子算一下），设 $A,B,M,R$ 每个元素用 $a,b,x,y$ 表示，那么就有：
$$
C_{uv}\equiv\sum_{i=0}^9\sum_{j=0}^9 a_{ui}x_{ij}b_{jv}+y_{uv}\pmod p
$$
得到对应矩阵关系：
$$
(x_{00},…,x_{99},y_{00},…,y_{99},k_{00},…,k_{99},1)\mathbf M=(\vec x_{100},\vec y_{100},\vec 0_{100},1)
$$
其中

这个需要给最终结果为 $0$ 的列统一乘上很大的数 $2^{8000}$ 保证规约出 $0$ ，这个建议用flatter，找最后一列为 $1$ 的向量就OK，跑起来时间也不长。

from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
p=
W=
X=
Y=
Z=
C=
Cexpand=C.copy()
W,X,Y,Z,C=[matrix(GF(p),10,10,mati) for mati in [W,X,Y,Z,C]]
A=W*X
B=Y*Z
Mx=[[0 for _ in range(100)] for __ in range(100)]
for u in range(10):
    for v in range(10):
        for i in range(10):
            for j in range(10):
                Mx[i*10+j][10*u+v]=A[u][i]*B[j][v]
Mx=matrix(GF(p),Mx)

M=block_matrix(ZZ,[
    [identity_matrix(100),zero_matrix(100),Mx,0],
    [zero_matrix(100),identity_matrix(100),identity_matrix(100),0],
    [zero_matrix(100),zero_matrix(100),-p*identity_matrix(100),0],
    [zero_matrix(1,100),zero_matrix(1,100),-matrix(Cexpand),1],
])
from datetime import *
Mb=diagonal_matrix([1]*200+[2**8000]*100+[1])
print(datetime.now())
M3L=flatter(M*Mb)
print(datetime.now())
for vec in M3L:
    if(vec[-1] in [1,-1]):
        vec=vec*vec[-1]
        print(bytes(vec))

5.Matrix 2

题目：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint
from hashlib import md5
from secret import flag

n = len(flag)
p = getPrime(256)
secret = [randint(1,p) for i in range(n)]

def encrypt(n,p,msg):
    while(1):
        L = []
        R = []
        for i in range(n):
            temp = random_vector(Zmod(p), n)
            L.append(temp)
            R.append(msg[i]*temp)
        L = Matrix(Zmod(p),L).T
        R = Matrix(Zmod(p),R).T
        if(L.rank() == n and R.rank() == n):
            return (R*L^(-1))^(bytes_to_long(b"Tequila"))

print("p =", p)
print("C =", encrypt(n,p,vector(Zmod(p),secret)).list())
print("enc =", AES.new(key=md5(str(sum(secret)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

这里给出的内容是： $L$ 为随机矩阵， R[i]=msg[i]*temp 可以转换成 $R=DL$，其中 $D=\mathrm {diag}(m_0,…,m_{n-1})$。但后面又进行了转置，就变成了 $R^T(L^T)^{-1}=L^TD(L^T)^{-1}$。为了简化，后面还是记作 $C=RL=LDL^{-1}$。

然后给 $C$ 升高到 $e$ 次方，那就变成了 $C^e=LD^eL^{-1}$。

这个，太明显了 Jordan 标准型。这里 $D$ 是对角阵，每个对角元的值为 $C$ 的特征值，$L$ 的每一行都是 $C$ 的特征向量。

既然这里只要求 $m$，那就对 $C^e$ 求特征值就OK了，就得到了 $m^e$，然后设 $d\equiv e^{-1}\pmod {p-1}$，那么 $D^{ed}\equiv D$，那么密钥也就出来了，最后解AES就OK。

p=
C=
enc = 
n=35
C=matrix(GF(p),35,35,C)
cLambsE=C.eigenvalues() #求特征值
from Crypto.Util.number import *
e=bytes_to_long(b"Tequila")
d=pow(e,-1,p-1)
s=0
for i in cLambs:
    s+=Integer(pow(i,d,p))
from hashlib import md5
from Crypto.Cipher import AES
AES.new(key=md5(str(s).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(enc)
#b'NSSCTF{A_S1mPl3_e1g3nVa1ue5_tr1ck!}'

6.Matrix 4

origin

题目和 Matrix 2 差不多，只不过这次 flag 不是特征值而是特征向量了。

from Crypto.Util.number import *
from random import randint
from secret import flag

n = len(flag)
p = getPrime(256)

def encrypt(n,p,msg):
    while(1):
        L = [msg]
        R = [randint(1,p)*msg]
        for i in range(n-1):
            temp = random_vector(Zmod(p), n)
            L.append(temp)
            R.append(randint(1,p)*temp)
        L = Matrix(Zmod(p),L).T
        R = Matrix(Zmod(p),R).T
        if(L.rank() == n and R.rank() == n):
            return (R*L^(-1))^(bytes_to_long(b"Tequila"))

print("p =", p)
print("C =", encrypt(n,p,vector(Zmod(p),flag)).list())

那就求 $C$ 的特征向量呗，但求出来之后，发现所有的特征向量的 $0$ 分量全是 $1$，并不存在目标分量。这是因为如果 $\vec v$ 是 $C$ 的特征向量，那么 $k\vec v$ 也是 $C$ 的特征向量。

但我们发现：flag 以 NSSCTF 开头，那么我们比较 $1$ 分量和 $2$ 分量，如果相等，给向量乘个 ord('N') 就OK 了。

p=
C=
C=matrix(GF(p),42,42,C)
vecs=C.eigenvectors_right()
for _,v,_ in vecs:
    v=v[0]
    if(v[1]==v[2]):
        print(bytes(v*ord('N')))
#b'NSSCTF{AnotHer_S1mPl3_EIGeNVecT0Rs_tr1ck!}'

revenge

当然，上面做法是个非预期，如果是预期的话可不能这样做，可以很容易patch掉，比如改编一下，这里就无法获取flag的任何信息了。

from Crypto.Util.number import *
from random import randint
n = 42
sec=[randint(0,1435756428) for i in range(42)]
flagvec=Matrix(GF(1435756429),6,6,sec[:36])*vector(GF(1435756429),sec[36:42])
flag='{:08x}-{:08x}-{:08x}-{:08x}-{:08x}-{:08x}'.format(*list(flagvec.change_ring(ZZ)))
flag='flag{'+flag+'}'
p = getPrime(256)

def encrypt(n,p,msg):
    while(1):
        L = [msg]
        R = [randint(1,p)*msg]
        for i in range(n-1):
            temp = random_vector(Zmod(p), n)
            L.append(temp)
            R.append(randint(1,p)*temp)
        L = Matrix(Zmod(p),L).T
        R = Matrix(Zmod(p),R).T
        if(L.rank() == n and R.rank() == n):
            return (R*L^(-1))^(bytes_to_long(b"Tequila"))
C= encrypt(n,p,vector(Zmod(p),sec)).list()
print("p =", p)
print("C =",C)
#p = 112169051851714802540387099585133397833014816285769678393235096111510364869297
#C 太长了，这里不显示了
#我给出 flag 和 sec ，供读者复现结果
#flag{0a5641e7-3b0ca89c-4c2792c5-486576b2-0d4f6332-47ac2802}
#sec=[671443054, 586630007, 336583719, 1298232990, 829231085, 1070753942, 1333204010, 590719965, 849200590, 741406549, 983712290, 373905527, 320060101, 1397695941, 638919568, 478237791, 1046713805, 786161945, 1264629445, 1149174551, 1342496024, 1126237882, 290399463, 454222086, 738507754, 248959554, 1132393069, 942996878, 1103926530, 204050933, 735861754, 6762665, 34841354, 1024108418, 1028205630, 173588932, 1003835352, 429073821, 1293368791, 1371635298, 278995282, 635134165]

那么最后一步就要用 Warm-Up的方法，构造矩阵进行求解了。

p=
C=
C=matrix(GF(p),42,42,C)
vecs=C.eigenvectors_right()
def solve3(v):
    M=block_matrix(ZZ,[matrix(v),p*identity_matrix(len(v))],nrows=2)
    M3L=M.LLL()
    return M3L[1]
for _,v,_ in vecs:
    v=v[0]
    sol=(solve3(v))
    if(all([abs(i)<1435756429 for i in sol])):
        print(sol)
        break
if(sol[0]<0):
    sol=-sol
flagvec=Matrix(GF(1435756429),6,6,sol[:36])*vector(GF(1435756429),sol[36:42])
flag='{:08x}-{:08x}-{:08x}-{:08x}-{:08x}-{:08x}'.format(*list(flagvec.change_ring(ZZ)))
print(flag)
#0a5641e7-3b0ca89c-4c2792c5-486576b2-0d4f6332-47ac2802

7.Matrix 5

这个题目的又一个变式：每个特征向量的最后 $5$ 个数是 flag 的一部分。

from Crypto.Util.number import *
from random import randint
from secret import flag

n = len(flag)-4
p = getPrime(256)

def encrypt(n,p,msg):
    while(1):
        L = []
        R = []
        for i in range(n):
            temp = vector(Zmod(p), [randint(1,p) for _ in range(n-5)] + list(msg[i:i+5]))
            L.append(temp)
            R.append(randint(1,p)*temp)
        L = Matrix(Zmod(p),L).T
        R = Matrix(Zmod(p),R).T
        if(L.rank() == n and R.rank() == n):
            return (R*L^(-1))^(randint(1,p))

print("p =", p)
print("C =", encrypt(n,p,vector(Zmod(p),flag)).list())

由于 flag 每个值均在 $32\sim 126$ 之间，并且这个区间内素数还不少，因此 flag[i]/flag[i+1] 的比值的数量是有限的，我们可以存下这个比值。因为特征向量整体乘一个数，相邻两个数的比值是不变的。那么我们就可以根据两两之间的比值，得到相关的flag信息了。再根据flag以 NSSCTF 开头，因此我们就能通过手动拼接实现了！

p=
C=
C=matrix(GF(p),47,47,C)
vecs=C.eigenvectors_right()
D=[]
#构造取值集合
for i in range(32,127):
    for j in range(32,127):
        D.append((i*pow(j,p-2,p)%p,i,j,GCD(i,j)==1))
D=set(D)
for _,v,_ in vecs: #计算比值，可能比值对应结果不唯一，但因为互素概率不低，因此 4 组数据肯定能有互素的:D
    v=v[0]
    judgarr=[v[-i]/v[-i+1] for i in [5,4,3,2]]
    R=[[],[],[],[]]
    for i in range(4):
        for item in D:
            if(item[0]==judgarr[i]):
                R[i].append(item)
    for i in range(4):
        if(len(R[i])==1):
            r=R[i][0]
            v=v/v[-5+i]*r[1]
            print(bytes(v[-5:]))
            break
#最后需要把所有输出进行手动拼接，并且是乱序的，有点麻烦
#NSSCTF{U_h4Ve_C0mp1et3d_H@lF_0f_MATRIX_cha1LenGe5!}

然而我看了wp，发现这个题又被我非预期了:D。正解是把最后 $5$ 个分量拿进去规约。

p=
C=
C=matrix(GF(p),47,47,C)
vecs=C.eigenvectors_right()
def solve3(v):
    M=block_matrix(ZZ,[matrix(v),p*identity_matrix(len(v))],nrows=2)
    M3L=M.LLL()
    return M3L[1] if M3L[1][0]>0 else -M3L[1]
arr=[]
for _,v,_ in vecs[::]: 
    v=v[0]
    s=(solve3(v[-5:]))
    print(bytes(s))

8.Matrix 6

from Crypto.Util.number import *
from random import randint
from secret import flag

polyeval = lambda poly, x: sum(a*pow(x,i,n) for a,i in poly) % n

p = getPrime(256)
q = getPrime(256)
n = p*q
e = 1337
m = bytes_to_long(flag)

nums = 10
g = [(randint(1,n), i) for i in range(nums)]
F = []
C = []
for i in range(nums+1):
    f = [(randint(1,n), (randint(1,n))) for i in range(nums)]
    F.append(f)
    C.append(polyeval(g,polyeval(f,m)))

print("n =", n)
print("c =", pow(m,e,n))
print("F =", F)
print("C =", C)

题目生成了两个素数： $p,q$，并计算 $n=pq$。然后生成了 $11$ 个次数巨大的 $f_i(x)$ 和一个 $9$ 次 $10$ 项的 $g(x)$，计算 $g(f_i(m))$ 的结果，题目还给出了 $c\equiv m^{1337} \pmod n$ 的值。

很显然，$f$ 是已知的，但 $g$ 是未知的，但我们有了这些式子：
$$
g(f(x))=\sum_{i=0}^9 a_if^i(x)
$$
很自然地，我们要想方法求出 $g$ 的系数。但问题是，这边 $f$ 的次数非常大，可能不好算。

好在注意到 $g(f_i(x))-C_i\equiv 0\pmod n$ ，然后设 $h(x)=x^{1337}-c$。那么我们就有了 $g(f_i(m))-C_i=0$ 和 $h(m)=0$。

由于 $h$ 是 $1337$ 次，因此可以将次数巨大的 $f$ 模 $h$ 进行将次处理，然后求出 $g$ 的系数。

如果想求 $g$ 的系数，其实很自然地，这就是解线性方程组。但列出来，发现，$f$ 有 $11$ 个，但 $g$ 只有 $10$ 项。构造出来的方程组类似于这样：

因此这边就成立一个突破口：左边是 $n+1$ 行 $n$ 列的矩阵，乘上一个 $n$ 维向量，得到的结果为 $n+1$ 维向量，即 $\mathbf F_{11,10}\vec g_{10}=\vec c_{11}$。说明矩阵和等号右边的向量是存在线性关系的，因此可以将等号右边的向量与左边的矩阵合并，得到 $(n+1)\times(n+1)$ 的增广矩阵 $(\mathbf F|\vec c)_{11,11}$。

由于矩阵中的元素都是多项式，因此最终矩阵的行列式也是多项式，记为 $D(x)$。根据 $F$ 与 $c$ 存在的线性关系，因此增广矩阵肯定不满秩，我们就有了当 $x=m$ 时 $D(x)=0$ 成立。又因为当 $x=m$ 时，$h(x)=x^{1337}-c=0$ 也成立，那就可以求多项式GCD，结果肯定是 $x-m$，这样 $m$ 我们就得到了。

不得不吐槽一下，就因为 $n$ 是合数，sage 就不实现多项式GCD了。。。这个玩意这么简单都NotImplentedError，还得自己写一个，无语。。

n=
c=
F=
C=
R.<x_>=PolynomialRing(Zmod(n))
Rq.<x>=R.quotient(x_**1337-c) #降次关键
Fx=[]
from tqdm import *
for i in tqdm(range(len(F))):
    fx=sum([a*x**b for a,b in F[i]])
    Fx.append(fx)
M=[]
for i in range(len(Fx)):
    M.append([Fx[i]**j for j in range(10)]+[-C[i]])
M=matrix(M)
detM=M.det()
from Crypto.Util.number import *
def fxgcd(fx,gx):
    if(gx==0):
        return fx.monic()
    return fxgcd(gx,fx%gx)
long_to_bytes(int(-fxgcd(R(list(detM)),x_**1337-c)%x_))

9.Matrix 7

这个题，把多项式变成了矩阵，反而还简单了:D

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

def F(A):
    res = Matrix(Zmod(p), n, n)
    for i in range(len(f)):
        res += A^(i+1)*f[i]
    return res

n = 10
p = getPrime(256)
f = [Matrix(Zmod(p), n, n, pad(flag,n^2))] + [random_matrix(Zmod(p), n, n) for i in range(n-1)]

C = []
for i in range(10):
    A = random_matrix(Zmod(p), n, n)
    C.append([A.list(),F(A).list()])

print("p =", p)
print("C =", C)

题目给出了十组关系式 $C=f(A)=\sum_{i=1}^{10}A^iF_i$ （没有 0 次项）。其中 flag 藏在 $F_1$ 中。

很自然地，根据拉格朗日插值法列矩阵方程，只不过以前矩阵中每个元素是是数字，现在变成了分块矩阵，以三个为例，就是这样的：

直接对左边的矩阵进行 solve_right 即可，就直接得到了所有的 $F$ 了，思路和解题都是比较自然的。

p=
C=
Y=[matrix(GF(p),10,10,C[i][1]) for i in range(10)]
Y=block_matrix(GF(p),Y,nrows=10)
A=[matrix(GF(p),10,10,C[i][0]) for i in range(10)]
M=[[A[i]**j for j in range(1,11)] for i in range(10)]
M=block_matrix(GF(p),M)
Z=M.solve_right(Y)
s=[]
for i in range(10):
    s+=list(Z[i])
bytes(s)
#NSSCTF{M@tRiX_L4granGe_InterP0lati0n_1Sn't_H4rD}

10.Matrix 8

不同于 Matrix 7，这里 flag 藏于每个 $F$ 中，并且此时 $F_i$ 也不再是随机矩阵，而是每个元素的数值都不超过256的矩阵。这里给出了 7 组 $A,B=f(A)$，要求 $f$ 中的矩阵系数 $F_i$。

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

def F(A):
    res = Matrix(Zmod(p), n, n)
    for i in range(len(f)):
        res += A^(i+1)*f[i]
    return res

n = 7
p = getPrime(256)
f = [Matrix(Zmod(p), n, n, pad(flag,n^2)) for i in range(n)]

C = []
for i in range(1):
    A = random_matrix(Zmod(p), n, n)
    C.append([A.list(),F(A).list()])

print("p =", p)
print("C =", C)

讲个笑话：因为每个 $F$ 前面都是flag，后面是随机填充的，我一开始看错了题，以为所有 $F$ 一样，结果上手直接算了个 $(\sum_{i=1}^{10}A^i)^{-1}B_0$，然后解出了 flag 的大半，只有几个值算不出来。。当然，这个方法终究是错的XD。

既然题目中出现了明显的小量，那肯定往LLL处去思考。设 $B_T=[b_{t;ij}],F_T=[x_{T;ij}]$，那么我们可以得到式子：
$$
b_{uv}=\sum_{T=0}^6\sum_{i=0}^{6} a_{T;ui}x_{T;iv}
$$
所以得到的线性关系是这样的：
$$
(x_{0;00},…,x_{6;66},k_0,…,k_{48},1)\mathbf M=(x_{0;00},…,x_{6;66},0,…,0,1)
$$
因此构造矩阵:

其中 $M_X$ 为 $343$ 行 $49$ 列的矩阵，其定义如下，由上面 $b_{uv}$ 的关系式可以推出。（注意：由于我们是左乘行向量，因此每一行的结果对应行向量的分量，每一列对应一个线性等式关系）

Aarr=[A**i for i in range(1,8)]
Mx=[[0 for _ in range(49)]for __ in range(343)]

for u in range(7):
    for v in range(7):
        for T in range(7):
            for i in range(7):
                Mx[49*T+i*7+v][u*7+v]=Aarr[T][u][i]

Mx=matrix(ZZ,Mx)

得到EXP：

p=
C=
A,B=C[0][0],C[0][1]
A=matrix(GF(p),7,7,A)
from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

Aarr=[A**i for i in range(1,8)]
Mx=[[0 for _ in range(49)]for __ in range(343)]

for u in range(7):
    for v in range(7):
        for T in range(7):
            for i in range(7):
                Mx[49*T+i*7+v][u*7+v]=Aarr[T][u][i]

Mx=matrix(ZZ,Mx)
M=block_matrix(ZZ,[
    [identity_matrix(343),Mx,zero_matrix(343,1)],
    [zero_matrix(49,343),-p*identity_matrix(49),zero_matrix(49,1)],
    [zero_matrix(1,343),-matrix(B),1]
])
from datetime import *
print(datetime.now())
Mb=diagonal_matrix([1]*343+[2**2000]*49+[1])
M3L=flatter(M*Mb)
print(datetime.now())
#2025-03-31 20:39:39.723676
#2025-03-31 20:44:35.216418
for vec in M3L:
    if(vec[-1] in [1,-1]):
        vec*=vec[-1]
        print(bytes(vec))
#NSSCTF{Y3t_4n0Th3r_L@graNge_InterP0lati0n_TasK}

11.Matrix 8-2

题目将之前的 $n=7$ 改成了 $n=15$，其余部分完全一致。

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

def F(A):
    res = Matrix(Zmod(p), n, n)
    for i in range(len(f)):
        res += A^(i+1)*f[i]
    return res

n = 15
p = getPrime(256)
f = [Matrix(Zmod(p), n, n, pad(flag,n^2)) for i in range(n)]

C = []
for i in range(1):
    A = random_matrix(Zmod(p), n, n)
    C.append([A.list(),F(A).list()])

print("p =", p)
print("C =", C)

根据上个题构造了 $343+49+1=383$ 维的矩阵（$n^3+n^2+1$），那么当 $n=15$ 时，矩阵规模就达到了 $3375+225+1=3601$。然后根据 LLL 算法的复杂度为 $O(n^{6} \ln^3 n)$，这复杂度直接炸了。。。

我们再回顾一下前面造矩阵的的过程：

Aarr=[A**i for i in range(1,8)]
Mx=[[0 for _ in range(49)]for __ in range(343)]

for u in range(7):
    for v in range(7):
        for T in range(7):
            for i in range(7):
                Mx[49*T+i*7+v][u*7+v]=Aarr[T][u][i]

以及当时推出的等式：
$$
b_{uv}=\sum_{T=0}^6\sum_{i=0}^{6} a_{T;ui}x_{T;iv}
$$
可以发现：$b_{uv}$ 的计算中，仅涉及到了 $x_{T;iv}$ 和 $a_{T;ui}$，$a$ 的下标是没有 $v$ 这个量的。也就相当于，我们在前面构造了 $343$ 行内容，都是与 $v$ 无关的。那么我们就可以分离处这个 $v$ （即将 $B=f(A)$ 的列固定，考察 $B$ 的每一列和 $A,F$ 的关系即可 ），构造的矩阵和前面无异，只是我们需要分离每一列，分别建立矩阵，去规约。

from subprocess import check_output
from re import findall
from sage.all import *

def flatter(M):  # flatter
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
A,B=C[0][0],C[0][1]
A=matrix(GF(p),15,15,A)
B=matrix(GF(p),15,15,B)
Aarr=[A**i for i in range(1,16)]
from datetime import *
for v in range(15):
    print(f'Round {1+v} start at',datetime.now())
    Mx=[[0 for _ in range(15)]for __ in range(225)]
    for u in range(15):
        for T in range(15):
            for i in range(15):
                Mx[15*T+i][u]=Aarr[T][u][i]
    Mx=matrix(Mx)
    M=block_matrix(ZZ,[
        [identity_matrix(225),Mx,zero_matrix(225,1)],
        [zero_matrix(15,225),-p*identity_matrix(15),zero_matrix(15,1)],
        [zero_matrix(1,225),-matrix((B.T)[v]),1]
    ])
    Mb=diagonal_matrix([1]*225+[2**2000]*15+[1])
    M3L=flatter(M*Mb)
    for vec in M3L:
        if(vec[-1] in [1,-1]):
            vec*=vec[-1]
            print(bytes(vec))

运行结果：

12.Matrix 9

题目很短，我们只知道 $B=f(A)$ 这一条信息，其中 $f$ 是一个 $10$ 次多项式。

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

n = 10
A = random_matrix(GF(2), n, n)
PR.<x> = PolynomialRing(GF(2))
B = PR.random_element(degree=n)(A)

print("B =", B.list())
print("enc =", AES.new(key=md5(str(A).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

这个题的话，真就属于不知道真就不知道，但知道了就很简单的题：因为 $B=f(A)$，那么就会有 $BA=AB$。

为啥？其实想到这个还是比较自然的：
$$
f(A)A=\left(\sum c_iA^i\right)A=\sum c_iA^{i+1}=A\sum c_iAi=Af(A)
$$
但如果反应不过来还真想不到。

那么后面就很简单了：既然 $BA=AB$，$A$ 未知，那就把 $A$ 看成 $X$，解方程 $BX=XB$，也就是 $BX-XB=O$。

设 $C=BX-XB$，那么可以得到等式：
$$
c_{uv}=\sum_{i=0}^9 b_{ui}x_{iv} - \sum_{i=0}^{9} b_{iv}x_{ui}
$$
构造出矩阵 $C$ 后，测试了一下， $r(C)=88$，即 $\mathrm {dim}K(C)=12$，而 $A$ 就是 $C$ 的核空间向量自由组合的结果。

由于是 $\mathbb F_{2}$ 上的运算，简单枚举一下，找到符合要求的解密结果就OK了。

B = [1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1]
enc = b'\xc7\xa19UlZ\xbb\x18\xdcb\x16\x8e,\x17\xd8\xc6\x12\xfc\xc69\xd6{\x01!-\xc1\xcb\xf0\x8ad\xbd\xef\xdeSy\xcc\xb2R\x0e\x95m'

B=matrix(GF(2),10,10,B)
M=[[0 for _ in range(100)]for __ in range(100)]

for u in range(10):
    for v in range(10):
        for i in range(10):
            M[u*10+v][10*i+v]+=int(B[u][i])
            M[u*10+v][10*u+i]-=int(B[i][v])
M=matrix(GF(2),M)

K=M.right_kernel().matrix()
Ks=[K[i] for i in range(K.nrows())]
from Crypto.Cipher import AES
from hashlib import md5
for i in range(2**len(Ks)):
    v=[bool(i&(1<<j)) for j in range(len(Ks))]
    A=sum([vi*ki for vi,ki in zip(v,Ks)])
    A=matrix(GF(2),10,10,A)
    s=(AES.new(key=md5(str(A).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(enc))
    if(all([s[i]<128 and s[i]>32 for i in range(12)])):
        print(s)
#b'NSSCTF{U31nG_C0mmut@t1vE_and_Bru7eF0rCe!}'

13.Matrix 9-2

和上个题差不多，依然是 $B=f(A)$，题目中只有 $B$，$A$ 未知。但这次换到了模 $p$ 上。

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

n = 10
p = getPrime(256)
A = Matrix(Zmod(p), n, n, pad(flag,n^2))
PR.<x> = PolynomialRing(Zmod(p))
B = PR.random_element(degree=n)(A)

print("p =", p)
print("B =", B.list())

看到这个 pad，就很明显地知道 $A$ 中所有元素不超过 $256$ 了，那肯定是构造矩阵然后LLL了。

还是使用上一题的式子：
$$
c_{uv}=\sum_{i=0}^9 b_{ui}x_{iv} - \sum_{i=0}^{9} b_{iv}x_{ui}
$$
计算 $C=BX-XB$，然后求 $K(C)$ （这里 $r(C)=90$），这里面所有向量的线性组合就构成了 $A$，也就是：
$$
\vec a_{100}\equiv \sum_{i=0}^{9}d_i\vec k_i \pmod p
$$
既然 $d_i$ 不知道，而 $A$ 的每个分量很小，并且是 $\vec k$ 的线性组合，想到第一题的矩阵

那不就可以搞一个类似的吗：

不过注意这边是 $110\times 100$ 的矩阵，因此 LLL 之后，目标向量在第 $11$ 行（从 $0$ 开始计数，$0\sim 10$ 行都是 $\vec 0$ ），如果正的解不出来，就给目标向量取负再试一次。

但最后实测发现，flag好像有几位解不出来，不过无伤大雅，还是能够推出来是什么内容的。

p=
B=

Bm=matrix(GF(p),1,100,B)
B=matrix(GF(p),10,10,B)
Mx=[[0 for _ in range(100)]for __ in range(100)]

for u in range(10):
    for v in range(10):
        for i in range(10):
            Mx[u*10+v][10*i+v]+=int(B[u][i])
            Mx[u*10+v][10*u+i]-=int(B[i][v])
Mx=matrix(GF(p),Mx)
K=Mx.right_kernel().matrix()

M=block_matrix(ZZ,[
    [K],
    [-p*identity_matrix(100)]
])
M3L=M.LLL()
s=(-M3L[11]) #
ans=''
for i in range(len(s)):
    if(s[i]>=32 and s[i]<=127):
        ans+=chr(s[i])
    else:
        ans+='.'
print(ans)
#.SSCTF{St1l.LLL111lllI.I_1n_th3_k.rn3L!}
#NSSCTF{St1llLLL111lllIII_1n_th3_k3rn3L!}

99.总结

这上面有些题目还是值得把玩一下的，比如 Matrix 6,8,8-2,9,9-2 这 5 个题目，不做一下里面涉及的技巧还真不一定知道。。。

所以CTF真的就是比谁会用Sage，以及谁trick多了吧。。平时还是得多接触接触一些trick，不然遇到题目，不知道trick，真就做不出来:(