2025VNCTF-Crypto-WP

只写了密码部分和一道杂项,最后离比赛结束还有几十秒的时候发现自己从30掉到了31,以为与奖品无缘了,但是后面收集wp的时候,前面有两队没交wp,所以排到29了:D。

eazymath

题目:

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 *
from secret import flag
flag=bytes_to_long(flag)
l=flag.bit_length()//3 + 1
n=[]
N=1
while len(n) < 3:
p = 4*getPrime(l)-1
if isPrime(p):
n.append(p)
N *= p

print(f'c={flag*flag%N}')

from sympy import symbols, expand
x = symbols('x')
polynomial = expand((x - n[0]) * (x - n[1]) * (x - n[2]))

print(f'{polynomial=}')
# c=24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
# polynomial=x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619

题目对flag做了如下加密: \[ c = (flag)^2 \mod N \] 其中N是三个素数(n0, n1, n2)的乘积,所以我们可以把加密的等式现转换到模素数下: \[ c = (flag)^2 \mod n_i \ \ \ i \in {0, 1, 2} \] 然后来看如何获取这3个素数,题目给了一个整数上的polynomial,这3个素数就是这个多项式的根,所以直接用roots方法求解就行。 这样我们就得到了3个模素数下的二次方程,解这3个方程可以用AMM算法开模素数下的根号,但是这里我们用的是sage自带的roots方法,roots方法也是可以求解模素数下的多项式的根的。最后我们得到的结果是模\(n_i\)下的\(flag\),所以还要用CRT(中国剩余定理)将模数提升到\(N\)。 exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
PR.<x> = PolynomialRing(ZZ)
c=24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
polynomial=x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
n1, n2, n3 = [i[0] for i in polynomial.roots()]
all_root = []
for n in [n1, n2, n3]:
PR.<x> = PolynomialRing(GF(n))
f = x^2 - c
all_root.append([ZZ(r[0]) for r in f.roots()])

for r1 in all_root[0]:
for r2 in all_root[1]:
for r3 in all_root[2]:
flag = crt([r1, r2, r3], [n1, n2, n3])
flag = long_to_bytes(flag)
if flag.isascii():
print(flag)
# b'VNCTF{90dcfb2dfb21a21e0c8715cbf3643f4a47d3e2e4b3f7b7975954e6d9701d9648}'

Simple_prediction

题目:

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
from random import shuffle
from Crypto.Util.number import getPrime
from random import choice, randint
from secret import *

# flag来源
flag = b"VNCTF{xxxxxxx}"
assert len(flag)<100
FLAG1=flag[:32]
FLAG2=flag[32:]

# part1
class LCG:
def __init__(self, seed=None, a=None, b=None, m=None):
if not m:
self.m = getPrime(512)
if not seed:
self.seed = getPrime(512)
if not a:
self.a = getPrime(512)
if not b:
self.b = getPrime(512)
#print(f"LCG 初始化参数: seed={self.seed}\n a={self.a}\n b={self.b}\n m={self.m}")

def next(self):
self.seed = (self.seed * self.a + self.b) % self.m
return self.seed
binary_flag = ''.join(f"{byte:08b}" for byte in FLAG1)
m = [int(bit) for bit in binary_flag]

n=[]
lcg=LCG()

for i in m:
z=lcg.next()
if i == 0:
n.append(z)
else:
z=randint(0, 2**512)
n.append(z)
print(f"n={n}")
'''
n = [...]
'''

# part2
class FlagEncoder:
def __init__(self, flag: bytes, e: int = 65537):
self.flag = flag
self.e = e
self.encoded_flag = []
self.n = None
self.c = None

def process(self):
for idx, byte in enumerate(self.flag):
self.encoded_flag.extend([idx + 0x1234] * byte)
shuffle(self.encoded_flag)
p, q = getPrime(1024), getPrime(1024)
self.n = p * q
self.c = sum(pow(m, self.e, self.n) for m in self.encoded_flag) % self.n
print(f"{self.n = }\n{self.e = }\n{self.c = }\n")

