NSSCTFEasyMod

NSSCTF EasyMod系列EXP

0.Introduction

接上期，这一次是EasyMod系列的做题记录，来看看某些地方是不是还有什么技巧

ref：LWE | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

1.easyMod1

第一题，题目还是很明显的。

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

table = "01234567"
p = getPrime(328)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(70)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)
"""
p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263
"""

题目给出了素数 $p$ 和密文 $c$，我们要求 flag 中间的值，这些值都在 $0\sim7$ 之间。

很自然地想到，把已知的部分给它减掉，然后把字符 $0\sim7$ 改为数字 $0\sim7$，我们得到改变后的 $c$。再加上最后一位处理后多了一个 $256$ 的倍数，也可以将其除掉。

1
2
3
4
p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263
t=bytes_to_long(b"NSSCTF{" + bytes([0x30]*70) + b"}")
c=(c-t)*pow(256,p-2,p)%p

那么等式就过来了：
$$
\sum_{i=0}^{69} 256^{69-i}x_i-c-kp=0
$$
然后这不就来得很自然了吗（这里仍然以 $n=3$ 为例，$n=70$ 同理）

1

$p$ 是 $328$ 位的，最后构造的矩阵是 $72\times 72$的，算一下界：$328/72=4.55$，应该是勉强够的。

先来了一发LLL，结果没出。然后记得正规子群中哪个小伙伴说过，如果是 $0/1$ 决策，用 BKZ 可以找到更短的向量。然后就用了BKZ，原题得解。

但是发现BKZ好像对向量的绝对长度比较敏感：因为我给最后一列乘 $2^{400}$，一秒钟就能出，而如果给最后一列乘 $2^{1600}$，就要跑好久好久。。。

EXP：

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 *
p = 501785758961383005891491265699612686883993041794260611346802080899615437298977076093878384543577171
c = 327005346153237517234971706274055111857447948791422192829214537757745905845319188257204611848165263
t=bytes_to_long(b"NSSCTF{" + bytes([0x30]*70) + b"}")
c=(c-t)*pow(256,p-2,p)%p

M=[[i==j for j in range(72)]for i in range(72)]
M[-1][-1]=p
M[-2][-1]=-c
for i in range(70):
    M[i][-1]=pow(256,69-i,p)
Mb=diagonal_matrix([1]*71+[2**400])
M=matrix(ZZ,M)
M3L=(M*Mb).BKZ()

for vec in M3L:
    if(vec[-2] in [1,-1] and vec[-1]==0):
        if(all([abs(i)<9 for i in vec[:-2]])):
            s=''.join([str(i) for i in vec[:-2]])
            print('NSSCTF{'+s+'}')
            break
#NSSCTF{5036541772751046406531362142757356307107252723754051320011253505562041}

2.easyMod2

第二题和第一题看似完全一样，但长度从 $70$ 变成了 $80$。如果这个时候再算界的话，$328/82=4$。但考虑到维数比较高， $4$ 位的长度肯定不够了。

不过可以考虑消掉MSB进行配平（见自己博客LatticeNotes8第五部分），也就是以前是 $0,1,2,3,4,5,6,7$，每个分量 $3$ 位，变成以 $4$ 为中心的 $-4,-3,-2,-1,0,1,2,3$，这样每个分量都只有 $2$ 位了。

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

table = "01234567"
p = getPrime(328)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(80)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)
print(flag)

'''
p = 324556397741108806830285502585098109678766437252172614832253074632331911859471735318636292671562523
c = 141624663734155235543198856069652171779130720945875442624943917912062658275440028763836569215230250
'''

EXP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
p = 324556397741108806830285502585098109678766437252172614832253074632331911859471735318636292671562523
c = 141624663734155235543198856069652171779130720945875442624943917912062658275440028763836569215230250
t=bytes_to_long(b"NSSCTF{" + bytes([0x34]*80) + b"}")
c=(c-t)*pow(256,p-2,p)%p
M=[[i==j for j in range(82)]for i in range(82)]
M[-1][-1]=p
M[-2][-1]=-c
for i in range(80):
    M[i][-1]=pow(256,79-i,p)
