糖醋小鸡块的blog
0%

2024-NSSCTF-Matrix_challenges-wp-crypto

发表于 更新于 分类于 Valine：

最近做到的一些矩阵题目对我启发很大，所以花了一个晚上和一个早上出了一共九道简单的小题目，做成了这个题单，给自己巩固的同时也给工坊群友做练习，欢迎各位师傅来玩：

Matrix_challenges | NSSCTF

输出大多都挺长，所以这篇wp统一不放output，去NSS上下载附件就好了，题目可能还会慢慢有更新。

Matrix_warm_up

题目：

1
2
3
4
5
6
7
8
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]))

题目给出256bit的素数p以及一个模p下的向量c，满足：

其中a未知，mi是flag的字符对应数值，qi是随机取的128bit的素数。

突破点显然在于向量m较小，所以用如下格：

这个格具有的线性关系是：

注意到这个格并不是一个方阵，这是因为a的逆元并不是一个模p意义下的小数字，所以我们没有必要规约他。而这种行>列的非方阵格会带来一个问题——格基并不是线性无关的，秩只有i，因此LLL会得到一行全0，故向量m会出现在第二行。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

p = 
c = 

L = block_matrix(ZZ,[
    [Matrix(ZZ,c)],
    [p]
])
res = L.LLL()[1]

for i in res:
    print(chr(abs(i // factor(i)[-1][0])),end="")


#NSSCTF{F1nd_@_s3cR3t_NUMBER_1s_eAsy_4_U}



Matrix1

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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())

题目将flag分为前后两部分，分别做随机字节填充使得其长度为100，并转化为模p下的10阶方阵M1、M2。之后生成模p下的随机矩阵A，并计算：

给出p、A、B，要求还原flag。

很明显的，M1、M2在模p下都是小值构成的矩阵，所以目标还是规约出他们。而M2的逆显然不是小值矩阵，为此先做个移项：

为了方便之后阐述，不妨记：

把所有矩阵写开：

可以看出对于任意一个C[i,j]，我们都可以理出对应的一条线性等式：

这个时候我们再消去c得到：

这样的等式一共有n^2个，把所有等式搜集起来，并组合成一个矩阵方程就是：

其中展平的M1、M2拼接起来的M显然是矩阵方程的解：

而由于L有n^2的右核，所以直接求矩阵方程会有无穷组解。然而M显然是这些解里比较小的，所以对右核的basis进行一次规约就可以找到M了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *
from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    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)))

############################################################################################### data
p = 
A = 
B = 

############################################################################################### exp
########################################## part1 to mat
n = 10
A, B = Matrix(Zmod(p), n, n, A), Matrix(Zmod(p), n, n, B)


########################################## part2 get solution of M1A = BM2
L = Matrix(Zmod(p), n^2, 2*n^2)
for i in range(n):
    for j in range(n):
        for t in range(n):
            L[n*i+j, n^2+n*i+t] -= A[t,j]
            L[n*i+j, j+n*t] += B[i,t]
XY = Matrix(ZZ,L.right_kernel().basis())


########################################## part3 LLL
L = Matrix(ZZ,2*n^2,2*n^2)
for i in range(n^2):
    for j in range(2*n^2):
        L[i,j] = XY[i,j]
        L[n^2+i,n^2+i] = p
#print(L.dimensions())
res = flatter(L)[0]


########################################## part4 get flag
m1 = res[n^2:n^2+16]
m2 = res[:16]
flag = ""
for i in m1:
    flag += chr(i)
for i in m2:
    flag += chr(i)
print(flag)


#NSSCTF{LLL111lll_1n_th3_k3rn3L!}

这个题很重要的一个思想是：不管是矩阵还是向量运算，运算操作都是线性的，因此可以随时随地把矩阵与向量做等价转换（也就是展平）来得到更清楚的线性等式，这一点在后面的题目中会反复用到。



Matrix1_v2

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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())

与Matrix1的区别在于，矩阵维数降低到了5，并且：

这一次M2没有求逆的操作，所以没有办法移项变成线性操作了。

而由于M1、M2都是flag编码矩阵，其中数值都在0-255，所以他们之中的数值相乘是个0-65536的量，依然是小量。所以我们的核心思路就是换元，把这个矩阵乘法中的二次项换元成0-65536的一次项去规约。

还是把矩阵乘法写开：

