VNCTF2025_Crypto

2025/2/16 CTF CTF Crypto Writeup

Simple prediction

task.py

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

明文的二进制序列，如果明文是0，则增加lcg的结果，否则，是随机数

由于flag是VNCTF打头的，而且字符是8位，由于ascii码的限制，最高位是0.所以每8个一组，我们列三个方程就可以解a,b,m

exp1

from Crypto.Util.number import long_to_bytes, isPrime, inverse
FLAG1 = b"VNCTF{"
binary_flag = ''.join(f"{byte:08b}" for byte in FLAG1)
sample = [int(bit) for bit in binary_flag]
n=[...]
PR = PolynomialRing(ZZ, names = ['seed', 'a', 'b'])
seed, a, b = PR.gens()
poly = []
tmp = seed
for idx, val in enumerate(sample):
    tmp = a * tmp + b 
    if val == 0:
        poly.append(tmp - n[idx])
Ideal(poly).groebner_basis()
'''
[seed + 2165903508073506623994838827066532958941139554558794270016694649783805145530913119818321131856946871239910300387306903547575263070144295368326573844536005, a + 429873896302458910672986962586276737599414094876069899060035489494025286474462816078224557288966599271476609468200373372521963415875150647376511007465212, b + 1589404022992814210771169508378145412844556443333866647707390024788331812145300690677773046411734443033110788720862387777824656124349529846537194036826450, 10916943396243271758266829435555189967315413084893315714705045128417174415341289341427433287377943483933876693839607971139318822507789476490876054697833171]
'''
m = 10916943396243271758266829435555189967315413084893315714705045128417174415341289341427433287377943483933876693839607971139318822507789476490876054697833171
a = -429873896302458910672986962586276737599414094876069899060035489494025286474462816078224557288966599271476609468200373372521963415875150647376511007465212 % m
b = -1589404022992814210771169508378145412844556443333866647707390024788331812145300690677773046411734443033110788720862387777824656124349529846537194036826450 % m
seed = (n[0] - b) * inverse(a, m) % m
tmp = seed
flag1 ='' 
for i in n:
    tmp = (a * tmp + b) % m
    if tmp == i:
        flag1 += '0'
    else:
        flag1 += '1'
print(long_to_bytes(int(flag1, 2))) #
#b'VNCTF{Happy_New_Year_C0ngratu1at'

part2

背包问题

$\begin{pmatrix} m_0 & m_1 & \dots & m_i & 1 & k \end{pmatrix} \begin{pmatrix} 1 & 0 & \dots & 0 & 0 & (0x1234 + 0)^e \\ 0 & 1 & \dots & 0 & 0 & (0x1234 + 1)^e \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & (0x1234 + i)^e \\ 0 & 0 & \dots & 0 & 1 & -c \\ 0 & 0 & \dots & 0 & 0 & n \end{pmatrix} = \begin{pmatrix} m_0 & m_1 & \dots & m_i & 1 & 0 \end{pmatrix}$

由于flag不超过100位，所以我们要做range(32,68)次LLL

exp2

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
import sys

n = 16880924655573626811763865075201881594085658222047473444427295924181371341406971359787070757333746323665180258925280624345937931067302673406166527557074157053768756954809954623549764696024889104571712837947570927160960150469942624060518463231436452655059364616329589584232929658472512262657486196000339385053006838678892053410082983193195313760143294107276239320478952773774926076976118332506709002823833966693933772855520415233420873109157410013754228009873467565264170667190055496092630482018483458436328026371767734605083997033690559928072813698606007542923203397847175503893541662307450142747604801158547519780249
e = 65537
c = 9032357989989555941675564821401950498589029986516332099523507342092837051434738218296315677579902547951839735936211470189183670081413398549328213424711630953101945318953216233002076158699383482500577204410862449005374635380205765227970071715701130376936200309849157913293371540209836180873164955112090522763296400826270168187684580268049900241471974781359543289845547305509778118625872361241263888981982239852260791787315392967289385225742091913059414916109642527756161790351439311378131805693115561811434117214628348326091634314754373956682740966173046220578724814192276046560931649844628370528719818294616692090359
for t in tqdm(range(32, 68)):
    b = []
    for i in range(t):
        b.append(pow(0x1234 + i, e, n))
    L = block_matrix([[identity_matrix(t), Matrix(ZZ, t, 1), Matrix(ZZ, t, 1, b)], 
                      [Matrix(ZZ, 1, t), 1, -c], 
                      [Matrix(ZZ, 1, t), 0, n]]) 
    res = L.LLL()
    for i in res:
        if i[-1] == 0:
            new = i[:-2:]
            if all(0 < abs(j) < 255 for j in new):
                flag = ''.join([chr(abs(k)) for k in new])
                if flag.isascii():
                    print(flag)
                    sys.exit()
#i0ns_On_Rec0vering_The_Messages}

easymath

task.py

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

很简单，貌似用deepseek R1可以秒杀？就是先解个方程，然后就是开二次根的问题(Rabin)

exp

from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
import itertools
R.<x> = PolynomialRing(ZZ)
f=x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
print(f.roots())
# 定义素数和常量
p1 = int(5908636118089697338533572785710162817248001570348495067227)
p2 = int(5487564316951417093934647798659941512646442958127439071827)
p3 = int(3868765709106144154703556118635822400623994075212553582411)
N = p1 * p2 * p3
c=24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944