encoder = FlagEncoder(FLAG2)
encoder.process()

'''
self.n = 16880924655573626811763865075201881594085658222047473444427295924181371341406971359787070757333746323665180258925280624345937931067302673406166527557074157053768756954809954623549764696024889104571712837947570927160960150469942624060518463231436452655059364616329589584232929658472512262657486196000339385053006838678892053410082983193195313760143294107276239320478952773774926076976118332506709002823833966693933772855520415233420873109157410013754228009873467565264170667190055496092630482018483458436328026371767734605083997033690559928072813698606007542923203397847175503893541662307450142747604801158547519780249
self.e = 65537
self.c = 9032357989989555941675564821401950498589029986516332099523507342092837051434738218296315677579902547951839735936211470189183670081413398549328213424711630953101945318953216233002076158699383482500577204410862449005374635380205765227970071715701130376936200309849157913293371540209836180873164955112090522763296400826270168187684580268049900241471974781359543289845547305509778118625872361241263888981982239852260791787315392967289385225742091913059414916109642527756161790351439311378131805693115561811434117214628348326091634314754373956682740966173046220578724814192276046560931649844628370528719818294616692090359
'''

Part1 题目基于一个LCG(线性同余的伪随机数生成器),他的参数我们都不知道,但是由于FLAG1前缀是b"VNCTF{",所以可以知道LCG特定位置的值,那么可以找到一个i,使得: \[ X_i = (aX_{i-1} + b) \% m \] 这里找到的是: \[ \begin{aligned} X_{8} = (aX_{7} + b) \% m \\ X_{11} = (aX_{10} + b) \% m \\ X_{12} = (aX_{15} + b) \% m \\ X_{19} = (aX_{18} + b) \% m \end{aligned} \] 所以有: \[ a = \frac{X_{8} - X_{11}}{X_{7}-X_{10}} = \frac{X_{11}-X_{16}}{X_{10}-X_{15}} = \frac{X_{16} - X_{19}}{X_{15}-X_{18}} \] 所以: \[ \begin{aligned} (X_{8} - X_{11})(X_{10}-X_{15})-(X_{7}-X_{10})(X_{11}-X_{16}) \equiv 0 \mod m \\ (X_{11} - X_{16})(X_{15}-X_{18})-(X_{10}-X_{15})(X_{16}-X_{19}) \equiv 0 \mod m \end{aligned} \] 上面两式的左侧都是m的倍数,那他们的最大公因数很可能就是m,得到m后再利用上式求出a,b,然后反推出seed。 exp.sage:

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 getPrime, GCD
n=[...]
class LCG:
def __init__(self, seed=None, a=None, b=None, m=None):
self.m = m
self.seed = seed
self.a = a
self.b = b
#print(f"LCG 初始化参数: seed={self.seed}\n a={self.a}\n b={self.b}\n m={self.m}")

def next(self):
self.seed = (self.seed * self.a + self.b) % self.m
return self.seed

p1 = (n[8]-n[11])*(n[10]-n[15]) - (n[7]-n[10])*(n[11]-n[16])
p2 = (n[11]-n[16])*(n[15]-n[18]) - (n[10]-n[15])*(n[16]-n[19])
p = (GCD(p1, p2))
a = (n[8] - n[11])*pow(n[7] - n[10], -1, p) % p
b = (n[8] - a*n[7]) % p
seed = (n[0] - b)*pow(a, -1, p) % p
lcg = LCG(seed, a, b, p)
FLAG1 = ""
for i in range(len(n)):
if n[i] == lcg.next():
FLAG1 = FLAG1 + "0"
else:
FLAG1 = FLAG1 + "1"
FLAG1 = long_to_bytes(int(FLAG1, 2))
print(FLAG1)
# b'VNCTF{Happy_New_Year_C0ngratu1at'
Part2 题目中的密文c可以如下表示: \[ c = \sum^{len(FLAG2)-1}_{i=0} m_{i}*a_{i} \\ a_i = (i + 0x1234)^e \ \%n \] 由于FLAG2的长度未知,这里只知道他的长度小于69,但是我们还是可以假设长度为68,这样如果实际上没有这么长,那也就对应到\(m_i=0\)的情况。 所以现在的问题就是如何解上面的多元线性方程组了,这里一共68个变量,但我们只有一个等式,所以这个方程实际上是有无穷多个解。难道就没办法求解了吗,其实我们还漏掉了一些信息,那就是这里的线性方程组都是整数,而且我们要求的未知量\(m_i\)相比系数\(a_i\)要小的多。前面无穷多解的结论是建立在实数域上的,这里满足上述条件的解是有限的。而找到这个解的方法就是使用格基规约算法,我们找下面这样的格\(A\):