为了表示方便，用行向量表示M1矩阵，用列向量表示A矩阵，就有：

那么对于矩阵B任意位置(i,j)的量，有：

这就得到了我们需要的一组等式，接下来只需要把所有n^2个等式搜集起来，并把m1与m2对应乘积看成小量后做规约就可以得到所有二次项。

得到二次项之后，注意到B中同一行的所有数值其实是被相同的M1行向量和不同的M2的值加密的，所以作一下gcd就可以恢复M1的所有值，恢复M1后自然就恢复了M2。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from Crypto.Util.number import *
from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    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)))

############################################################################################### data
p = 
A = 
B = 

############################################################################################### exp
########################################## part1 to mat
n = 5
A = Matrix(Zmod(p), n, n, A)

########################################## part2 flatten
FA = []
for i in range(n):
    for j in range(n):
        FA.append(A[j,i])

FFA = []
for i in range(n^2):
    temp = [0]*n^2*i + FA + [0]*(n^4-n^2*i-n^2)
    FFA.append(temp)


########################################## part3 LLL
L = block_matrix(ZZ, [
    [1,Matrix(ZZ,FFA).T.stack(-vector(B))],
    [0,p]
]
)
L[:,-n^2:] *= p
#print(L.dimensions())
res = flatter(L)


########################################## part4 recover M1
for i in res:
    if(all(j == 0 for j in i[-n^2:]) and abs(i[-n^2-1]) == 1):
        ans = i[:-n^2-1]
        
        M1 = Matrix(Zmod(p), n, n)
        for j in range(n):
            temp = ans[:n^2]

            for k in range(n):
                mjk = gcd(ans[0+k], ans[n+k])
                for r in range(1,n-1):
                    mjk = gcd(mjk, gcd(ans[r*n+k], ans[(r+1)*n+k]))
                M1[j,k] = mjk
            
            ans = ans[n^3:]
        print(M1)
        break


########################################## part5 recover M2
B = Matrix(Zmod(p), n, n, B)
M2 = A^(-1)*M1^(-1)*B


########################################## part6 get flag
def flatten(M):
    M_flatten = []
    rows,cols = M.dimensions()
    for i in range(rows):
        for j in range(cols):
            M_flatten.append(M[i,j])
    return M_flatten

for i in flatten(M1):
    print(chr(i), end="")
print()
for i in flatten(M2):
    print(chr(i), end="")


#NSSCTF{M@k3_N0n_L1ne@r_L1ne@r!}



Matrix2

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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))

题目仍然先随机生成一个256bit的素数p，之后生成一个长为flag长度的列表secret，其中每个元素都是模p下的随机值，记他为：

传secret进入encrypt加密，加密步骤主要是：

  • 生成两个矩阵，满足：

  • 当L和R都满秩时（其实也就是L的所有向量线性无关），返回下面矩阵作为密文：

    其中e是”Tequila”对应的整数值

  • 以列表secret的和的md5值作为AES的key加密flag，得到enc

给出p、C、enc，要求还原flag。

由于L和R的列向量之间的关系实在是太引人注意了，所以我们先不考虑这个加密指数e的话，可以假设一个A满足：

这也就是：

随便取一条列向量来看就是：

可以看出两个事实：

  • L中的所有列向量是A的特征向量
  • secret中的所有值是A的特征值

而我们现在有：

为了利用这一点，做以下推导：

若矩阵A满足：

则$\lambda$是A的特征值，$\textbf{x}$是A的特征向量，而对于A^2则有：

以此类推就得到：

得到结论：

  • A和A^n的特征向量相同
  • A^n的特征值是A对应特征值的n倍

把结论作用在这个题目就有：

  • C的特征值是A的特征值的e倍，也就是si^e

而特征值是模p下的一个数字，所以有：

所以我们只需要求e关于p-1的逆d，然后将C的所有特征值做d次方之后求和就可以得到sum(secret)，之后就可以解AES得到flag。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5

############################################################################################### data
p = 
C = 
enc = 

############################################################################################### exp
########################################## part1 to mat
n = int(pow(len(C),1/2))
C = Matrix(GF(p), n, n, C)


########################################## part2 find eigenvalues and flag
res = C.eigenvalues()
e = bytes_to_long(b"Tequila")
key = 0
for i in res:
    key += int(pow(i,inverse(e,p-1),p))

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