Mb=diagonal_matrix([1]*81+[2**400])
M=matrix(ZZ,M)
M3L=(M*Mb).BKZ()
for vec in M3L:
    if(vec[-2] in [1,-1] and vec[-1]==0):
        vec=vec*vec[-2]
        if(all([abs(i)<5 for i in vec[:-2]])):
            s=''.join([str(4+i) for i in vec[:-2]])
            print('NSSCTF{'+s+'}')
            break
#NSSCTF{25350625451533421162474265547571536103420331260232652121722452361537257541460235}

3.easyMod3

这个时候开始，技巧就开始有了：

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

table = "Nss"
p = getPrime(328)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(100)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)

'''
p = 421384892562377694077340767015240048728671794320496268132504965422627021346504549648945043590200571
c = 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178
'''

Table变成了 Nss，也就是 $78$ 和 $115$，其他内容和以前完全一致。自然要想办法把 $78$ 和 $115$ 变换成 $0,1$。

显然，这个变换可以是：
$$
f(x)=\frac{x-78}{115-78}
$$
之前的表达式为（当然，这个 $c$ 处是处理过的 $c$，也就是要先减掉已知的部分）：
$$
\sum_{i=0}^{99} 256^{99-i}x_i\equiv c\pmod p
$$
那么处理一下，就变成了：
$$
f\left(\sum_{i=0}^{99} 256^{99-i}x_i\right)\equiv f(c) \pmod p
$$
由于这个 $f$ 是线性变换，因此可以提出来：
$$
\sum_{i=0}^{99}256^{99-i}f(x_i)-f(c)\equiv 0\pmod p
$$
那么我们就有：

2

最右边就只有 $0$ 和 $1$ 两个取值了，直接 BKZ 就行。

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 *
p = 421384892562377694077340767015240048728671794320496268132504965422627021346504549648945043590200571
c = 273111533929258227142700975315635731051782710899867431150541189647916512765137757827512121549727178
t=bytes_to_long(b"NSSCTF{" + bytes([78]*100) + b"}")
c=(c-t)*pow(256,p-2,p)*pow(37,p-2,p)%p
M=[[i==j for j in range(102)]for i in range(102)]
M[-1][-1]=p
M[-2][-1]=-c
for i in range(100):
    M[i][-1]=pow(256,99-i,p)
Mb=diagonal_matrix([1]*101+[2**400])
M=matrix(ZZ,M)
M3L=(M*Mb).BKZ()
for vec in M3L:
    if(vec[-2] in [1,-1] and vec[-1]==0):
        vec=vec*vec[-2]
        if(all([abs(i) in [0,1] for i in vec[:-2]])):
            s=''.join([chr(78+37*i) for i in vec[:-2]])
            print('NSSCTF{'+s+'}')
            break
#NSSCTF{NNNssNsNNNNsNNNsNNNNNssNNNssNNNsNsNNsNsNNssNNNNNNsNNNssNsNNNNNssNssssNsNNsNsssNNNNssNNNssNsNNssNsNss}

4.easyMod4

上一题是两个，这一题是四个：

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

table = "GAME"
p = getPrime(440)
flag = b"NSSCTF{" + "".join([choice(table) for i in range(100)]).encode() + b"}"
c = bytes_to_long(flag) % p

print("p =",p)
print("c =",c)
print(flag)

'''
p = 2271129678202363707972156644097566224560370806295266873816026779022614695317611229903770390498322537051358521932851893609555063610221
c = 244176818026839545554951436126300508547217557099550914232243928051857553603712968234687200629719468115535825237511413058786560692170
'''

AEGM 四个符号的ASCII码分别为 $65,69,71,77$，$71$ 恰好是这四个数的平均数。那么给所有数字减去 $71$，就变换成了 $-6,-2,0,2$，然后再除以 $2$ 就变成了 $-3,-1,0,1$ 了。

