战绩：RP.2866 RK.30

Crypto

easymath

题目

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

exp

多项式分解得到n1,n2,n3

polynomial=x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
factor(polynomial)

# (x - 3868765709106144154703556118635822400623994075212553582411)*(x - 5487564316951417093934647798659941512646442958127439071827)*(x - 5908636118089697338533572785710162817248001570348495067227)

用sage求得有限域上开方，用crt合并解

from Crypto.Util.number import *
from sympy.ntheory.modular import crt

c = 24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
n1 = 3868765709106144154703556118635822400623994075212553582411
n2 = 5487564316951417093934647798659941512646442958127439071827
n3 = 5908636118089697338533572785710162817248001570348495067227

res1 = Zmod(n1)(c).nth_root(2, all=True)
res2 = Zmod(n2)(c).nth_root(2, all=True)
res3 = Zmod(n3)(c).nth_root(2, all=True)

for i in res1:
    for j in res2:
        for k in res3:
            m = crt([n1,n2,n3],[int(i),int(j),int(k)])
            if m is not None:
                try:
                    print(long_to_bytes(int(m[0])).decode())
                except Exception as e:
                    continue

# VNCTF{90dcfb2dfb21a21e0c8715cbf3643f4a47d3e2e4b3f7b7975954e6d9701d9648}

ss0Hurt!

题目

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

# n = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823

# hash(A,B,C) = (17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910, 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036, 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071)

exp

sage文件主要实现了矩阵快速幂的运算，最终hash(A，B，C)计算如下式子

$$hash(A,B,C) = \begin{pmatrix} 5& 1&-5\\ 1& 5&-1\\ 0& 0& 5\\ \end{pmatrix}^{m} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix}$$

小学二年级学过的线性代数告诉我们，对于矩阵由于不存在乘法交换律，所以幂运算时及其复杂。所以引出了相似对角化以此来简化幂运算，然而不是所有矩阵都能对角化，以此引出Jordan标准型（若尔当标准型）

参考文章-若尔当标准型与矩阵离散对数问题

此exp用于解决此类离散对数问题$G\cdot V=Y\ mod\ p$

from Crypto.Util.number import*
from sage.all import*

G = [[5, 1,-5],[0, 5,-1],[0, 0, 5]]
V = [2025,208,209]
Y = [17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910, 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036, 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071]

p = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823
n = 3 # 矩阵阶数

M_G = matrix(GF(p),G)
v = vector(GF(p),V)
y = vector(GF(p),Y)

J, P = M_G.jordan_form(subdivide = False,transformation = True)
t = P**-1 * v
z = P**-1 * y
lambda0 = J[n-1][n-1]

x = lambda0 * (t[n-1]*z[n-2] - t[n-2]*z[n-1]) * inverse(int(t[n-1]*z[n-1]),p) % p

print(long_to_bytes(int(x)))

# VNCTF{WWhy_diagonalization_1s_s0_brRRRrRrrRrrrRrRRrRRrrrRrRrRuUuUUUTTTtte3333?????ouch!ouch!Th3t_is_S0_Crazy!!!!}

Simple prediction

第一部分是LCG，未知a，b，m，所以用Gröbner基求解参量

output = [n[i] for i in [7,8,10,11,15,16,18,19,20,21]]

R.<a,b> = PolynomialRing(ZZ)

f1 = output[0]*a + b - output[1]
f2 = output[2]*a + b - output[3]
f3 = output[4]*a + b - output[5]
f4 = output[6]*a + b - output[7]
f5 = output[7]*a + b - output[8]
f6 = output[8]*a + b - output[9]

F = [f1,f2,f3,f4,f5,f6]
# 使用F构建一个理想的Ideal。
ideal = Ideal(F)
# 计算Ideal的Gröbner基I
I = ideal.groebner_basis()

a = ZZ(-I[0].univariate_polynomial()(0))
b = ZZ(-I[1].univariate_polynomial()(0))
m = ZZ(I[2])

print(a%m)
print(b%m)
print(n)

# a = 10487069499940812847593842472968913229715998990017245815645009638923149128866826525349208730088976884662400084371407597766796859091914325843499543690367959
# b = 9327539373250457547495659927177044554470856641559449066997655103628842603195988650749660240966209040900765905118745583361494166383439946644338860661006721
# m = 10916943396243271758266829435555189967315413084893315714705045128417174415341289341427433287377943483933876693839607971139318822507789476490876054697833171