#NSSCTF{A_S1mPl3_e1g3nVa1ue5_tr1ck!}



Matrix3

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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())

题目将flag编码为模p下的n阶方阵M，并随机生成一个同样由0-255以内数值组成的n阶矩阵e，之后生成模p下的随机矩阵W、X、Y、Z，并计算：

给出p、W、X、Y、Z、C，要求还原明文。

由于W、X、Y、Z全都知道，所以简化一下也就有：

M和e在模p下都很小，所以看上去是个LWE。然而常见的LWE一般是这种形式：

相比于上面的等式来说主要有两个区别：

  • M、e都是矩阵而非向量
  • M还右乘了一个随机矩阵B

而正如Matrix1的wp中最后一点所讲，矩阵的操作都是线性的，我们完全可以将他转化成向量的操作，所以这题的主要问题就在于怎么将矩阵展平成向量。

做一下下述处理的话，可以转化成Matrix1的类似问题：

这题我们换个思路，直接硬来

我们仍然把矩阵写开，便于观察：

可以发现把C、e两部分展平成向量很容易：

因此我们主要关注的是下面这部分如何展平：

仍然是任取一个位置(i,j)来构建对应的线性等式：

也就是：

如此一来我们就将M也展平成向量放进线性等式中了。可以发现这样一条线性等式其实已经包含了M的所有值，所以如果M中值够小的话（比如0、1），那么其实给C的其中一个值或许都可以规约出来。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from Crypto.Util.number import *
from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    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)))

############################################################################################### data
p = 
W = 
X = 
Y = 
Z = 
C = 


############################################################################################### exp
########################################## part1 to mat
n = 10
W, X, Y, Z, C = Matrix(Zmod(p),n,n,W), Matrix(Zmod(p),n,n,X), Matrix(Zmod(p),n,n,Y), Matrix(Zmod(p),n,n,Z), Matrix(Zmod(p),n,n,C)


########################################## part2 flatten
def flatten(M):
    M_flatten = []
    rows,cols = M.dimensions()
    for i in range(rows):
        for j in range(cols):
            M_flatten.append(M[i,j])
    return M_flatten

E = W*X
F = Y*Z
EF = []
for i in range(n):
    for j in range(n):
        temp = []
        for k in range(n):
            for m in range(n):
                temp.append(F[m,j]*E[i,k])
        EF.append(temp)

EF = Matrix(Zmod(p), EF)
CC = Matrix(Zmod(p), flatten(C)).T


########################################## part3 LWE
L = block_matrix(
    [
        [matrix.identity(n^2)*p, matrix.zero(n^2, n^2+1)],
        [(matrix(EF).T).stack(-vector(CC)).change_ring(ZZ), matrix.identity(n^2+1)],
    ]
)
#print(L.dimensions())
res = flatter(L)[0]
flag = ""
for i in res:
    flag += chr(abs(i))
print(flag)


#NSSCTF{fl@tt3n_4nd_LWE!}



Matrix4

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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())

与Matrix2很相似，只是这一次L和R变成了：

其中si依然是模p下未知的随机数，然后计算：

给出p、C，要求还原明文。

仍然令：

我们知道A的其中一个特征向量就是m，而又因为：

由Matrix2中的推导可知，C的特征向量就是A的特征向量，因此我们求C的特征向量，其中有一个应该就是m了。

然而我们会遇到一个问题就是，虽然有：

但是也有：

也就是特征向量的任意倍数（非0）也是特征向量，而我们直接用sage求出来的也确实是k倍的m，而不是原向量。

但是由于m较小，所以现在正好转化成了warm_up的相同的问题，因此只需要对求出来的特征向量逐个尝试规约就行。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *

############################################################################################### data
p = 
C = 


############################################################################################### exp
########################################## part1 to mat
n = int(pow(len(C),1/2))
C = Matrix(GF(p), n, n, C)

########################################## part2 find eigenvectors
L = []
res = C.eigenvectors_right()
for i in res:
    eigenvalue = i[0]
    eigenvector = i[1][0]
    L = block_matrix(ZZ,[
        [Matrix(ZZ,eigenvector)],
        [p]
    ])
    res = L.LLL()[1]
    if(abs(res[0]) < 128):
        for i in res:
            print(chr(abs(i)),end="")
        break