\[ \begin{pmatrix} a_0 & 1 & 0 & \cdots & 0\\ a_1 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{67} & 0 & 0 & \cdots & 1 \\ c & 0 & 0 & \cdots & 0 \\ \end{pmatrix}_{68 \times 68} \] 这个格满足如下的线性关系: \[ (m_0, m_1 \cdots, m_{67}, -1)\begin{pmatrix} a_0 & 1 & 0 & \cdots & 0\\ a_1 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{67} & 0 & 0 & \cdots & 1 \\ c & 0 & 0 & \cdots & 0 \\ \end{pmatrix}_{68 \times 68} = (0, m_0, m_1, \cdots, m_{67}) \] 所以\((0, m_0, m_1, \cdots, m_{67})\)就是格中的一个短向量,我们对格使用格基规约算法就很有可能得到这个短向量。 exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 16880924655573626811763865075201881594085658222047473444427295924181371341406971359787070757333746323665180258925280624345937931067302673406166527557074157053768756954809954623549764696024889104571712837947570927160960150469942624060518463231436452655059364616329589584232929658472512262657486196000339385053006838678892053410082983193195313760143294107276239320478952773774926076976118332506709002823833966693933772855520415233420873109157410013754228009873467565264170667190055496092630482018483458436328026371767734605083997033690559928072813698606007542923203397847175503893541662307450142747604801158547519780249
e = 65537
c = 9032357989989555941675564821401950498589029986516332099523507342092837051434738218296315677579902547951839735936211470189183670081413398549328213424711630953101945318953216233002076158699383482500577204410862449005374635380205765227970071715701130376936200309849157913293371540209836180873164955112090522763296400826270168187684580268049900241471974781359543289845547305509778118625872361241263888981982239852260791787315392967289385225742091913059414916109642527756161790351439311378131805693115561811434117214628348326091634314754373956682740966173046220578724814192276046560931649844628370528719818294616692090359
length = 68
m = []
for i in range(length):
m.append(pow(i + 0x1234, e, n))
M = column_matrix(ZZ, m + [c])
M = M.augment(identity_matrix(ZZ, length+1))
M = M.stack(vector(ZZ, [n] + [0]*(length+1)))
MLLL = M.LLL()
f = -MLLL[0]
FLAG2 = b""
for i in f:
if i >= 32 and i <= 127:
FLAG2 += bytes([i])
print(FLAG2)
print(FLAG1 + FLAG2)
# b'i0ns_On_Rec0vering_The_Messages}'
# b'VNCTF{Happy_New_Year_C0ngratu1ati0ns_On_Rec0vering_The_Messages}'

ss0Hurt!

题目:

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 flag import flag

class DaMie:
def __init__(self, flag , n = None):
self.m = ZZ(bytes_to_long(flag))
self.n = n if n else getPrime(1024)
self.P = Zmod(self.n)
print(f'n = {self.n}')

def process(self, x, y, z):

return vector([5 * x + y - 5 * z, 5 * y - z, 5 * z])

def Mat(self, m):
PR = self.P['x,y,z']
x,y,z = PR.gens()

