抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

正交格

crypto日常学习

发布于：2024年12月25日

次浏览

首先了解一下有关右核空间和左核空间的概念

image-20241224180324898

image-20241224162858240

下面介绍几道相关的题目

题1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#sage
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5
import os
FLAG = os.environ.get("FLAG", "ctfpunk{XXX_FAKE_FLAG_XXX}")

m = 8
n = 16
p = random_prime(2^512)
A = matrix(ZZ, m, n, [randint(-8, 8) for _ in range(m*n)])
alpha = vector(Zmod(p), [randint(0, p-1) for _ in range(m)])
B = alpha*A
key = md5(str(A.LLL()[0]).encode()).digest()
c = AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG.encode(), 16)).hex()
print(f"{p = }")
print(f"{B = }")
print(f"{c = }")
"""
p = 7064984525561049833941455975315226062215100031502799222949438013406933213082068867354036190111862807403852790782169608415945334428256205825536265168993973
B = (6987440969759551353324677044999675737478126165510769544641525950312340465193691011136383575459117912622463499210240058765919716935919792151451368790904779, 538501908287016811770814963869685588636459507797312498284354257994183787357905990712386568881195466207490578273886998862874804517050990895004493276622276, 4124700208764334513441041531109970827407619648924057630248643329941250298226684483835309006912271794287221844326010511009880926888582259293308874125209877, 1615413470791777172379323594442031980292585267892079844004183034341437946970488889566801194517266423798228232900016427804210664190615250548086969042194055, 4453186502956586735169761657773894925807402254863319717550428624608132045603657281631438493339928635626807899844397961244294365141137080375145978997162407, 6565297672673205366900244325925091704172709184740810263912769943991146161592510244188212998365337366799449944806144562811282170199815376100544325738733703, 1082053880848206246726144084651304123017961124487218546982771854226794920852362975101989964225092310302907400526821842093804607949373873172750421436163130, 707884557268649511183729198708049152610268391656383463908475012939759581261144538094163601701830391103878546436147413922244554897338703575756816396973108, 1472673584290904041194662509179596920341470146210177446004553787904580153104167642987022353312828664564561950541911131984067380572588601476553014264896958, 386126396470902821152131060129593655531616414683521247932592997234654538269464964653091784064790712577097306279712523790073065938893701108104371593190803, 2074128829325519904811849727958434498966441498530579789542382644345388219184360798023203260112646258446112696224286738764577717685929070971045878859298331, 5005696223266177218949847645750647510805747805303156551048184881164677033778700367030717404660127773709053114311640483128611645614441966336013368064152709, 499402862374637565500719745355889892944053567112997684075016072023661464527102673694443235571624833161355323814432566640883825055442487521153172951492084, 2644251123569446715688240316036367098663434133248552246336537366670452536527388132412221201540681300060695922122106419325792546232222449697523053183087366, 837532276539709830888899573089652001142615822398174430524163703591884616290441133332639039580178431384615448154994439512821967333004008882702386597272711, 3743627786813483303995800702852963206656602981404111956128499594153025373806112629265678889858113778648805990248747256067691240913712516523978237984936878)
c = '409a6ce08fbc0f66667b6d14e593ea8df3dad5052de7ac1ab592b43237fde2d8bae740dbea10b722557c3579126b6cfe'
"""

对于这题，很明显有

al1×8∗A8×16=B1×16al_{1\times 8} * A_{8\times 16} = B_{1\times 16}

这边的A矩阵都是小量，很明显是格的方向来想

转置一下，有

B16×1T=A16×8T∗al8×1TB^{T}_{16\times 1} = A^{T}_{16\times 8} * al^{T}_{8\times 1}

如果我们能找到一个矩阵M，满足M∗B16×1T=M∗A16×8T∗al8×1T=0M*B^{T}_{16\times 1} = M * A^{T}_{16\times 8} * al^{T}_{8\times 1} = 0，很明显该矩阵M应该是A16×8TA^{T}_{16\times 8}的左核空间才行（因为B16×1TB^{T}_{16\times 1}本身是没有核空间的），根据秩-零性定理，那么这矩阵M的维度应该是8×168 \times 16