#NSSCTF{AnotHer_S1mPl3_EIGeNVecT0Rs_tr1ck!}



Matrix5

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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())

本题仍然基于特征向量和特征值，这一次L、R变成：

仍然记：

对于本题的C来说，题意在于他的每一个特征向量的某个k倍，其最后五个值会是flag的片段。

我们不妨记我们直接求出的某个特征向量为$\textbf{l}$，那么就有：

其中k我们并不知道，vi中的值是模p下的随机量，只有最后五个值，也就是m的片段在模p下才是小量，所以我们也取$\textbf{l}$的最后五维向量片段，仍然做warm_up的规约，就可以得到所有片段了。

此时得到的明文片段是无序的，然而由于相邻的片段会有四个字符的重合，所以从已知的flag头”NSSC”出发检查所有片段的重合字符数量就可以还原flag。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from Crypto.Util.number import *

############################################################################################### data


############################################################################################### exp
########################################## part1 to mat
n = int(pow(len(C),1/2))
def to_mat(M):
    mat = []
    for i in range(n):
        temp = []
        for j in range(n):
            temp.append(M[n*i+j])
        mat.append(temp)
    return Matrix(Zmod(p), mat)
C = Matrix(GF(p),to_mat(C))

########################################## part2 find eigenvectors
L = []
res = C.eigenvectors_right()
flag_pad = []
for i in res:
    eigenvalue = i[0]
    eigenvector = i[1][0]
    L = block_matrix(ZZ,[
        [Matrix(ZZ,eigenvector[-5:])],
        [p]
    ])
    res = L.LLL()[1]
    temp = ""
    for i in res:
        temp += chr(abs(i))
    flag_pad.append(temp)

prefix = "NSSC"
flag = "NSSC"
for i in range(n+3):
    for j in flag_pad:
        if(j[:4] == prefix[-4:]):
            flag += j[-1]
            prefix = j
            break
print(flag)


#NSSCTF{U_h4Ve_C0mp1et3d_H@lF_0f_MATRIX_cha1LenGe5!}

如果特征向量中只有最后一个字符是flag的话，这个方法是做不了的，原因如下：

  • 无法还原顺序

  • 造出的格是：

    一定会有：

    这个向量短于作为字符的mi，所以找不到解

如果特征向量只有最后两个字符是flag的话，顺序的问题基本得到解决，题目就可以解出了，只是要注意一下下面这一点，也就是格为：

期望的目标向量是：

在两个字符的数值互素时这样当然没有问题，然而如果两个字有最大公约数d，那么找到的解应该是：

所以找的时候还要小爆一下d才行，但是这个步骤感觉没有什么必要，因此最后是每五个字符作为一个片段，这样基本上就不会有公约数的问题了。



Matrix6

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)

题目改编自：

2024-江西省第三届天使杯网络安全技能大赛线上预选赛-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

本题相比于这个题目也就加了个小trick，前面的部分可以参考上篇文章，这里直接从插值的部分开始，我们有：

这是一个非齐次方程，由于我们知道这个矩阵方程存在解，为m和g和多项式g(x)的系数，所以其系数矩阵的秩等于增广矩阵的秩，因此有增广矩阵不满秩，所以有：

所以我们获得了一个在模n下以m为根的多项式。

而我们同时还有一个以m为根的多项式h：

所以两个多项式求一求gcd就好了。

问题在于L中每个f的度都很大，所以直接求L的行列式并不现实(度太大了，多项式都建不出来)。但处理方法也很熟悉，只需要在模h(x)的商环下去做就行。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from Crypto.Util.number import *
from tqdm import *

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

############################################################################################### data
n = 
c = 
F = 
C = 


############################################################################################### exp
nums = 10
e = 1337
PR.<x> = PolynomialRing(Zmod(n))
PRq.<a> = PR.quo(x^e-c)
L = Matrix(PRq,nums+1,nums+1)
for i in trange(nums+1):
    f = F[i]
    ci = C[i]
    temp = 0
    for j in range(nums):
        temp += f[j][0] * a^f[j][1]
    for j in range(nums):
        L[i,j] = temp^j
    L[i,-1] = ci

m = -gcd(L.det().lift(), x^e-c)[0]
print(long_to_bytes(int(m)))


#NSSCTF{L@graNge_InterP0lati0n_w1Th_QUoT1enT}



Matrix7

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