因此，本题的变换为：
$$
f(x)=\dfrac{x-71}{2}
$$
那就和上个题一样，先进行 $f$ 的线性变换，再进行规约，只是处理变了一下，矩阵都不带变的。。。

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 *
p = 2271129678202363707972156644097566224560370806295266873816026779022614695317611229903770390498322537051358521932851893609555063610221
c = 244176818026839545554951436126300508547217557099550914232243928051857553603712968234687200629719468115535825237511413058786560692170
t=bytes_to_long(b"NSSCTF{" + bytes([71]*100) + b"}")
c=(c-t)*pow(256,p-2,p)*pow(2,p-2,p)%p
M=[[i==j for j in range(102)]for i in range(102)]
M[-1][-1]=p
M[-2][-1]=-c
for i in range(100):
    M[i][-1]=pow(256,99-i,p)
Mb=diagonal_matrix([1]*100+[1]+[2**450])
M=matrix(ZZ,M)
M3L=(M*Mb).BKZ()
for vec in M3L:
    if(vec[-2] in [1,-1] and vec[-1]==0):
        vec=vec*vec[-2]
        if(all([abs(i) in [0,1,2,3] for i in vec[:-2]])):
            s=''.join([chr(71+2*i) for i in vec[:-2]])
            print('NSSCTF{'+s+'}')
            break
#NSSCTF{GEEGEEEMEEMMAAMGGGGEEGMMAMEGGEEEGAGGMEMEMMAMGGGEAAGMGEAAGEMMEEEMGMAAMMGEAAEEEEEGGEMMMMAEGAAAMEMEAEGE}

5.easyModX

下面来看这个题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from random import choice
from secret import flag

p = 261088368789732794845261013655166647659
e = [30588206725334965124218576566361946366, 240378629906987890008899515210199268104, 73900925710927218655807121061998508862, 157139777808957554332353318136098888483, 243765215780142061395530407127372013475, 181095457676420403619327909683177178758, 168511590304599342147975740568964397279, 235779989157654444966538876611679250050, 192467270172062191434950332116042687554, 46558659970310197982201637597747473216, 62529113215285430840184698629133000066, 251750442402629677824521937643064776900, 160526363682111725718984210053271633854, 89871378955902451513790182093384035712, 137782738690828150087739365187540616262, 176496816927086958576967271084657160704, 11231167607205560879604623617803674145, 173110231053932787190336379167484415333, 113827058823365300800764773640462325987, 208437723417037424292933393147428214404, 105841832200877684371773243124769562562, 200452496794549807863941862631735450979, 54543886592797814411193168113440236641, 248363856529475506437891045725892031529, 227794762535166828537547346095986486625, 129797512068340533658747834671847852837, 70514339837773047269176229144825763491, 149154551186469937903361787620406125058, 38573433347822581553210107082054709791, 224408176662012657150916454178813741254]

m, n = 320, 137
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(e) for i in range(m)])
b = A*s + e

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

$30$ 个 $e$ 值，这是在逗我玩吗？

回看前面四个题，第一、二题是 $48\sim55$ ，使用的变换为 $f(x)=x-48$ 和 $f(x)=x-52$。

第三题是二元的值 $78,115$，我们选择的变换为 $f(x)=\dfrac{x-78}{37}$。

第四题是四元值 $65,69,71,77$，对应的变换为 $f(x)=\dfrac{x-71}{2}$。

如果真的问这些值是如何看到的。。那我只能说：瞪眼法（bushi）

但这个题瞪眼法似乎失效了，但看前面的变换：我们都是构造了一个线性变换 $f(x)=kx+u$ （这里用 $u$，不和题目中的 $b$ 混淆），使得对于每个 $x$， $f(x)$ 的值特别小。那我们是否可以找到 $k,u$ 来得到 $f(x)$ 呢？

我们假设 $f(x)$ 很小，以三个为例，那么就有下面的关系：

3

然后就可以寻找目标向量了。这边还真能找到一个，事后看了WP，才知道原来这个是被精心构造的。