if m != 0:
plana = self.Mat(m//2)
planb = plana(*plana)
if m % 2 == 0:
return planb
else:
return self.process(*planb)
else:
return self.process(*PR.gens())

def hash(self, A, B, C):
return self.Mat(self.m)(A, B, C)

if __name__ == '__main__':

Ouch = DaMie(flag)
result = Ouch.hash(2025,208,209)
print(f'hash(A,B,C) = {result}')

题目中的process方法实际上实现了一个如下的线性变换: \[ M = \left(\begin{matrix} 5 & 0 & 0\\ 1 & 5 & 0\\ -5&-1 & 5\\ \end{matrix} \right) \] 题目中的Mat方法实现了一个类似矩阵快速幂的算法,之所以是类似,是因为快速幂算法中,当m=0时,返回值是一个恒等变换的结果,但这里又返回了经过\(M\)变换后的结果,所以当输入为flag时,得到的实际上时\(M^{flag+2^k}\)。我们可以不用管这个\(2^k\),因为他只会让我们最后得到的flag有1个比特的偏差,手动修复就好。

所以现在我们的问题就是已知\(M, M^n\),如何求\(n\)。 对于矩阵\(M^n\)的求解,可以做如下操作: \[ M = \left(\begin{matrix} 0 & 0 & 0\\ 1 & 0 & 0\\ -5&-1 & 0\\ \end{matrix} \right) + \left(\begin{matrix} 5 & 0 & 0\\ 0 & 5 & 0\\ 0 & 0 & 5\\ \end{matrix} \right) = K + 5I \] 而: \[ K^3 = \mathbf{0} \] 所以对\((K+5I)^n\)用二项式定理: \[ M^n = (K + 5I)^n = C^2_nK^2(5I)^{n-2} + C^1_nK(5I)^{n-1}+(5I)^n \\ = \left(\begin{matrix} 5^n & 0 & 0\\ n5^{n-1} & 5^n & 0\\ a_{31} & -n5^{n-1} & 5^n\\ \end{matrix} \right) \] 所以: \[ (2025,208,209)M^n = (A, 2028*5^n-2029*n5^{n-1}, 2029*5^n) = (A, B, C) \] 根据上面向量相等,可以提取出下面两个等式: \[ 2028*5^n-2029*n5^{n-1} = B \\ 2029*5^n = C \] 我们把\(n, 5^n\)看作两个新的未知量,直接解方程组就可以得到\(n\)

exp.sage:

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
h_A, h_B, h_C = (17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910, 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036, 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071)
A, B, C = [2025, 208, 209]
n = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823
K_5 = h_C * pow(C, -1, n) % n
K = 5*(B*K_5 - h_B)*pow(C*K_5, -1, n) % n
print(long_to_bytes(int(K)))
b'VNCTF{WWhy_diagonalization_1s_s0_brRRRrRrrRrrrRrRRrRRrrrRrRrRuUuUUUTTTtte3333?????ouch!ouch!Th3t_is_S0_Crazy!!!!}'

并非RC4

题目:

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
from Crypto.Util.number import *
from sympy import *
import random
from secret import small_key, flag

#你能找到这个实现错在哪吗
def faulty_rc4_encrypt(text):
data_xor_iv = []
sbox = []
j = 0
x = y = k = 0
key = small_key

for i in range(256):
sbox.append(i)
else:
for i in range(256):
j = j + sbox[i] + ord(key[i % len(key)]) & 255
sbox[i] = sbox[j]
sbox[j] = sbox[i]
else:
for idx in text:
x = x + 1 & 255
y = y + sbox[x] & 255
sbox[x] = sbox[y]
sbox[y] = sbox[x]
k = sbox[sbox[x] + sbox[y] & 255]
data_xor_iv.append(idx^k^17)
return data_xor_iv


def main():
mt_string = bytes([random.getrandbits(8) for _ in range(40000)])
encrypted_data = faulty_rc4_encrypt(mt_string)

p = nextprime(random.getrandbits(512))
q = nextprime(random.getrandbits(512))
n = p * q
e = 65537

flag_number = bytes_to_long(flag.encode())
encrypted_flag = pow(flag_number, e, n)

with open("data_RC4.txt", "w") as f:
f.write(str(encrypted_data))

print("n =", n)
print("e =", e)
print("encrypted_flag =", encrypted_flag)

if __name__ == "__main__":
main()


'''
n = 26980604887403283496573518645101009757918606698853458260144784342978772393393467159696674710328131884261355662514745622491261092465745269577290758714239679409012557118030398147480332081042210408218887341210447413254761345186067802391751122935097887010056608819272453816990951833451399957608884115252497940851
e = 65537
encrypted_flag = 22847144372366781807296364754215583869872051137564987029409815879189317730469949628642001732153066224531749269434313483657465708558426141747771243442436639562785183869683190497179323158809757566582076031163900773712582568942616829434508926165117919744857175079480357695183964845638413639130567108300906156467

'''

这题RC4的实现的问题出在了swap部分:

1
2
sbox[i] = sbox[j]  
sbox[j] = sbox[i]

这样导致的在多次进行交换后,sbox中的值会慢慢同化,而这题在加密后面20000bits的数据时,sbox中的值已经完全一样了,所以可以枚举sbox,得到后面20000bits的数据,这20000bits的数据,用来破解python的随机数系统完全足够了,之后就可以预测后面的素数生成,求解RSA了。 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
from random import getrandbits, setstate, getstate
from tqdm import trange
from sympy import nextprime
from Crypto.Util.number import long_to_bytes

SAMPLES = 20000//8
M = []
for i in trange(19968):
state = [int(0) for _ in range(624)]
state[i//32] = int(1 << (31 - (i%32)))
setstate((3, tuple(state+[int(624)]), None))
[getrandbits(8) for _ in range(40000-SAMPLES)]
v = []
for _ in range(SAMPLES):
v += [int(j) for j in bin(int(getrandbits(8)))[2:].zfill(8)]
M.append(v)
M = matrix(GF(2), M)

# print(M.dimensions())
# print(M.rank())
# (19968, 20000)
# 19937

KK = M[:32, list(range(32, 19968))]
print(KK.dimensions())
MM = M[32:, list(range(32, 19968))]
print(MM.dimensions())
print(MM.rank())
MM_inv = MM^(-1)
a0 = matrix(GF(2), [[1] + [0]*31])

C = [...] # data_RC4.txt
n = 26980604887403283496573518645101009757918606698853458260144784342978772393393467159696674710328131884261355662514745622491261092465745269577290758714239679409012557118030398147480332081042210408218887341210447413254761345186067802391751122935097887010056608819272453816990951833451399957608884115252497940851
e = 65537
encrypted_flag = 22847144372366781807296364754215583869872051137564987029409815879189317730469949628642001732153066224531749269434313483657465708558426141747771243442436639562785183869683190497179323158809757566582076031163900773712582568942616829434508926165117919744857175079480357695183964845638413639130567108300906156467
for sbox in trange(256):
# print(sbox)
v = []
for i in C[40000-SAMPLES:]:
v += [int(j) for j in bin(i^^17^^sbox)[2:].zfill(8)]
s = matrix(GF(2), [v[32: 19968]])
v = s + a0*KK
sol = v*MM_inv
final_state = a0.list()+sol.list()
state = [int("".join([str(j) for j in final_state[32*i:32*i+32]]), 2) for i in range(624)]
if state[0] != 1<<31:
continue
setstate((3, tuple(state+[int(624)]), None))
[getrandbits(8) for _ in range(40000)]
p = nextprime(getrandbits(512))
if n%p == 0:
print(p)
break
q = n//p
d = pow(e, -1, (p-1)*(q-1))
flag = pow(encrypted_flag, d, n)
print(long_to_bytes(int(flag)))
# VNCTF{FL4w3d_RC4_C0nv3rg3s_2_123_4nd_M1nd_Sm4ller_MT_Brut3}

*fwshikaku

题目:

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
from Crypto.Util.number import getPrime 
from sympy import nextprime
from secret import FLAG
import numpy as np
import random
import signal
import os


def _handle_timeout(signum, frame):
raise TimeoutError('function timeout')

timeout = 450
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

def uniform_sample(n, bound, SecureRandom):
return [SecureRandom.randrange(-bound, bound) for _ in range(n)]

def choice_sample(n, L, SecureRandom):
return [SecureRandom.choice(L) for i in range(n)]

n = 197
m = 19700
q = getPrime(20)

e_L = [random.randrange(0, q-1) for i in range(2)]
R_s = random.SystemRandom()
R_e = random.SystemRandom()

s = np.array(uniform_sample(n, q//2, R_s))
e = np.array(choice_sample(m, e_L, R_e))

seed = os.urandom(16)
R_A = random
R_A.seed(seed)
A = np.array([uniform_sample(n, q, R_A) for _ in range(m)])
b = (A.dot(s) + e) % q

print(f"{q = }")
print(f"{e_L = }")
print(f"{seed.hex() = }")
print(f"{b.tolist() = }")

s_ = input("Give me s: ")
if s_ == str(s.tolist()):
print("Congratulations! You have signed in successfully.")
print(FLAG)
else:
print("Sorry, you cannot sign in.")

这题比赛的时候就有思路了,但是没写出来,因为当时的思路是求解一个19700维的方程组,但是我这内存不够,每次使用sage的求解器都会奔溃,而且sage的solve_right方法默认是单线程的,所以就算内存够,时间也不够,因为题目给了450s的限时。赛后升级了一下内存,也顺便研究了一下solve_right的多线程,就把这题复刻了一遍。 #### 思路 这题具体的思路如下: 题目会生成一个秘密向量\(\mathbf{s}\),然后将\(\mathbf{s}\)进行如下操作: \[ \mathbf{c}_{19700 \times 1} = \mathbf{A}_{19700 \times 197} \mathbf{s}_{197 \times 1} + \mathbf{e}_{19700 \times 1} \]

然后把\(\mathbf{c}, \mathbf{A}\)发送给我们,如果我们能找到\(\mathbf{s}\)就能获得flag。这题关键在于我们不知道\(\mathbf{e}\),但是只知道\(\mathbf{e}\)中的每个分量都是从e_L这个列表二选一得到的,所以对于\(\mathbf{A}\)的每行,我们可以得到: \[ \begin{gather} c_i = (a_{i0}, a_{i1}, \cdots, a_{i196}) \begin{pmatrix} s_0\\ s_1\\ \vdots\\ s_{196}\\ \end{pmatrix} + e\_L[0] \\ \mathrm{or} \\ c_i = (a_{i0}, a_{i1}, \cdots, a_{i196}) \begin{pmatrix} s_0\\ s_1\\ \vdots\\ s_{196}\\ \end{pmatrix} + e\_L[1] \end{gather} \]

稍微变形得: \[ \begin{gather} a_{i0}s_0 + a_{i1}s_1 + \cdots + a_{i196}s_{196} + e\_L[0] - c_i = 0 \\ \mathrm{or}\\ a_{i0}s_0 + a_{i1}s_1 + \cdots + a_{i196}s_{196} + e\_L[1] - c_i = 0 \end{gather} \] 虽然这两个等式不知道哪一个会成立,但是我们能得出下面这个式子一定成立: \[ (a_{i0}s_0 + a_{i1}s_1 + \cdots + a_{i196}s_{196} + e\_L[0] - c_i)*(a_{i0}s_0 + a_{i1}s_1 + \cdots + a_{i196}s_{196} + e\_L[1] - c_i) = 0 \] 这个方程是二次的,含有197未知量,即使我们能获取到19700个这样的等式,想要求解他们也是很困难的,所以我们可以采取以下措施来将方程行线性化,我们直接打开上面的括号: \[ \begin{gather} a_{i0}^2s_{0}^2 + a_{i1}^2s_{1}^2 + \cdots + a_{i196}^2s_{196}^2 + \\ 2a_{i0}a_{i1}s_{0}s_{1} + 2a_{i0}a_{2}s_{i0}s_{2} + \cdots + 2a_{i195}a_{i196}s_{195}s_{196} + \\ a_{i0}(e\_L[0]+e\_L[1]-2c_i)s_{0} + a_{i1}(e\_L[0]+e\_L[1]-2c_i)s_{1} + \cdots + a_{i196}(e\_L[0]+e\_L[1]-2c_i)s_{196} \\ = (c_i-e\_L[0])(c_i-e\_L[1]) \end{gather} \] 打开后我们发现等号左边刚好19700项,所以我们可以把左边的每一项的未知量都用一个新的未知量代替: \[ a_{i0}^2x_{0} + a_{i1}^2x_{1} + \cdots + a_{i196}(e\_L[0]+e\_L[1]-2c_i)x_{19699} = (c_i-e\_L[0])(c_i-e\_L[1]) \] 这样就得到了一个19700个未知量的线性方程了,而这样的方程一共有19700个,所以我们就可以用sage的solve_right求解了。

多线程solve_right

sage的线性代数操作是基于BLAS(Basic Linear Algebra Subprograms)接口的,而对于这个接口的实现,一般都是操作系统自带的实现,它主要保证了稳定性,但在效率方面一般,而且不能使用多线程,所以这里我们需要把这个默认的实现更换掉,这里我换成了openblas: 通过sudo pacman -S openblas安装openblas, 通过sudo pacman -S blas-openblas安装blas-openblas,这个包会将系统默认 blas 替换为 openblas。

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
import random
from Crypto.Util.number import *
import numpy as np
from concurrent.futures import ProcessPoolExecutor
from time import time
from pwn import *

def uniform_sample(n, bound, SecureRandom):
return [SecureRandom.randrange(-bound, bound) for _ in range(n)]

def choice_sample(n, L, SecureRandom):
return [SecureRandom.choice(L) for i in range(n)]


io = remote("node.vnteam.cn", 47987)
q = int(io.recvline().decode().strip().split(" = ")[1])
e_L = eval(io.recvline().decode().strip().split(" = ")[1])
seed = bytes.fromhex(io.recvline().decode().strip().split(" = ")[1].strip("'"))
b = eval(io.recvline().decode().strip().split(" = ")[1])


print("数据收集完成")
R_A = random
R_A.seed(seed)

A = [uniform_sample(197, q, R_A) for _ in range(19700)]

def get_row_task(begin, end):
M_i = random_matrix(ZZ, end-begin, 19700)
row = [0] * 19700 # 初始化一行数据ZZ
for k in range(begin, end):
for i in range(197):
row[i] = A[k][i] ** 2
cnt = 197
for i in range(197):
for j in range(i + 1, 197):
row[cnt] = 2 * A[k][i] * A[k][j]
cnt += 1
for i in range(197):
row[cnt] = A[k][i] * (e_L[0] + e_L[1] - 2 * b[k])
cnt += 1
M_i[k-begin] = row
return M_i

begin = time.time()
dim = 19700
num = 8
gap = dim // num
M = matrix(GF(q), [[0 for i in range(19700)]])
with ProcessPoolExecutor(max_workers=num) as executor:
future_all = [executor.submit(get_row_task, gap*i, gap*(i+1)) for i in range(num)] + [executor.submit(get_row_task, gap*8, dim)]
for future in future_all:
M = M.stack(future.result())
M = M[1:]
end = time.time()
print(f"矩阵 M 填充完成,耗时{end-begin}s")

begin = time.time()
y = []
for i in range(dim):
y.append(-(b[i]-e_L[0])*(b[i]-e_L[1]))
y = vector(GF(q), y)
x = M.solve_right(y)
end = time.time()
print(f"求解完成,耗时{end-begin}s")
s = x[-197:].change_ring(ZZ).list()
for i in range(len(s)):
if s[i] >= q//2:
s[i] -= q
s = np.array(s)
io.recvuntil(b"Give me s: ")
io.sendline(str(s.tolist()).encode())
print(io.recvline())
flag = io.recvline()
print(flag)
1
2
3
矩阵 M 填充完成,耗时103.08421277999878s
求解完成,耗时145.3967547416687s
VNCTF{Wh3%_th3rr0R_c@nd1d@t3s_0f_L3@rn1n9-w1tH-3r^20r_1s_sm4ll,it_WoulD_b3-R3411Y_D4ng3r0us!!}