但是这边我们不知道A16×8TA^{T}_{16\times 8}，所以这边只能利用B16×1TB^{T}_{16\times 1}来造一个格来得到近似的结果（因为LLL规约算法他是得到近似正交的基向量，并不一定要完全正交），很容易想到可以构造如下的格（一个非常非常重要的点！经过多次测试，这个格不需要规约！规约了反而会得不到预期的结果）

[I16×16B16×1T016×1p]\begin{bmatrix} I_{16\times 16} & B^{T}_{16\times 1}\\ 0_{16\times 1} & p \end{bmatrix}

对于M的每组基向量，很明显有

( m1, m2, m3, ..., m16, k)[I16×16B16×1T016×1p]=( m1, m2, m3, ..., m16, 0)(\ m_1,\ m_2,\ m_3,\ ...,\ m_{16},\ k) \begin{bmatrix} I_{16\times 16} & B^{T}_{16\times 1}\\ 0_{16\times 1} & p \end{bmatrix} = (\ m_1,\ m_2,\ m_3,\ ...,\ m_{16},\ 0)

所以我们只要对规约结果进行检验，满足一个是0的就是我们所需要的基向量

这边在本地测试的话，会发现这个规约出来的近似M就是我们所要寻找的M

通过如下的代码验证：

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
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5

m = 8
n = 16
p = random_prime(2^512)
A = matrix(ZZ, m, n, [randint(-8, 8) for _ in range(m*n)])
alpha = vector(Zmod(p), [randint(0, p-1) for _ in range(m)])
B = alpha*A
B = Matrix(ZZ, 1, 16, B.list())



#构造对应的块矩阵
L = block_matrix([
                [identity_matrix(16), B.T], 
                [matrix.zero(1, 16), p]
])  #不需要规约

res1 = L.LLL()
M = []
#寻找满足条件的正交向量，一般来说会和我们要求的矩阵（这边是A）一样大，有8组，每组十六个
for i in res1:
    if i[-1] == 0:
        M.append(i[:-1])
    else:
        continue
M = Matrix(ZZ, 8, 16, M)
print(M * A.T)

'''
[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]
'''

到这边求出矩阵M之后有两种做法

格做法

此时我们很明显有

M8×16∗A16×8T=0M_{8\times 16} * A^{T}_{16\times 8}=0

转置一下，很明显有

A8×16∗M16×8T=0A_{8\times 16} * M^{T}_{16\times 8}=0

因为这边A是短向量，很明显只要构造出如下的格就可以规约出A（记住右下角是方阵就很容易构造）

[I16×16M16×8T08×16I8×8∗p]\begin{bmatrix} I_{16\times 16} & M^{T}_{16\times 8}\\ 0_{8\times 16} & I_{8\times 8} *p \end{bmatrix}

该格满足

( a1, a2, a3, ..., a16, k1, k2, ..., k8)[I16×16M16×8T08×16I8×8∗p]=( a1, a2, a3, ..., a16, 0, 0, ..., 0)(\ a_1,\ a_2,\ a_3,\ ...,\ a_{16},\ k_1,\ k_2,\ ...,\ k_8) \begin{bmatrix} I_{16\times 16} & M^{T}_{16\times 8}\\ 0_{8\times 16} & I_{8\times 8} *p \end{bmatrix} = (\ a_1,\ a_2,\ a_3,\ ...,\ a_{16},\ 0,\ 0,\ ...,\ 0)

或者下面这个格

[I16×16M16×8T]\begin{bmatrix} I_{16\times 16} & M^{T}_{16\times 8} \end{bmatrix}

该格满足

( a1, a2, a3, ..., a16)[I16×16M16×8T]=( a1, a2, a3, ..., a16, 0, 0, ..., 0)(\ a_1,\ a_2,\ a_3,\ ...,\ a_{16}) \begin{bmatrix} I_{16\times 16} & M^{T}_{16\times 8} \end{bmatrix} = (\ a_1,\ a_2,\ a_3,\ ...,\ a_{16},\ 0,\ 0,\ ...,\ 0)

两个格，本地测试都是可以的

实现代码如下：

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
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5


m = 8
n = 16
p = random_prime(2^512)
A = matrix(ZZ, m, n, [randint(-8, 8) for _ in range(m*n)])
alpha = vector(Zmod(p), [randint(0, p-1) for _ in range(m)])
B = alpha*A
B = Matrix(ZZ, 1, 16, B.list())



#构造对应的块矩阵
L = block_matrix([
                [identity_matrix(16), B.T], 
                [matrix.zero(1, 16), p]
])