1
2
3
4
5
6
7
8
9
10
11
12
13
p = 
e = 
M=block_matrix(ZZ,[
    [1,0,matrix(e)],
    [0,1,matrix([1]*30)],
    [zero_matrix(30,1),zero_matrix(30,1),p*identity_matrix(30)]
])
Mb=diagonal_matrix([1,1]+[p//120]*30)
M3L=(M*Mb).LLL()*Mb**-1
vec=M3L[1] #可能是1 ，也可能是3，取决于平衡系数的分母。如果小于 30 就是3 ，大于 30 就是 1
print(vec)
k,u,ed=vec[0],vec[1],vec[2:]
#(-59856154147186816166001902668286083329, -89318704509298137176851764675399872440, -3, -10, 8, -1, 21, -13, 26, 25, 14, -11, -19, 17, 30, 0, -24, 22, -26, -9, -12, 6, -8, 10, -15, -14, 29, -20, -23, 3, -7, -2)

有了 $k,u$ 然后就是求flag了，这边取 $160$ 组，构造 $298^2$ 的矩阵，配置一下平衡参数 $(1,2^{123},2^{128})$ 然后规约，flatter 在服务器上大概跑了 $\mathsf{5}$ 分钟。

4

那么，剩下的部分也就出来了：

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
A=
b=
c=
fA=[0]*len(A)
fb=[0]*len(b)
for i in range(len(A)):
    fA[i]=k*A[i]%p
for i in range(len(b)):
    fb[i]=(k*b[i]+u)%p
M=block_matrix(ZZ,[
    # [identity_matrix(160),zero_matrix(160,137),identity_matrix(160),zero_matrix(160,1)],
    [identity_matrix(137),-matrix(ZZ,160,137,fA[:160*137]).T,zero_matrix(137,1)],
    [zero_matrix(160,137),-p*identity_matrix(160),zero_matrix(160,1)],
    [zero_matrix(1,137),matrix(fb[:160]),1]
])
print(M.nrows(),M.ncols())
Mb=diagonal_matrix([1]*137+[1<<123]*160+[1<<128])
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)))
from datetime import *
print(datetime.now())
M3L=flatter(M*Mb)
print(datetime.now())
M3LuB=M3L*(Mb**-1)
for vec in M3LuB:
    if(vec[-1] in [1,-1]):
        print(vec)
        break
assert all([abs(i)<=30 for i in vec[137:137+160]])
s=vector(GF(p),vec[:137])
from Crypto.Cipher import AES
from hashlib import md5
print(AES.new(key=md5(str(s).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(bytes.fromhex(c)))
#b'NSSCTF{Th1s_T1m3_U_Kn0W_whaT_Lin3AR_M3@Ns!}'

6.easyMod alpha

这部分的最后一题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from random import choice, randint
from secret import flag

p = getPrime(64)
e = [randint(0, p), randint(0, p)]

m, n = 220, 137
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(e) for i in range(m)])
b = A*s + e