# 计算c在每个素数下的模
cp1 = c % p1
cp2 = c % p2
cp3 = c % p3

# 定义函数计算模平方根
def find_square_roots(cp, p):
    if pow(cp, (p-1)//2, p) != 1:
        return []
    root = pow(cp, (p+1)//4, p)
    return [root, p - root]

# 获取每个素数的平方根
roots_p1 = find_square_roots(cp1, p1)
roots_p2 = find_square_roots(cp2, p2)
roots_p3 = find_square_roots(cp3, p3)

# 生成所有可能的平方根组合
combinations = itertools.product(roots_p1, r oots_p2, roots_p3)
from sympy import Integer

# 对每个组合使用 CRT 求解
for combo in combinations:
    try:
        combo = [Integer(x) for x in combo]  # 使用 sympy 的 Integer 类型
        m, _ = crt([Integer(p1), Integer(p2), Integer(p3)], combo)

        # 验证解是否正确
        if (m * m) % N == c:
            print("Flag found:", long_to_bytes(m).decode())
            exit()
    except Exception as e:
        print("Error:", e)
#VNCTF{90dcfb2dfb21a21e0c8715cbf3643f4a47d3e2e4b3f7b7975954e6d9701d9648}

ss0Hurt!

这题是和XYCTF的fakeRSA那题一样

https://www.cnblogs.com/mumuhhh/p/18149676

task.py

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

矩阵快速幂问题：

$A^m=(PJP^{-1})^m=PJ^mP^{-1}$

使用WolframAlpha计算 j^m

https://www.wolframalpha.com/input?i=%7B%7B5%2C1%2C0%7D%2C%7B0%2C5%2C1%7D%2C%7B0%2C0%2C5%7D%7D%5En&lang=zh

$\begin{pmatrix} x' \\ y' \\ z' \end{pmatrix} = \frac{5^{m-2}}{2} \begin{pmatrix} m^{\frac{5m-2}{2}} & 50 & 10m \\ 0 & 50 & m^2 - m \\ 0 & 0 & 50 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix}$

我们把u投影到Jordan基，得到x,y,z 把v投影到Jordan基，得到x’,y’,z’

exp


from Crypto.Util.number import *
n = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823
K = Zmod(n)
A = matrix(K, [[5, 1, -5], [0, 5, -1], [0, 0, 5]])
u = vector(K, (2025, 208, 209))
v = vector(K,(17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910, 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036, 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071),)
J, P = A.jordan_form(transformation=True)
# A^n*v=u
# A=PJP^-1
# J^n*vv=uu
print(J)
vv = ~P * v
uu = ~P * u
x, y, z = uu
xx, yy, zz = vv
n = (50 * yy * z - 50 * y * zz) / (10 * z * zz)
print(long_to_bytes(int(n)))

[5 1 0]
[0 5 1]
[0 0 5]
b'\xd6NCTF{WWhy_diagonalization_1s_s0_brRRRrRrrRrrrRrRRrRRrrrRrRrRuUuUUUTTTtte3333?????ouch!ouch!Th3t_is_S0_Crazy!!!!}'

并非RC4

task.py

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未实现sbox[i],sbox[j]交换，所以在若干次后造成所有sbox值相同
#通过尾部的624*4个数据恢复随机state 需要爆破256次，每次10分钟太长
#改为每个数据取2位，爆破4次 测试数据时根据key不同数据可能不够9984
from Crypto.Util.number import *
from tqdm import trange
from random import Random

length = 19968

def construct_a_row(RNG):
    row = []
    for _ in range(length//2):
        v = RNG.getrandbits(2)
        row += [int(i) for i in bin(v)[2:].zfill(2)]
    return row

def get_state(data):
    gift = []
    for v in data:
        gift += [int(i) for i in bin(v)[2:].zfill(2)]
    RNG = Random()
    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)
    #s*L = gift
    s = L.solve_left(vector(GF(2),gift))
    init = "".join(list(map(str,s)))
    state = []
    for i in range(624):
        state.append(int(init[32*i:32*i+32],2))
    RNG2 = Random()
    RNG2.setstate((3,tuple(state+[624]),None))
    return RNG2

tdata = eval(open('data_RC4.txt').read())[-19968//2:]
for i in trange(4):
    data = [i^^(a>>6) for a in tdata] #只保留2位进行4次爆破，每次10分钟
    try:
        rng = get_state(data) #得到的是启始状态
        for _ in range(19968//2):
            tmp = rng.getrandbits(32)
        p = next_prime(rng.getrandbits(512))
        if n%p == 0:
            print(p)
            q = n//p        
            print(long_to_bytes(int(pow(encrypt_flag, inverse_mod(e,(p-1)*(q-1)) ,n))))
            break
    except:
        pass

#VNCTF{FL4w3d_RC4_C0nv3rg3s_2_123_4nd_M1nd_Sm4ller_MT_Brut3}

sh1kaku_fwr

LWE问题，数据量很大。放个师兄的blog

https://suhanhan-cpu.github.io/2025/02/09/VNCTF%20wp/#sh1kaku_fwhttps://suhanhan-cpu.github.io/2025/02/09/VNCTF%20wp/#sh1kaku_fw

LOADING

VNCTF2025_Crypto

Simple prediction

part1

exp1

part2

exp2

easymath

exp

ss0Hurt!

exp

并非RC4

sh1kaku_fwr