res1 = L.LLL()
M = []
#寻找满足条件的正交向量，一般来说会和我们要求的矩阵（这边是A）一样大，有8组，每组十六个
for i in res1:
    if i[-1] == 0:
        M.append(i[:-1])
    else:
        continue
M = Matrix(ZZ, 8, 16, M)
# print(M * A.T)


# L1 = block_matrix([[identity_matrix(16), M.T], 
#                    [Matrix(ZZ, 8, 16), identity_matrix(8) * p]]) * diagonal_matrix(ZZ, [1] * 16 + [p] * 8)

L1 = block_matrix([[identity_matrix(16), M.T]]) * diagonal_matrix(ZZ, [1] * 16 + [p] * 8)

my = L1.LLL()


for i in my:
    if all(j == 0 for j in i[-8::]) and all(-8 <= j <=8 for j in i[:16:]):
        print(i[:-8:])
print(A)



这边对比以下发现确实不能完全规约出矩阵A，而且顺序也不固定，但是在8条基向量中可以规约出4条以上

因为这道题也不要求我们得到矩阵A，他是用A.LLL()[0]来作为AES加密的密钥，那我们就可以利用这些满足条件的基向量去规约得到，对比一下真正的矩阵A，看看两者的差距，如果有差距稍微线性组合一下包能出，一样的话就不需要了

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
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5


m = 8
n = 16
p = random_prime(2^512)
A = matrix(ZZ, m, n, [randint(-8, 8) for _ in range(m*n)])
alpha = vector(Zmod(p), [randint(0, p-1) for _ in range(m)])
B = alpha*A
B = Matrix(ZZ, 1, 16, B.list())



#构造对应的块矩阵
L = block_matrix([
                [identity_matrix(16), B.T], 
                [matrix.zero(1, 16), p]
])

res1 = L.LLL()
M = []
#寻找满足条件的正交向量，一般来说会和我们要求的矩阵（这边是A）一样大，有8组，每组十六个
for i in res1:
    if i[-1] == 0:
        M.append(i[:-1])
    else:
        continue
M = Matrix(ZZ, 8, 16, M)


# L1 = block_matrix([[identity_matrix(16), M.T], 
#                    [Matrix(ZZ, 8, 16), identity_matrix(8) * p]]) * diagonal_matrix(ZZ, [1] * 16 + [p] * 8)

L1 = block_matrix([[identity_matrix(16), M.T]]) * diagonal_matrix(ZZ, [1] * 16 + [p] * 8)

my = L1.LLL()

A_ = []
for i in my:
    if all(j == 0 for j in i[-8::]) and all(-8 <= j <=8 for j in i[:16:]):
        A_.append(i[:-8:])


A_ = Matrix(ZZ, A_)
print(A_.LLL()[0])
print(A.LLL()[0])


'''
(-1, -8, 6, -4, -2, 4, 0, -4, 0, 1, 7, -4, -1, 5, 2, 0)
(-1, -8, 6, -4, -2, 4, 0, -4, 0, 1, 7, -4, -1, 5, 2, 0)
'''

发现是一样的，由此我们即可解AES拿到flag

核空间做法

根据上面的推导，我们很明显有

此时我们很明显有

M8×16∗A16×8T=0A8×16∗M16×8T=0\begin{array}{l} M_{8\times 16} * A^{T}_{16\times 8}=0\\ A_{8\times 16} * M^{T}_{16\times 8}=0 \end{array}

所以这边有个很直接的想法，求M8×16M_{8\times 16}的右核空间或者M16×8TM^{T}_{16\times 8}的左核空间

虽然也并不能求出矩阵A，但是也可以做到LLL规约之后和原先的矩阵A是一样的

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
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5


m = 8
n = 16
p = random_prime(2^512)
A = matrix(ZZ, m, n, [randint(-8, 8) for _ in range(m*n)])
alpha = vector(Zmod(p), [randint(0, p-1) for _ in range(m)])
B = alpha*A
B = Matrix(ZZ, 1, 16, B.list())



#构造对应的块矩阵
L = block_matrix([
                [identity_matrix(16), B.T], 
                [matrix.zero(1, 16), p]
])