然后恢复前半段flag

from Crypto.Util.number import *

class LCG:
    def __init__(self, seed=None, a=None, b=None, m=None):
        if not m:
            self.m = getPrime(512)
        else:
            self.m = m
        if not seed:
            self.seed = getPrime(512)
        else:
            self.seed = seed
        if not a:
            self.a = getPrime(512)
        else:
            self.a = a
        if not b:
            self.b = getPrime(512)
        else:
            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

a = 10487069499940812847593842472968913229715998990017245815645009638923149128866826525349208730088976884662400084371407597766796859091914325843499543690367959
b = 9327539373250457547495659927177044554470856641559449066997655103628842603195988650749660240966209040900765905118745583361494166383439946644338860661006721
m = 10916943396243271758266829435555189967315413084893315714705045128417174415341289341427433287377943483933876693839607971139318822507789476490876054697833171

lcg = LCG(n[0],a,b,m)

binary = "0"
for i in range(1,32*8):
    tmp = lcg.next()
    if n[i] == tmp:
        binary += "0"
    else:
        binary += "1"

print(long_to_bytes(int(binary,2)))

# VNCTF{Happy_New_Year_C0ngratu1at

第二部分虽然分解不了n，但是$m_i$也是已知的，也就是$m_i^e$已知，需要知道的是有多少个$m_i^e$相加便能恢复出字节，同时根据flag长度可以得到$i<68$（好像背包密码）

$$\sum_{i=0}^{68}(m_i^emod\ n)\cdot byte_i\equiv c\ mod\ n$$

据此可以构造格如下（byte用b简写）

$$(b_1,b_2,\dots,b_n,-1,-k) \begin{pmatrix} 1& 0& \dots& 0& 0& m_0^e\\ 0& 1& \dots& 0& 0& m_1^e\\ \vdots&\vdots&\ddots&\vdots&\vdots& \vdots\\ 0& 0& \dots& 1& 0& m_{68}^e\\ 0& 0& \dots& 0& 1& c\\ 0& 0& \dots& 0& 0& n\\ \end{pmatrix} =(b_1,b_2,\dots,b_n,-1,0)$$

粗略计算一下行列式和向量模，发现不用配平，即可得到下面的exp

e = 0x10001
n = 16880924655573626811763865075201881594085658222047473444427295924181371341406971359787070757333746323665180258925280624345937931067302673406166527557074157053768756954809954623549764696024889104571712837947570927160960150469942624060518463231436452655059364616329589584232929658472512262657486196000339385053006838678892053410082983193195313760143294107276239320478952773774926076976118332506709002823833966693933772855520415233420873109157410013754228009873467565264170667190055496092630482018483458436328026371767734605083997033690559928072813698606007542923203397847175503893541662307450142747604801158547519780249
c = 9032357989989555941675564821401950498589029986516332099523507342092837051434738218296315677579902547951839735936211470189183670081413398549328213424711630953101945318953216233002076158699383482500577204410862449005374635380205765227970071715701130376936200309849157913293371540209836180873164955112090522763296400826270168187684580268049900241471974781359543289845547305509778118625872361241263888981982239852260791787315392967289385225742091913059414916109642527756161790351439311378131805693115561811434117214628348326091634314754373956682740966173046220578724814192276046560931649844628370528719818294616692090359
l = 68
ms = [pow(0x1234+i,e,n) for i in range(l)]
ge = [[0]*(l+2) for _ in range(l+2)]
for i in range(l):
    ge[i][i]  = 1
    ge[i][-1] = ms[i]
ge[-2][-2] = 1
ge[-2][-1] = c
ge[-1][-1] = n

Ge = Matrix(ZZ,ge).LLL()[0]

ans = ""
for i in Ge[:-2]:
    ans += chr(abs(i))
print(ans)

# i0ns_On_Rec0vering_The_Messages}

并非RC4 | 复现

第一次碰到MT19937已知特定bit位逆向的题目，记录一下，似乎是个板子

题目

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

