VNCTF2025

签到

欢迎

/proc/self/environ读取环境变量

sed匹配后使用&符号可以再次引用匹配到的字符

Crypto

easymath

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

PYTHON

解方程+AMM开根+CRT

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
86
87
88
89
90
91
92
from Crypto.Util.number import *
from sympy import symbols, Eq, solve
from gmpy2 import *
import random
import math
a=15264966144147258587171776703005926730518438603688487721465
b=76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923
c=125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619

p, q, r= symbols('p q r')
equation1 = Eq(p+q+r, a)
equation2 = Eq(p*q+p*r+q*r, b)
equation3 = Eq(p*q*r,c)
solutions = solve((equation1, equation2,equation3), (p, q,r))
p,q,r=solutions[0]
p,q,r=int(p),int(q),int(r)

c=24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
n=p*q*r
e=2
def onemod(e, q):
    p = random.randint(1, q-1)
    while(powmod(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = powmod(p, r**(t-1)*s, q)
    b = powmod(o, r*a-1, q)
    c = powmod(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = powmod(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (powmod(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp

def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

cp = c % p
cq = c % q
cr = c % r

mp = AMM_rth(cp, e, p)
mq = AMM_rth(cq, e, q)
mr = AMM_rth(cr, e, r)

rt1 = ALL_ROOT2(e, p)
rt2 = ALL_ROOT2(e, q)
rt3 = ALL_ROOT2(e, r)

amp = ALL_Solution(mp, p, rt1, cp, e)
amq = ALL_Solution(mq, q, rt2, cq, e)
amr = ALL_Solution(mr, r, rt3, cr, e)
for x in amp:
    for y in amq:
        for z in amr:
            print(long_to_bytes(int(CRT([x,y,z],[p,q,r]))))
#VNCTF{90dcfb2dfb21a21e0c8715cbf3643f4a47d3e2e4b3f7b7975954e6d9701d9648}
PYTHON

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
37
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}')

PYTHON

参考[2024-XYCTF-wp-crypto | 糖醋小鸡块的blog](https://tangcuxiaojikuai.xyz/post/146254b2.html)

本题加密是进行一个矩阵的快速幂，flag在指数部分，所以是一个矩阵上的DLP

(51−505−1005)flag∗(a,b,c)=(A,B,C)\left( \begin{matrix} 5&1&-5\\ 0&5&-1\\ 0&0&5\\ \end{matrix} \right)^{flag}*(a,b,c)=(A,B,C)

使用jordan form:本质是解一个模p下的线性方程组

如果使用行列式方法，p-1并不光滑；如果使用一般线性群的阶，他所有的子群阶也都不光滑

jordan form原理：

任何一个非奇异矩阵L都可以通过如下方式变换成jordan form：

L=P∗J∗P−1(P−1∗L∗P)n=JnP−1∗Ln∗P=JnL=P*J*P^{-1}\\ (P^{-1}*L*P)^n=J^n\\ P^{-1}*Ln*P=J^n

（然后就看不懂了，原理一样，脚本也一样）

（最后结果高位有点问题，看不懂找不出原因）

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
from Crypto.Util.number import *

p = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823
G = Zmod(p)


L = Matrix(Zmod(p),[
    [5,1,-5],
    [0,5,-1],
    [0,0,5]
])
vec1 = (2025,208,209)
vec2 = (17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910, 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036, 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071)

vec1 = vector(Zmod(p),vec1)
vec2 = vector(Zmod(p),vec2)

M1 = Matrix(Zmod(p),Matrix(vec1).T)
M1 = M1.augment(L*vec1)
M1 = M1.augment(L^2*vec1)

M2 = Matrix(Zmod(p),Matrix(vec2).T)
M2 = M2.augment(L*vec2)
M2 = M2.augment(L^2*vec2)

R = M2*M1^(-1)

gl, P = L.jordan_form(transformation=True)
gr = P^(-1)*R*P

g = gl[0,0] 
t = gr[0,1] # t = ng^(n-1)
k = gr[1,1] # k = g^n
#so gt = nk  ->  n = gtk^(-1)

n = g * t * inverse(k,p) % p

print(long_to_bytes(int(n)))
#b'\xd6NCTF{WWhy_diagonalization_1s_s0_brRRRrRrrRrrrRrRRrRRrrrRrRrRuUuUUUTTTtte3333?????ouch!ouch!Th3t_is_S0_Crazy!!!!}'
#VNCTF{WWhy_diagonalization_1s_s0_brRRRrRrrRrrrRrRRrRRrrrRrRrRuUuUUUTTTtte3333?????ouch!ouch!Th3t_is_S0_Crazy!!!!}
PYTHON

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

# 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}")
        print(self.m,self.seed,self.a,self.b)
    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}")

# 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()
PYTHON

part1

LCG但不是连着的，当flag的二进制为1时，我们没有这个数据了。所以我们需要找到连着的数据，当然跳过一次的也算连着

例如：si+2=a2si+ab+bs_{i+2}=a^2s_i+ab+b，我们可假设a=a2,b=ab+ba=a^2,b=ab+b，也是一个LCG

我们还知道flag头为VNCTF{，二进制为010101100100111001000011010101000100011001111011

通过手动打表，到最后一串000这时，可以发现有一大串连着的数据（前面也有连着的数据，但不够多，或者试了没用）

利用这6组数据，我们可以求出模数p,a2,ab+b,seed25模数p,a^2,ab+b,seed_{25}，只有p是原来的，我们还需要还原出原来的a,b,seeda,b,seed，通过之前一题，我直接用AMM来开a2a^2了，然后b,seed0b,seed_0就迎刃而解了（最初的seed用第一个数据就好了）

然后直接正着判断是否相等，相等就代表此位为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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
from gmpy2 import *
from Crypto.Util.number import *
import random
import math
def onemod(e, q):
    p = random.randint(1, q-1)
    while(powmod(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = powmod(p, r**(t-1)*s, q)
    b = powmod(o, r*a-1, q)
    c = powmod(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = powmod(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (powmod(o, alp, q)*h)
    return result
def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp

def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li
n=eval(open('n.txt','r').read())
"""
FLAG1 = b"VNCTF{"
binary_flag = ''.join(f"{byte:08b}" for byte in FLAG1)
print(binary_flag)
'010101100100111001000011010101000100011001111011'
"""
s=[n[26],n[28],n[30],n[32],n[34],n[36]] 
t = []
l=len(s)
for i in range(1,l):
    t.append(s[i]-s[i-1])
 
all_p = []
for i in range(1,l-3):
    all_p.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1])))
for p in all_p:
    p=abs(p)
    if p==1:
        continue
    
    a=(s[2]-s[1])*invert((s[1]-s[0]),p)%p
 
    ani=invert(a,p)
    
    b=(s[1]-a*s[0])%p
 
    seed = (ani*(s[0]-b))%p
    

    mp = AMM_rth(a, 2, p)  # AMM算法得到一个解

    rt1 = ALL_ROOT2(2, p)

    amp = ALL_Solution(mp, p, rt1, a, 2)  # 得到所有的mp
    
    for a in amp:
        b=(n[32]-a*n[31])%p
        
        seed=((n[0]-b)*inverse(a,p))%p


        flag=''
        for mi in n:
            seed=(a*seed+b)%p
            if seed == mi :
                flag+='0'
            else:
                flag+='1'
        print(long_to_bytes(int(flag,2)))

    break
#b'VNCTF{Happy_New_Year_C0ngratu1at'
PYTHON

part2

格一下就行了，就爆破一下flag2的长度就好了，然后判断一下输出

自己生成测试第一个向量就是最短向量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sage.all import *
n = 16880924655573626811763865075201881594085658222047473444427295924181371341406971359787070757333746323665180258925280624345937931067302673406166527557074157053768756954809954623549764696024889104571712837947570927160960150469942624060518463231436452655059364616329589584232929658472512262657486196000339385053006838678892053410082983193195313760143294107276239320478952773774926076976118332506709002823833966693933772855520415233420873109157410013754228009873467565264170667190055496092630482018483458436328026371767734605083997033690559928072813698606007542923203397847175503893541662307450142747604801158547519780249
e = 65537
c = 9032357989989555941675564821401950498589029986516332099523507342092837051434738218296315677579902547951839735936211470189183670081413398549328213424711630953101945318953216233002076158699383482500577204410862449005374635380205765227970071715701130376936200309849157913293371540209836180873164955112090522763296400826270168187684580268049900241471974781359543289845547305509778118625872361241263888981982239852260791787315392967289385225742091913059414916109642527756161790351439311378131805693115561811434117214628348326091634314754373956682740966173046220578724814192276046560931649844628370528719818294616692090359

for l in range(1,100):
    L=Matrix(ZZ,l+2,l+2)
    for i in range(l+1):
        L[i,i]=1
        L[i,-1]=pow((i+0x1234),e,n)
    L[-2,-1]=c
    L[-1,-1]=-n
    x=L.LLL()[0]
    if abs(int(x[l-1]))==125:
        print(l,x)
        for i in x[:l]:
            print(chr(abs(int(i))),end="")
        print()
        break

#i0ns_On_Rec0vering_The_Messages}
PYTHON

并非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
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()
PYTHON

不同就是在生成key的时候不是交换而是直接覆盖了，然后最后多异或了一个17

但是我分析不出来怎么攻击，直接自己执行了一遍这个代码，发现在后面的时候idx^k^17的这个k会等于一个值，自己测试就拿30000后面的数据发现可以解出来，直接爆破这个k就好了

然后就是MT19937的8bits分析，之前遇到过好多次类似的了就不讲了

总之就是爆破，爆了1个半小时

问完出题人这就是预期解

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from sage.all import *
from Crypto.Util.number import *
from random import *
from tqdm import *

data=eval(open('data_RC4.txt','r').read())[30000:]


RNG = Random()
length = 19968
def construct_a_row(RNG):
    for _ in range(30000):RNG.getrandbits(8)
    ind = 0
    row = []
    while(1):
        t1 = bin(RNG.getrandbits(8))[2:].zfill(8)
        for tt in t1:
            row.append(int(tt))
        if(len(row) >= length):
            return row
        ind += 1
"""L = []
for i in trange(length):
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(length-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG))
L = Matrix(GF(2),L)
save(L, "matrix.sobj")"""
#自己测试的时候已经生成好了，这里节省时间
L = load("matrix.sobj")
#(123,256)
for key in trange(0,256):
    data1=[key^i^17 for i in data]
    known = []
    for i in data1:
        for j in bin(i)[2:].zfill(8):
            known+=j
        if(len(known) >= length):
            break
    try:
        s = L.solve_left(vector(GF(2),known))
    except:
        continue
    print(key)
    init = "".join(list(map(str,s)))
    state = []
    for i in range(624):
        state.append(int(init[32*i:32*i+32],2))

    def backfirst(state1):
        high = 0x80000000
        low = 0x7fffffff
        mask1 = 0x9908b0df
        tmp = state1[623] ^ state1[396]
        if tmp & high == high:
            tmp ^= mask1
            tmp <<= 1
            tmp |= 1
        else:
            tmp <<= 1
        return (1 << 32 - 1) | tmp & low, tmp & low
    seed1, seed2 = backfirst(state)
    state1 = [seed1] + state[1:]
    state2 = [seed2] + state[1:]


    n = 26980604887403283496573518645101009757918606698853458260144784342978772393393467159696674710328131884261355662514745622491261092465745269577290758714239679409012557118030398147480332081042210408218887341210447413254761345186067802391751122935097887010056608819272453816990951833451399957608884115252497940851
    e = 65537
    encrypted_flag = 22847144372366781807296364754215583869872051137564987029409815879189317730469949628642001732153066224531749269434313483657465708558426141747771243442436639562785183869683190497179323158809757566582076031163900773712582568942616829434508926165117919744857175079480357695183964845638413639130567108300906156467
    prng = Random()
    prng.setstate(tuple([3, tuple(state1+[624]), None]))
    for _ in range(40000):
        prng.getrandbits(8)
    p = next_prime(prng.getrandbits(512))
    q = next_prime(prng.getrandbits(512))
    print(p)
    print(q)
    if n==p*q:
        print(long_to_bytes(int(pow(encrypted_flag,inverse_mod(e,(p-1)*(q-1)),n))))

    prng = Random()
    prng.setstate(tuple([3, tuple(state2+[624]), None]))
    for _ in range(40000):
        prng.getrandbits(8)
    p = next_prime(prng.getrandbits(512))
    q = next_prime(prng.getrandbits(512))
    print(p)
    print(q)
    if n==p*q:
        print(long_to_bytes(int(pow(encrypted_flag,inverse_mod(e,(p-1)*(q-1)),n))))
""""
123
2849821642489040816444237149453951123096937420879364734457565300636069483308108133275885434910493679378607501786658532870247845818686651940429045958638523
9467471397205882947962218830745171049297627946722122603974372237041601408122191262161200434063435224151339148022637680690503653259129267359148432740698537
b'VNCTF{FL4w3d_RC4_C0nv3rg3s_2_123_4nd_M1nd_Sm4ller_MT_Brut3}'
"""
PYTHON

misc

VN_Lang

txt打开搜索vnctf就行

ctf > wp
#ctf
VNCTF2025
http://example.com/2025/02/09/vnctf2025/
作者
Naby
发布于
2025年2月9日
许可协议