res1 = L.LLL()
M = []
#寻找满足条件的正交向量，一般来说会和我们要求的矩阵（这边是A）一样大，有8组，每组十六个
for i in res1:
    if i[-1] == 0:
        M.append(i[:-1])
    else:
        continue
M = Matrix(ZZ, 8, 16, M)


print(M.right_kernel().matrix().LLL()[0])
print(A.LLL()[0])

print()


print(M.T.left_kernel().matrix().LLL()[0])
print(A.LLL()[0])


'''
(4, -1, 0, 3, 5, 2, 1, -1, 5, 4, 5, -7, 1, -2, 6, -2)
(4, -1, 0, 3, 5, 2, 1, -1, 5, 4, 5, -7, 1, -2, 6, -2)

(4, -1, 0, 3, 5, 2, 1, -1, 5, 4, 5, -7, 1, -2, 6, -2)
(4, -1, 0, 3, 5, 2, 1, -1, 5, 4, 5, -7, 1, -2, 6, -2)
'''

在sage里面，求核空间的速度是比较慢的，这边维度小体现不出来，如果维度大了，差距就会比较明显了

所以这边推荐还是格做法，因为如果给你限时了，格还是能做的

具体可以看下面这题

题2

加密代码：

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
from sage.modules.free_module_integer import IntegerLattice
from Crypto.Cipher import AES
from base64 import b64encode
from hashlib import *
from secret import flag
import signal

n = 75
m = 150
r = 10
N = 126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109

def gen(n, m, r, N):
    t1 = [ZZ.random_element(-2^15, 2^15) for _ in range(n*m)]  #75 * 150
    t2 = [ZZ.random_element(N) for _ in range(r*n)]  #10 * 75
    B = matrix(ZZ, n, m, t1)  #75 * 150
    L = IntegerLattice(B)
    A = matrix(ZZ, r, n, t2)  #10 * 75
    C = (A * B) % N
    return L, C

def pad(s):
    return s + (16 - len(s) % 16) * b"\x00"

#signal.alarm(60)
#token = input("team token:").strip().encode()  这题主要是练习，省略靶机交互流程