'''

exp

from Crypto.Util.number import * 
from random import * 
from tqdm import * 
from sage.all import * 
import sympy 
 
data =  ?
def construct_a_row(RNG): 
    row = [] 
    # 先消耗掉前29999个随机数 
    for _ in range(29999): 
        RNG.getrandbits(8) 
     
    # 获取接下来的9984个随机数的前2位 
    for _ in range(9984): 
        # 获取8位随机数,右移6位只保留前2位 
        bits = RNG.getrandbits(8) >> 6 
        # 转换为二进制并填充到2位 
        row += list(map(int, bin(bits)[2:].zfill(2))) 
   
    return row 
 
# 构造线性方程组的矩阵 
L = [] 
for i in trange(19968): 
    state = [0]*624  # MT19937使用624个32位整数作为状态 
    # 构造一个只有一位为1,其他都为0的序列 
    temp = "0"*i + "1"*1 + "0"*(19968-1-i) 
    # 将这个序列分成624段,每段32位,转换为整数 
    for j in range(624): 
        state[j] = int(temp[32*j:32*j+32], 2) 
     
    RNG = Random() 
    RNG.setstate((3,tuple(state+[624]),None)) 
    L.append(construct_a_row(RNG)) 
 
# 将L转换为GF(2)上的矩阵（二进制域） 
L = Matrix(GF(2),L) 
 
def cul(xor): 
    try: 
        # 构造目标向量R 
        R = [] 
        for i in range(29999, 39983): 
            # 对数据进行异或处理 
            num = data[i] >> 6 
            R += list(map(int, (bin(num ^^ xor)[2:].zfill(2)))) 
         
        R = vector(GF(2), R) 
        s = L.solve_left(R)  # 这里可能会抛出异常 
         
        # 将解转换为二进制字符串 
        init = "".join(list(map(str,s))) 
        state = [] 
        # 将解重新分割成624个32位整数 
        for i in range(624): 
            state.append(int(init[32*i:32*i+32],2)) 
 
        # 创建新的RNG并设置恢复出的状态 
        RNG1 = Random() 
        RNG1.setstate((3,tuple(state+[624]),None)) 
 
        for _ in range(40000): 
            RNG1.getrandbits(8) 
 
        p = sympy.nextprime(RNG1.getrandbits(512)) 
        q = sympy.nextprime(RNG1.getrandbits(512)) 
        n = 26980604887403283496573518645101009757918606698853458260144784342978772393393467159696674710328131884261355662514745622491261092465745269577290758714239679409012557118030398147480332081042210408218887341210447413254761345186067802391751122935097887010056608819272453816990951833451399957608884115252497940851 
        e = 65537 
        encrypted_flag = 22847144372366781807296364754215583869872051137564987029409815879189317730469949628642001732153066224531749269434313483657465708558426141747771243442436639562785183869683190497179323158809757566582076031163900773712582568942616829434508926165117919744857175079480357695183964845638413639130567108300906156467 
        phi = (p-1)*(q-1) 
        d = inverse(e,phi) 
        flag = pow(encrypted_flag,d,n) 
        print(f"For xor value {xor}:") 
        print(long_to_bytes(int(flag))) 
         
    except Exception as e: 
        print(f"Attempt with xor={xor} failed: {str(e)}") 
        pass  # 直接继续下一次循环 
 
# 主循环 
print("Starting brute force...") 
for i in range(4): 
    cul(i) 
print("Brute force completed.") 

# VNCTF{FL4w3d_RC4_C0nv3rg3s_2_123_4nd_M1nd_Sm4ller_MT_Brut3}

Misc

VN_lang

为啥要一个个猜，直接逆向shift+F12，如果没有加密flag得话，直接就能找到

幸好没加密

VNCTF{Q1VpT6NfR6AEQwE3uZ9jjJwwyBKhzW8MtJld364qVxvHR}

ezSignal

Win的资源管理器无法解压缩，winrar也不行，不知道为啥。换kali用命令行

unzip ezSignal_fix.zip

然后无名称文件是使用GNU radio写的grc文件，手动补全后缀

对图片binwalk分离出两个flag.txt

然后查看原grc文件，发现是NBFM发射器脚本。

于是按源码反向操作得到如图的grc文件

然后解调的到wav文件，播放很有sstv的特色

用kali的qsstv抄收得到

Aztec码扫描得到flag

VNCTF{W0w_Y0u_Ar3_G0od_4t_R4di0_S1gn4L}