print("A =", A.list())
print("b =", b.list())
print("c =", AES.new(key=md5(str(s).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag).hex())
print("p =", p)

题目还是熟悉的 LWE，但误差值未知，$\vec s$ 的取值也是随机数。因此直接规约是不太可能的。。。

然后第二眼想的是：既然 $e$ 只有两个，是不是可以列方程解方程（但这需要 $O(n^2)$ 个等式，所以这个思路也是没法做的）

那这，还能规约吗？继续 $f(x)=kx+u$，试试看？

根据原式 $\vec b=A\vec s+\vec e$，那么就有：
$$
f(\vec b)=f(A\vec s+\vec e)
$$
化简就是（其中 $\vec 1$ 表示全 $1$ 向量）：
$$
k\vec b+u\vec 1=kA\vec s+k\vec e+u\vec 1
$$
也就是：
$$
f(\vec b)=kA\vec s+f(\vec e)
$$
其中 $f(\vec e)$ 的每个分量仅由 $0$ 和 $1$ 构成。

那么就可以得到式子：

5

这边的话，还是取 $160$ 组，这样构造 $299\times299$ 的矩阵，平衡一下然后LLL。

最后筛选中间一部分仅由两个数值组成的向量，就能得到目标向量了。

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
A=
b=
c=
p=
A=matrix(GF(p),220,137,A)
from subprocess import check_output
from re import findall

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 EE(x):
    return identity_matrix(x)
def OO(x,y=0):
    if(not y):
        return zero_matrix(x,x)
    return zero_matrix(x,y)
from Crypto.Util.number import *
M=block_matrix(ZZ,[
    [EE(137),A[:160].T,OO(137,2)],
    [OO(160,137),p*EE(160),OO(160,2)],
    [OO(1,137),-matrix(ZZ,b[:160]),matrix([1,0])],
    [OO(1,137),-matrix(ZZ,[1]*160),matrix([0,1])],
])
Mb=diagonal_matrix([1] * 137 + [2**500] * 160 + [1,1])
M3L=flatter(M*Mb)*Mb**-1
for vec in M3L:
    if(set(vec[137:137+160])==set([0,1]) or set(vec[137:137+160])==set([0,-1])):
        print(vec)
        break
vec=vector(GF(p),vec)
s,e,k,u=vec[:137],-vec[137:137+160],vec[-2],vec[-1]
from Crypto.Cipher import AES
from hashlib import md5
print(AES.new(key=md5(str(s/k).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(bytes.fromhex(c)))
#b'NSSCTF{Aut0_Advanced_WhEN_err0r_is_bivar1aT3!}'

7.只规约 $\vec e$ 不规约 $\vec s$ 的方法？

刚好最近在学矩阵论，来看一下这个方法！

我们再回顾一下第 5 题和第 6 题，因为 LLL 的复杂度为 $O(n^{6}\ln ^3 \max|\vec v|)$，在 $n=137,m=160$ 时，需要构造 $298^2$ 的矩阵，使用 flatter 也需要 $5$ 分钟。如果 $n,m$ 扩展到 $400$，那这复杂度是直接爆炸的。并且很多题目中，$\vec s$ 是随机分布而非小量，这个时候我们反而更加关注的是 $\vec e$ 的值了。因为拿到 $\vec e$ 可以直接解 $\vec s$，并且解方程的复杂度为 $O(n^{3})$（实际上现在的算法已经优化到 $O(n^{2.37})$ 了，和 $O(n^6)$ 比起来肯定时快了不少的，毕竟 $500$ 个未知数的线性方程组Sage解方程只要 $10$ 秒）

我们之前的规约方法是（因为构造矩阵使用行向量，那么这里使用行向量形式 $\vec b=\vec sA+\vec e$）：

7

很自然地能够想到，既然不规约 $\vec s$，那就把 $\vec s$ 这一维直接去掉。

8

不过这个结果看上去其实是很不自然的，以 $n=137,m=160$ 为例：左边是 $298$ 个数，右边是 $138$ 个数，矩阵为 $298$ 行 $138$ 列，仍然是 $298$ 个向量在规约，没有本质上的有优化。并且，如果矩阵的行和列相差过大，Sage使用LLL会给出一些错误结果（比如可能给出全 $0$ 结果）

因为我们并不关心 $\vec s$，那么可以给 $\vec s$ 做一些变换。根据自己的规约经验（CryptoHack Noise Cheap那个题，$n=64$，当时我只取了 $64$ 组数据就规约，结果没成功，然后取到了 $96$ 组成功了）。取样次数 $m$ 一般都会超过秘密向量维数 $n$。如果我们对 $\vec s$ 进行一些线性变换，那么 $A$ 也会跟着变动。那我们肯定想的是让 $A$ 变简单一些 :D。

啥样的 $A$ 最简单？显然是 $A=E$，但 $A$ 不是方阵。那就是 $A=[E|B]$ 最简单了呗。

那么我们就要找一个线性变换，使得 $f(\vec A)=[E|B]$，这不就是解线性方程组的克莱默法则的过程吗？既然都是简单线性变换，那就一定存在一个 $n$ 阶可逆方阵 $C$ 使得：
$$
f(A)=CA
$$
在原等式中插入一个 $C^{-1}C$，就有了
$$
\vec b=\vec sC^{-1}CA+\vec e
$$
因为我们不关心 $\vec s$，只关心 $\vec e$，那么我们可以随意对 $\vec s$ 进行变换：
$$
\vec b= (\vec sC^{-1})(CA)+\vec e
$$
也就是：
$$
\vec b= (\vec sC^{-1})[E|B]+\vec e
$$
设 $\vec sC^{-1}=\vec t$，就得到：
$$
\vec b=\vec t[E|B]+\vec e
$$
看到这个 $E$ 了吗？$\vec t$ 的前半部分就是 $\vec b-\vec e$ 的值（这里 $\vec b,\vec e$ 比 $\vec s$ 长）！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p=1435756429
s=random_vector(Zmod(p),8)
A=random_matrix(Zmod(p),8,12)
e=vector(Zmod(p),[randint(-3,3) for _ in range(12)])
b=s*A+e
A1=A.echelon_form()
C=A.solve_left(A1)
print(s)
print(s*C**-1)
print(b-e)
print(b)
print(e)
(1359516898, 87718237, 786451258, 256157568, 850005568, 702156437, 1408974758, 198576099)
(1055091037, 152325457, 820871867, 1292686262, 1113081561, 923620710, 597279934, 923145442)
(1055091037, 152325457, 820871867, 1292686262, 1113081561, 923620710, 597279934, 923145442, 629652248, 1272827508, 728063535, 384816526)
(1055091035, 152325456, 820871870, 1292686265, 1113081562, 923620707, 597279934, 923145441, 629652250, 1272827505, 728063538, 384816529)
(1435756427, 1435756428, 3, 3, 1, 1435756426, 0, 1435756428, 2, 1435756426, 3, 3)

在上面这个例子中，$A$ 经过行变换 A.echelon_form()，得到的$[E|B]$ 如下

9

既然这样，上面的矩阵就可以化为：

10

以 $n=4,m=6$ 为例：

11

我们可以注意到：由于 $\vec t$ 的每个分量一定小于 $p$，那么前 $4$ 列没必要减去 $kp$，因为根据上面的理论， $t_i-b_i=e_i(i≤3)$ 恰好成立，因此这些列只需要放个 $1$ 和一个 $-b$ 就OK。

12

想到这个的人简直是个天才。。。

随便来一组数据测一下：

$m=80,n=50$，优化前方法 $\mathsf{25.31s}$，优化后方法 $\mathsf{6.00s}$

$m=166,n=140$，优化前方法 $\mathsf{382.10s}$，优化后方法 $$\mathsf{42.39s}$$

最后贴一个测试代码：

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
p=previous_prime(10**100)
n,m=140,166
dbgs=random_vector(Zmod(p),n)
A=random_matrix(Zmod(p),m,n)
dbge=vector(Zmod(p),[randint(-7,7) for _ in range(m)])
b=A*dbgs+dbge
from subprocess import check_output
from re import findall

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)))
from datetime import *
def EE(x):
    return identity_matrix(x)