题目先生成了一个长度为10的矩阵列表f，其中第一个矩阵为flag编码的编码矩阵，后面9个是模p下的随机矩阵。这个列表f其实相当于一个度为10的多项式系数，也就是对于任意一个输入矩阵A，经过F会计算：

注意两点：

  • 这个多项式度为n，没有0次项
  • 这个多项式对于系数F来说是右乘（换成左乘题目依然可以做，只是需要注意一下）

在此基础上，题目给了10组点对：

我们需要还原出矩阵列表f，从而找到作为一次项系数矩阵的flag编码矩阵。

这显然依然是要做插值来恢复系数，回顾一下前面的内容，我们已经做过了以下两种插值：

  • 点对为数值：$(x,y)$
  • 点对为函数：$(f(x), g(x))$

而现在我们的点对变成了矩阵。

不过方法还是没有变，依然写出插值需要的矩阵方程然后解就可以了：

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *

############################################################################################### data
p = 
C = 


############################################################################################### exp
n = 10
L = Matrix(Zmod(p), 0, n^2)
R = Matrix(Zmod(p), 0, n)
for i in range(n):
    Ai = Matrix(Zmod(p), n, n, C[i][0])
    Ci = Matrix(Zmod(p), n, n, C[i][1])
    temp = Ai
    R = R.stack(Ci)
    for j in range(1,n):
        temp = temp.augment(Ai^(j+1))
    L = L.stack(temp)

F = L.solve_right(R)
M = F[:n]
for i in range(n):
    for j in range(n):
        print(chr(M[i,j]), end="")


#NSSCTF{M@tRiX_L4granGe_InterP0lati0n_1Sn't_H4rD}



Matrix8

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

和Matrix7一样，依然基于矩阵多项式，区别在于：

  • 并没有给出足够的数据进行插值，仅仅给了一组矩阵点对
  • 系数矩阵列表f全部为flag编码矩阵

系数矩阵在模p下很小，所以要用格，我们现在拥有的矩阵方程是：

最简单的思路就是我们把这个矩阵方程展平，然后LLL即可。注意到F共有n个n阶方阵，代表着n^3个变量，因此选7已经要规约接近400维的方阵，因此才将n改为7便于展平规约。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from Crypto.Util.number import *
from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    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)))

def flatten(M):
    M_flatten = []
    rows,cols = M.dimensions()
    for i in range(rows):
        for j in range(cols):
            M_flatten.append(M[i,j])
    return M_flatten

############################################################################################### data
p = 
C = 


############################################################################################### exp
n = 7
t = 1
def matrix_lagrange_LLL(n, t, PT, p):   
    ##### part1 flatten Ci to R
    R = []
    for i in range(t):
        C = flatten(Matrix(Zmod(p), n, n, PT[i][1]))
        for j in C:
            R.append(j)
    R = vector(Zmod(p), R)
    
    
    ##### part2 get L
    L = Matrix(Zmod(p), t*n^2, n^3)
    for r in range(t):
        A = Matrix(Zmod(p), n, n, PT[r][0])
        for j in range(n):
            for k in range(n):

                for i in range(n):
                    Ai = A^(i+1)
                    for x in range(n):
                        L[n^2*r+n*j+k,n^2*i+n*k+x] = Ai[j,x]

    
    ##### part3 LLL
    M = block_matrix(ZZ,[
        [1,Matrix(ZZ,L).T.stack(Matrix(ZZ,R))],
        [0,p]
    ])
    M[:,-t*n^2:] *= p
    #print(M.dimensions())
    res = flatter(M)[0][:n^2]
    for i in range(n):
        for j in range(n):
            print(chr(res[n*j+i]), end="")


matrix_lagrange_LLL(n, t, C, p)


#NSSCTF{Y3t_4n0Th3r_L@graNge_InterP0lati0n_TasK}

但是这个方法显然并不好，因为我们人为的增大了格的维数，好一些的方法继续看v2



Matrix8_v2

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

对比Matrix8，唯一的区别在于矩阵的维数从7增大到了15，这使得我们展平后的F向量长度达到了15^3=3375，显然不能直接规约了。

我们依然从矩阵方程出发：

我们把F和C的矩阵用列向量形式来表示：

那么矩阵方程变成：

可以看出各个列向量之间其实是独立的，所以我们完全可以按如下方式逐个恢复列向量：

