2025VNCTF-Crypto-WP

Posted on Edited on

只写了密码部分和一道杂项，最后离比赛结束还有几十秒的时候发现自己从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!!}