def OO(x,y=None):
    if(not y):
        return zero_matrix(x,x)
    else:
        return zero_matrix(x,y)
def attack0():
    STIME=datetime.now()
    M=block_matrix(ZZ,[
        [EE(n),A.T,OO(n,1)],
        [OO(m,n),-p*EE(m),OO(m,1)],
        [OO(1,n),matrix(b),1]
    ])
    Mb=diagonal_matrix(ZZ,[1]*n+[p//8]*m+[p])
    MFL=flatter(M*Mb)*Mb**-1
    for vec in MFL:
        if(vec[-1] in [-1,1]):
            vec*=-vec[-1]
            return vector(GF(p),vec[:n]),(datetime.now()-STIME).total_seconds()
def attack1():
    STIME=datetime.now()
    ZEm=[[0 for __ in range(m)] for __ in range(m-n)]
    for i in range(1,m-n+1):
        ZEm[-i][-i]=-p
    ZEm=matrix(ZEm)
    M=block_matrix(ZZ,[
        [A.T.echelon_form(),OO(n,1)],
        [ZEm,OO(m-n,1)],
        [-matrix(b),1]
    ])
    Mb=diagonal_matrix(ZZ,[1]*m+[1])
    MFL=flatter(M*Mb)*Mb**-1
    for vec in MFL:
        if(vec[-1] in [-1,1]):
            vec*=-vec[-1]
            break
    err=vector(GF(p),vec[:m])
    s=A.solve_right(b-err)
    return s,(datetime.now()-STIME).total_seconds()
s0,t0=attack0()
print(t0)
assert dbgs==s0 or dbgs==-s0
s1,t1=attack1()
print(t1)
assert dbgs==s1 or dbgs==-s1

9.总结

奇怪的技巧又增加了:D

CTFSeason4
#ExpLog
NSSCTFEasyMod
http://example.com/2025/04/06/NSSCTFEasyMod/
作者
huangx607087
发布于
2025年4月6日
许可协议