这样相比于全部展平的矩阵，维数从n^3降低到了n^2，规约n次即可。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import *
from tqdm import *
from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    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)))


############################################################################################### data
p = 
C = 


############################################################################################### exp
############################################## part1 construct matrix equation
n = 15
L = Matrix(Zmod(p), 0, n^2)
R = Matrix(Zmod(p), 0, n)
for i in range(1):
    Ai = Matrix(Zmod(p), n, n, C[i][0])
    Ci = Matrix(Zmod(p), n, n, C[i][1])
    temp = Ai
    R = R.stack(Ci)
    for j in range(1,n):
        temp = temp.augment(Ai^(j+1))
    L = L.stack(temp)

############################################## part2 LLL
F1 = []
for i in trange(n):
    L1 = Matrix(ZZ,L)
    R1 = R[:,i:i+1]
    M = block_matrix(ZZ,[
        [1,L1.T.stack(Matrix(R1).T)],
        [0,p]
    ])
    M[:,-n:] *= p
    res = flatter(M)[0][:n]
    F1.append(list(map(abs,res)))


############################################## part3 recover F1
for i in range(n):
    for j in range(n):
        print(chr(F1[j][i]), end="")
    

#NSSCTF{d1m3nSi0n_1s_n0T_A_pr0B13m_FOr_th1S_T@sK}



Matrix9

题目：

1
2
3
4
5
6
7
8
9
10
11
12
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))

本题基于GF(2)下的矩阵运算，加密流程为：

  • 生成一个n维随机矩阵A

  • 生成一个度为10的随机多项式f

  • 计算：

  • 仅给出B，要求还原A，从而解AES密文得到flag

本题一个很重要的trick在于可交换矩阵，对于任意的多项式f，我们有：

所以我们有：

因此我们解下面的矩阵方程：

得到的kernel是n维的，因此小爆一下kernel其中就存在A，就可以解密得到flag了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *
from itertools import *
from Crypto.Cipher import AES
from hashlib import md5

############################################################################################### data
B =
enc = 


############################################################################################### exp
########################################## part1 to mat
n = 10
B = Matrix(GF(2), n, n, B)


########################################## part2 get solution of BA = AB
L = Matrix(GF(2), n^2, n^2)
for i in range(n):
    for j in range(n):
        for t in range(n):
            L[n*i+j, n*i+t] += B[t,j]
            L[n*i+j, j+n*t] -= B[i,t]
Ker = L.right_kernel().basis()


########################################## part3 bruteforce for A
def recover(A_flatten, n, p):
    A = Matrix(Zmod(p), n, n)
    for i in range(n):
        for j in range(n):
            A[i,j] = A_flatten[n*i+j]
    return A

for i in product([0,1], repeat=len(Ker)):
    A = Matrix(GF(2), n, n)
    for j in range(len(Ker)):
        A += recover(i[j]*Ker[j], n, 2)
    flag = AES.new(key=md5(str(A).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(enc)
    if(b"NSSCTF" in flag):
        print(flag)
        break


#NSSCTF{U31nG_C0mmut@t1vE_and_Bru7eF0rCe!}



Matrix9_v2

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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())

相比于Matrix9，本题变化为：

  • 回到了256bit的素数域
  • A变成了flag的编码矩阵

而由上题经验我们应该知道A依然是下面矩阵方程的解：

而A又很小，那么思路就很简单了——LLL！

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *

############################################################################################### data
p = 
B = 


############################################################################################### exp
########################################## part1 to mat
n = 10
B = Matrix(Zmod(p), n, n, B)


########################################## part2 get solution of BX = XB
L = Matrix(Zmod(p), n^2, n^2)
for i in range(n):
    for j in range(n):
        for t in range(n):
            L[n*i+j, n*i+t] += B[t,j]
            L[n*i+j, j+n*t] -= B[i,t]
T = Matrix(Zmod(p), L.right_kernel().basis())


########################################## part3 LLL
T = block_matrix(ZZ,[
    [T],
    [p]
])
res = T.LLL()[n+1]
for i in res:
    if(abs(i) < 128 and abs(i) > 32):
        print(chr(abs(i)), end="")
    else:
        print("*", end="")

#*SSCTF{St1l*LLL111lllI*I_1n_th3_k*rn3L!}
#NSSCTF{St1llLLL111lllIII_1n_th3_k3rn3L!}