L, C = gen(n, m, r, N)
print(C)
key = sha256(str(L.reduced_basis[0]).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
ct = b64encode(aes.encrypt(pad(flag))).decode()
print(ct)

题目给了如下信息

A10×75∗B75×150=C10∗150A_{10\times 75} * B_{75\times 150} = C_{10 * 150}

要我们求B，这边的B里面的元素都是小量

参考上题，做法如下：

C150∗10T=B150×75T∗A75×10TC^{T}_{150 * 10}= B^{T}_{150\times 75} * A^{T}_{75\times 10}

找到一个矩阵M75×150M_{75\times 150}，满足

M75×150∗C150∗10T=M75×150∗B150×75T∗A75×10T=0M_{75\times 150}*C^{T}_{150 * 10}= M_{75\times 150}*B^{T}_{150\times 75} * A^{T}_{75\times 10}=0

构造如下的格（这个格不需要规约！）：

[I150×150C150×10T010×150p10∗10]\begin{bmatrix} I_{150\times 150} & C^{T}_{150\times 10}\\ 0_{10\times 150} & p_{10*10} \end{bmatrix}

该格满足

( m1, m2, m3, ..., m150, k1, k2, …, k10)∗[I150×150C150×10T010×150p10∗10]=( m1, m2, m3, ..., m150, 0, 0, …, 0⏟10个)(\ m_1,\ m_2,\ m_3,\ ...,\ m_{150},\ k_1,\ k_2,\ \dots,\ k_{10}) * \begin{bmatrix} I_{150\times 150} & C^{T}_{150\times 10}\\ 0_{10\times 150} & p_{10*10} \end{bmatrix} = (\ m_1,\ m_2,\ m_3,\ ...,\ m_{150},\underbrace{\ 0,\ 0,\ \dots,\ 0}_{10\text{个}})

此时有

M75×150∗B150×75T=0M_{75\times 150}*B^{T}_{150\times 75} =0

转置一下，有

B75×150∗M150×75T=0B_{75\times 150} * M^{T}_{150\times 75}=0

构造如下的格：

[I150×150M150×75T]\begin{bmatrix} I_{150\times 150} & M^{T}_{150\times 75}\\ \end{bmatrix}

该格满足

( b1, b2, b3, ..., b150)∗[I150×150M150×75T]=( b1, b2, b3, ..., b150, 0, 0, …, 0⏟75个)(\ b_1,\ b_2,\ b_3,\ ...,\ b_{150}) * \begin{bmatrix} I_{150\times 150} & M^{T}_{150\times 75}\\ \end{bmatrix} = (\ b_1,\ b_2,\ b_3,\ ...,\ b_{150},\ \underbrace{0,\ 0,\ \dots,\ 0}_{75\text{个}})

虽然不能真正找到B75×100B_{75\times 100}，但是一样的道理，只要找到满足条件的基向量，然后拿去reduced_basis[0]就行了

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
from sage.modules.free_module_integer import IntegerLattice
from tqdm import trange
from itertools import product
from Crypto.Cipher import AES
from base64 import b64encode, b64decode
from hashlib import *
import sys

flag = b'flag{mylove_in_summer}'
n = 75
m = 150
r = 10
N = 126633165554229521438977290762059361297987250739820462036000284719563379254544315991201997343356439034674007770120263341747898897565056619503383631412169301973302667340133958109

def gen(n, m, r, N):
    t1 = [ZZ.random_element(-2^15, 2^15) for _ in range(n*m)]  #75 * 150
    t2 = [ZZ.random_element(N) for _ in range(r*n)]  #10 * 75
    B = matrix(ZZ, n, m, t1)  #75 * 150
    L = IntegerLattice(B)
    A = matrix(ZZ, r, n, t2)  #10 * 75
    C = (A * B) % N
    return L, C

def pad(s):
    return s + (16 - len(s) % 16) * b"\x00"

#signal.alarm(60)
#token = input("team token:").strip().encode()  这题主要是练习，省略靶机交互流程

L, C = gen(n, m, r, N)
key = sha256(str(L.reduced_basis[0]).encode()).digest()
aes = AES.new(key, AES.MODE_ECB)
ct = b64encode(aes.encrypt(pad(flag))).decode()






#exp
#只知道C和ct

#求M
M = []
L1 = block_matrix([[identity_matrix(150), C.T], 
                 [matrix.zero(10, 150), identity_matrix(10) * N]])  #不需要规约



res1 = L1.LLL()
for i in res1:
    if all(j == 0 for j in i[-10::]):
        M.append(i[:-10:])

M = Matrix(ZZ, 75, 150, M)

L2 = block_matrix([[identity_matrix(150), M.T]]) * diagonal_matrix(ZZ, [1] * 150 + [N] * 75)
res2 = L2.LLL()
# print(res2[0])

B_ = []
for i in res2:
    if all(j == 0 for j in i[-75::]):
        B_.append(i[:-75:])
B_ = Matrix(ZZ, B_)
B_ = IntegerLattice(B_)
res3 = B_.reduced_basis


for i in trange(-10, 10):  #直接拿到做密钥的话，发现不管基向量方向对不对，都解不出来，很明显要小爆一下
    for j, k in product(range(-10, 10), repeat = 2):
        res = i * res3[0] + j * res3[1] + k * res3[2]
        key = sha256(str(res).encode()).digest()
        aes = AES.new(key, AES.MODE_ECB)
        flag = aes.decrypt(b64decode(ct))
        if flag.isascii():
            print(flag)
            sys.exit()

'''
 45%|████▌     | 9/20 [00:00<00:00, 18.61it/s]
b'flag{mylove_in_summer}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
'''

题3

加密代码：

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 not2022but2024 import CBC_key
from Crypto.Util.Padding import pad

flag = b'flag{}'
from Crypto.Cipher import AES
from hashlib import sha256
import random

n = 31
m = 80
M = random_prime(2^256)
As = [random.randrange(0,M) for i in range(n)]
xs = [random_vector(GF(2),m).change_ring(ZZ) for i in range(n)]
Bs = sum([As[_] * vector(Zmod(M),xs[_]) for _ in range(n)]).change_ring(ZZ)

IV = sha256(str(int(sum(As))).encode()).digest()[:16]
aes = AES.new(CBC_key,AES.MODE_CBC,iv=IV)
cipher = aes.encrypt(pad(flag,16))
print(cipher)
print(Bs)
print(M)

"""
b'%\x97\xf77\x16.\x83\x99\x06^\xf2h!k\xfaN6\xb0\x19vd]\x04B\x9e&\xc1V\xed\xa3\x08gX\xb2\xe3\x16\xc2y\xf5/\xb1\x1f>\xa1\xa0DO\xc6gy\xf2l\x1e\xe89\xaeU\xf7\x9d\x03\xe5\xcd*{'
(53844623749876439509532172750379183740225057481025870998212640851346598787721, 15997635878191801541643082619079049731736272496140550575431063625353775764393, 8139290345909123114252159496175044671899453388367371373602143061626515782577, 51711312485200750691269670849294877329277547032926376477569648356272564451730, 56779019321370476268059887897332998945445828655471373308510004694849181121902, 11921919583304047088765439181178800943487721824857435095500693388968302784145, 41777099661730437699539865937556780791076847595852026437683411014342825707752, 68066063799186134662272840678071052963223888567046888486717443388472263597588, 62347360130131268176184039659663746274596563636698473727487875097532115406559, 5552427086805474558842754960080936702720391900282118962928327391068474712240, 48174546926340119542515098715425118344495523250058429245324464327285482535849, 8793683612853105242264232876135147970346410658466322451040541263235700009570, 78872313670499828088921565348302137515276635926740431961166334829533274321063, 45986964918902932699857479987521822871519141147943250535680974229322816549720, 5539445840707805914548390575494054384665037598195811353312773359759245783130, 20826977782899762485848762121688687172338304931446040988601154085704702880401, 46412211529487215742337744878389285037116176985579657423264681199244501574725, 50741521861819713251561088062479658512988690918747542471827101566427731303416, 2657362476409491643067267745198536051013594201408763262228104521443406410606, 44328850588851214219220815931558890597249087261312360172796979417041192180750, 17240480010040498121198897919561403023278264974274103780966819232080038065027, 76464770903606818697905572779761942703446600798395362596698226797476804541350, 68085613496380272855135907856973365357126900379731050931749074863934645465000, 9526872466819179025323613184178423510032119770349155497772862700507205270355, 28561337010953007345414455535991538568670238712225998300322929406204673707677, 39182834208152122329027105134597748924433413223238510660062164011424607149326, 19600894094417831727934201861135428039216930531542618497625138063955073257655, 33328666355366104030800248593757531247937582259417117239494927842284231531315, 27309478993506749161736165865367616487993717640890015043768259212155864131357, 32466044572968154084881296026899630667525833604042642990295342316076396001186, 49980145403553319854613749104421978583845098879328180142454823188167202440531, 38902032967058543060885229430655776526806612465844770409338358289020456837934, 78745490507168848644435092323691842070096557975478968062804777954092505226481, 29262215059225133132435433010691828148944958395141222387754208495595513295896, 6511387460586172200641169204557875679554320457409786241141816573577911255491, 66384481485687195909117407019475796131750762463683904604078327730810293442381, 423759905526048383541413041558602466949757468395447771021215945027193456079, 22783408973585275782090957855992582495700723663661365548067357177569979041893, 68353193576625297253561095680880135893826094396013897100461325445097220567952, 43167069172003777333498030236780725018297276760410131777676641770086016833895, 64358541048274393300028483577573557871346089755363306971761786692679519831483, 21556895066359380729591004278007242407987861350911480029337345312081293559522, 44577165826706395273335181181407938788716768576602201516787959082367484270939, 78757778436852423927977028333940102206341452120720821559562765928972163293676, 44086875063535769349025637423479101247594814134304419072849625465484225865969, 14807706619359620049095657244485266549982349493285112282927264862821502986777, 43450687889967222089875050731849984583914520350091026482076939962301357700844, 1474778474197964170746922000689413626959960404877093741742022788928758658052, 79005121352540562329295808987757987563818908122338120731119811866179839023066, 47361429831079185336051370209844150786334814579472466274050224935364333043476, 8909641306798261411104006708035991379862284048887418817598377473145077145642, 44993528669446910461207972446344484798499156885515181685694150462051560323869, 60204243272925546012169935228277233636280408169577344559847112958669050860101, 66809206609934431859673802937592425152676610053648406215573441926481740948749, 48623757302381792245138496825183044619235050623516633984941208604059757210728, 74934019261870654132458355068539987475536823529848461398042458398130801089348, 81278897734052917585963333108338812132716202790194259021265555401046891572210, 41418370274745377550600009352057265922713132669834032188979684042175922204024, 73981010754794931896065529724613353453372905938901875720094092383581574259191, 11510558496830929812186594415924901190526760075439658941646537744390447056913, 12871197940932509721689273944282764851472299179520294551038550766143300003239, 13125880938267970248643653453332470640527994428672724309079849030361661332656, 54395419708886945822916038876690794705789028459055268227222784885329659953982, 61086065362549289820758257234061183781820530343096737751500151263095654158833, 82468574289042215923908109910435173164917593677419944115441863191433795206895, 74824772928304750096519403623184368585460834399443013973554958461695733158569, 62083272769549467370505302454770858941632031970595402929903886003242570089639, 32887658447648473554892464271221330218759930615421257444587260809741011575629, 61429802749826163386356730793012182546392982886506956044525858721859869425131, 5026334434650853992374810127604777276035123569907012144091150436739161826287, 45670628392162402176230172863069957038704667046592086395237022845943911838596, 75520245720261510582172547313413372786802547571090110489287163846652239401646, 58965653594414801363386215405590061806834352303047020261264473838037335631061, 58420763657138617301836404602193276258504426799372302098717637069900583548539, 59706321905964570794806865247363209194143775670139452625484601579677510881069, 58198559234141523043769073193017418608700536234755760366044515212056701655389, 63604949023865770163110419193113341020042474142600282131130750460724114084001, 83394429495100363085521124642271430199140318544724150468993097819105267094727, 69274794456073656789648159458959148992942789823222968847070524400609637893875, 46951397339712109206750633799342393646147684284310708226074432825222250739146)
83509079445737370227053838831594083102898723557726396235563637483818348136543
"""

这个其实也是给了如下条件

A1×31∗X31×80=B1×80A_{1\times 31} * X_{31\times 80} = B_{1\times 80}

可以通过如下的代码片段来判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Cipher import AES
from hashlib import sha256
import random
n = 31  #行
m = 80  #列
M = random_prime(2^256)
As = [random.randrange(0,M) for i in range(n)]
xs = [random_vector(GF(2),m).change_ring(ZZ) for i in range(n)]
Bs = sum([As[_] * vector(Zmod(M),xs[_]) for _ in range(n)]).change_ring(ZZ)

A = Matrix(Zmod(M), 1, 31, As)
X = Matrix(Zmod(M), xs)
print(Bs.list() == (A * X).list())
#True

然后这个X31×80X_{31\times 80}里面的基向量的元素值都是0或1，很明显更好规约了

按照常规做法来做

B80×1T=X80×31T∗A31×1TM49×80∗B80×1T=M49×80∗X80×31T∗A31×1T\begin{array}{l} B^{T}_{80\times 1}= X^{T}_{80\times 31}*A^{T}_{31\times 1}\\ M_{49\times 80}*B^{T}_{80\times 1}= M_{49\times 80}*X^{T}_{80\times 31}*A^{T}_{31\times 1}\\ \end{array}

构造格，且满足

( m1, m2, m3, ..., m80, k)∗[I80×80B80×1T01×80p]=( m1, m2, m3, ..., m80, 0)(\ m_1,\ m_2,\ m_3,\ ...,\ m_{80},\ k) * \begin{bmatrix} I_{80\times 80} & B^{T}_{80\times 1}\\ 0_{1\times 80} & p \end{bmatrix} = (\ m_1,\ m_2,\ m_3,\ ...,\ m_{80},\ 0)

此时有

M49×80∗X80×31T=0M_{49\times 80}*X^{T}_{80\times 31}=0

转置一下

X31×80∗M80×49T=0X_{31\times 80}*M^{T}_{80\times 49}=0

构造格，且满足

( b1, b2, b3, ..., b80)∗[I80×80M80×49T]=( b1, b2, b3, ..., b80, 0, 0, …, 0⏟49个)(\ b_1,\ b_2,\ b_3,\ ...,\ b_{80}) * \begin{bmatrix} I_{80\times 80} & M^{T}_{80\times 49}\\ \end{bmatrix} = (\ b_1,\ b_2,\ b_3,\ ...,\ b_{80},\ \underbrace{0,\ 0,\ \dots,\ 0}_{49\text{个}})

exp调试中，排了一天的错误，愣是找不到哪个细节有问题

累了，剩下几题晚上再更o(￣ヘ￣o＃)

更新于：2024年12月25日

评论

评论区