XYCTF 2025 Crypto

因为前一天去旅游了，第二天中午才开始看

最唐的一集，整个人状态十分不佳(赛中没出的打*)

属实是唐人日记了

division

上来一看这么多解，直接先挑软柿子捏了（

题目

python

# -*- encoding: utf-8 -*-
'''
@File    :   server.py
@Time    :   2025/03/20 12:25:03
@Author  :   LamentXU 
'''
import random 
print('----Welcome to my division calc----')
print('''
menu:
      [1]  Division calc
      [2]  Get flag
''')
while True:
    choose = input(': >>> ')
    if choose == '1':
        try:
            denominator = int(input('input the denominator: >>> '))
        except:
            print('INPUT NUMBERS')
            continue
        nominator = random.getrandbits(32)
        if denominator == '0':
            print('NO YOU DONT')
            continue
        else:
            print(f'{nominator}//{denominator} = {nominator//denominator}')
    elif choose == '2':
        try:
            ans = input('input the answer: >>> ')
            rand1 = random.getrandbits(11000)
            rand2 = random.getrandbits(10000)
            correct_ans = rand1 // rand2
            if correct_ans == int(ans):
                print('WOW')
                with open('flag', 'r') as f:
                    print(f'Here is your flag: {f.read()}')
            else:
                print(f'NOPE, the correct answer is {correct_ans}')
        except:
            print('INPUT NUMBERS')
    else:
        print('Invalid choice')

这一看直接除数给 1 打 MT19937 得了

这个还不唐，写完脚本就出了

exp

python

from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from pwn import *
import re
from tqdm import *
def mt19937(bs, out):

    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
    print("solving...")
    
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    for i in trange(624):
        pyrand.getrandbits(32)
    rand1 = pyrand.getrandbits(11000)
    rand2 = pyrand.getrandbits(10000)    
    correct_ans = rand1 // rand2
    print(correct_ans)
    '''
    io.recvuntil(": >>>")
    io.sendline(b"2")
    io.sendafter(b"input the answer: >>> ",str(correct_ans).encode())'
    '''
    io.interactive()    
io=remote("47.93.96.189",20512)
out=[]
for i in trange(624):
    io.recvuntil(": >>>")
    io.sendline(b"1")
    io.recvuntil("input the denominator: >>>")
    io.sendline(b"1")
    s=io.recvline()[:-1].decode()
    numbers = re.findall(r'\d+', s)
    out.append(int(numbers[0]))
mt19937(32,out)

题目

python

from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
from secret import flag


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m)

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
'''

这个一看思路就很明确，因为次数为3，可以直接列两个方程，再一看给了高位，直接就一元coppersmith

只需要用结式将两个方程联系起来就好了

但是唐的是我刚开始把 128 看成了 120 ，绝了

浪费我半天

exp

python

from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
import itertools
from sage.matrix.matrix2 import Matrix
def resultant(f1,f2,var):
    return Matrix.determinant(f1.sylvester_matrix(f2,var))
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
PR=PolynomialRing(Zmod(n),'x,y')
x,y=PR.gens()
f=(mh[0]+x)**3-3*(mh[0]+x)*(mh[1]+y)**2-C[0]
g=3*(mh[0]+x)**2*(mh[1]+y)-(mh[1]+y)**3-C[1]
h1=resultant(f,g,y)
h2=resultant(f,g,x)
root1=h1.univariate_polynomial().monic().small_roots(X=2**128,beta=0.4,epsilon=0.01)
xx=root1[0]
root2=h2.univariate_polynomial().monic().small_roots(X=2**128,beta=0.4,epsilon=0.01)
yy=root2[0]
print(xx)
print(yy)
key=hashlib.sha256(str(mh[0]+xx+mh[1]+yy).encode()).digest()
flag=ChaCha20.new(key=key, nonce=b'Pr3d1ctmyxjj').decrypt(enc)
print(flag)

reed

题目

python

import string
import random
from secret import flag

assert flag.startswith('XYCTF{') and flag.endswith('}')
flag = flag.rstrip('}').lstrip('XYCTF{')

table = string.ascii_letters + string.digits
assert all(i in table for i in flag)
r = random.Random()

class PRNG:
    def __init__(self, seed):
        self.a = 1145140
        self.b = 19198100
        random.seed(seed)

    def next(self):
        x = random.randint(self.a, self.b)
        random.seed(x ** 2 + 1)
        return x
    
    def round(self, k):
        for _ in range(k):
            x = self.next()
        return x

def encrypt(msg, a, b):
    c = [(a * table.index(m) + b) % 19198111 for m in msg]
    return c

seed = int(input('give me seed: '))
prng = PRNG(seed)
a = prng.round(r.randrange(2**16))
b = prng.round(r.randrange(2**16))
enc = encrypt(flag, a, b)
print(enc)

这题的预期是找到不动点，但是非预期更好做，直接 gcd 搞出 a ,然后爆 b 就 ok

非预期 exp

python

from sage.all import *
from Crypto.Util.number import *
import string
import random
from tqdm import *
from pwn import *
table = string.ascii_letters + string.digits
r = random.Random()
a = 1145140
b = 19198100
class PRNG:
    def __init__(self, seed):
        self.a = 1145140
        self.b = 19198100
        random.seed(seed)

    def next(self):
        x = random.randint(self.a, self.b)
        random.seed(x ** 2 + 1)
        return x
    
    def round(self, k):
        for _ in range(k):
            x = self.next()
        return x
prng = PRNG(0)
#io=remote("39.106.48.123",34583)
#io.interactive()
ans=[8622166, 8622166, 1642584, 5715427, 8622166, 1642584, 5106812, 17325341, 1625542, 1033969, 16159237, 7439020, 3366177, 17325341, 18491445, 4532281, 17325341, 459438, 459438, 3366177, 16159237, 3940708, 18491445, 9179655, 1033969, 15584706, 3366177, 8605124, 459438, 8622166, 2808688, 8622166, 2808688, 17933956, 8622166, 4549323]
print(len(ans))
n=19198111

for i in trange(62):
    for j in range(62):
        if (GCD((-ans[3]+ans[2]+i*n),(-ans[0]+ans[2])+j*n))>1145140:
            print(i,j)

a=GCD((-ans[3]+ans[2]+0*n),(-ans[0]+ans[2])+1*n)
print(a)
b1=[]
b2=[]
for i in trange(62):
    b=(ans[0]-(a*i)%n)%n
    for j in range(62):
        if((a*j+b)%n)==ans[3]:
            b1.append(b)
for i in trange(62):
    b=(ans[0]-(a*i)%n)%n
    for j in range(62):
        if((a*j+b)%n)==ans[2]:
            b2.append(b)   
d=inverse(a,n)
for b in tqdm(b1):
    flag=""
    for i in range(len(ans)):
        t=(d*(ans[i]-b)%n)%n
        if t>61:
            continue
        else:
            flag+=table[t]
    if len(flag)==len(ans):
        print(flag)

预期 exp

python

from tqdm import trange
import string
from pwn import *

############# 1.find fixed point
def f(x):
    random.seed(x ** 2 + 1)
    return random.randint(1145140, 19198100)

if 0:
    a = 1145140
    b = 19198100
    for i in trange(a, b + 1):
        if f(f(i)) == i:
            print(i)
            # 7234044 17593903

############# 2.compute flag
table = string.ascii_letters + string.digits

def decrypt(enc, a, b):
    t = 19198111
    m = ''.join(table[(c - b) * pow(a, -1, t) % t] for c in enc)
    return m

seed = 7234044
r = process(['python3', 'reed.py'])
r.sendlineafter(b'give me seed: ', str(seed ** 2 + 1).encode())
enc = eval(r.recvline().strip().decode())
try:
    print(decrypt(enc, 17593903, 17593903))
except:
    pass
try:
    print(decrypt(enc, 7234044, 17593903))
except:
    pass
try:
    print(decrypt(enc, 7234044, 7234044))
except:
    pass
try:
    print(decrypt(enc, 17593903, 7234044))
except:
    pass

勒索病毒

题目

python

# Visit https://www.lddgo.net/string/pyc-compile-decompile for more information
# Version : Python 3.8


#Created on Sun Mar 30 18:25:08 2025

#@author: Crypto0

import re
import base64
import os
import sys
from gmssl import sm4
from Crypto.Util.Padding import pad
import binascii
from random import shuffle, randrange
from sage.all import*
N = 49 
p = 3
q = 128  
d = 3
assert q > (6 * d + 1) * p
R = PolynomialRing(ZZ,'x')
x=R.gen()
def generate_T(d1, d2):
    assert N >= d1 + d2
    s = [1] * d1 + [-1] * d2 + [0] * (N - d1 - d2)
    shuffle(s)
    return R(s)

def invert_mod_prime(f, p):
    Rp = R.change_ring(Integers(p)).quotient(x^N - 1)
    return R(lift(1 / Rp(f)))

def convolution(f, g):
    return (f * g) % (x^N - 1)

def lift_mod(f, q):
    return R([((f[i] + q // 2) % q) - q // 2 for i in range(N)])

def poly_mod(f, q):
    return R([f[i] % q for i in range(N)])

def invert_mod_pow2(f, q):
    assert q.is_power_of(2)
    g = invert_mod_prime(f, 2)
    while True:
        r = lift_mod(convolution(g, f), q)
        if r == 1:
            return g
        g = lift_mod(convolution(g, 2 - r), q)

def generate_message():
    return R([randrange(p) - 1 for _ in range(N)])

def generate_key():
    while True:
        try:
            f = generate_T(d + 1, d)
            g = generate_T(d, d)
            Fp = poly_mod(invert_mod_prime(f, p), p)
            Fq = poly_mod(invert_mod_pow2(f, q), q)
            break
        except:
            continue
    h = poly_mod(convolution(Fq, g), q)
    return h, (f, g)

def encrypt_message(m, h):
    e = lift_mod(p * convolution(h, generate_T(d, d)) + m, q)
    return e

def save_ntru_keys():
    h, secret = generate_key()
    with open("pub_key.txt", "w") as f:
        f.write(str(h))
    m = generate_message()
    with open("priv_key.txt", "w") as f:
        f.write(str(m))
    e = encrypt_message(m, h)
    with open("enc.txt", "w") as f:
        f.write(str(e))

def terms(poly_str):
    terms = []
    pattern = r'([+-]?\\s*x\\^?\\d*|[-+]?\\s*\\d+)'
    
    matches = re.finditer(pattern, poly_str.replace(' ', ''))
    
    for match in matches:
        term = match.group()
        if term == '+x' or term == 'x':
            terms.append(1)
        elif term == '-x':
            terms.append(-1)
        elif 'x^' in term:
            coeff_part = term.split('x^')[0]
            exponent = int(term.split('x^')[1])
            if not coeff_part or coeff_part == '+':
                coeff = 1
            elif coeff_part == '-':
                coeff = -1
            else:
                coeff = int(coeff_part)
            terms.append(coeff * exponent)
        elif 'x' in term:
            coeff_part = term.split('x')[0]
            if not coeff_part or coeff_part == '+':
                terms.append(1)
            elif coeff_part == '-':
                terms.append(-1)
            else:
                terms.append(int(coeff_part))
        else:
            if term == '+1' or term == '1':
                terms.append(0)
                terms.append(-0)
    return terms

def gen_key(poly_terms):
    binary = [0] * 128
    for term in poly_terms:
        exponent = abs(term)
        if term > 0 and exponent <= 127:  
            binary[127 - exponent] = 1
    binary_str = ''.join(map(str, binary))
    hex_key = hex(int(binary_str, 2))[2:].upper().zfill(32)
    return hex_key

def read_polynomial_from_file(filename):
    with open(filename, 'r') as file:
        return file.read().strip()


def sm4_encrypt(key, plaintext):
    assert len(key) == 16, "SM4 key must be 16 bytes"
    cipher = sm4.CryptSM4()
    cipher.set_key(key, sm4.SM4_ENCRYPT)
    padded_plaintext = pad(plaintext, 16)
    return cipher.crypt_ecb(padded_plaintext)

def sm4_encrypt_file(input_path, output_path, key):
    with open(input_path, 'rb') as f:
        plaintext = f.read()
    
    ciphertext = sm4_encrypt(key, plaintext)
    
    with open(output_path, 'wb') as f:
        f.write(ciphertext)

def resource_path(relative_path):
    if getattr(sys, 'frozen', False):
        base_path = sys._MEIPASS
    else:
        base_path = os.path.abspath(".")
    return os.path.join(base_path, relative_path)

def encrypt_directory(directory, sm4_key, extensions=[".txt"]):
    if not os.path.exists(directory):
        print(f"Directory does not exist: {directory}")
        return
    
    for root, _, files in os.walk(directory):
        for file in files:
            if any(file.endswith(ext) for ext in extensions):
                input_path = os.path.join(root, file)
                output_path = input_path + ".enc"
                
                try:
                    sm4_encrypt_file(input_path, output_path, sm4_key)
                    os.remove(input_path)
                    print(f"Encrypted: {input_path} -> {output_path}")
                except Exception as e:
                    print(f"Error encrypting {input_path}: {str(e)}")

def main():
    try:
        save_ntru_keys()
        poly_str = read_polynomial_from_file("priv_key.txt")
        poly_terms = terms(poly_str)
        sm4_key = binascii.unhexlify(poly_terms)
        user_name = os.getlogin()
        target_dir = os.path.join("C:\\Users", user_name, "Desktop", "test_files")
        
        if not os.path.exists(target_dir):
            os.makedirs(target_dir, exist_ok=True)
            print(f"Created directory: {target_dir}")
            return
            
        txt_files = [f for f in os.listdir(target_dir) 
                    if f.endswith('.txt') and os.path.isfile(os.path.join(target_dir, f))]
        
        if not txt_files:
            print("No .txt files found in directory")
            return
            
        for txt_file in txt_files:
            file_path = os.path.join(target_dir, txt_file)
            try:
                with open(file_path, 'rb') as f:
                    test_data = f.read()
                
                ciphertext = sm4_encrypt(sm4_key, test_data)
                encrypted_path = file_path + '.enc'
                
                with open(encrypted_path, 'wb') as f:
                    f.write(ciphertext)
            except Exception as e:
                print(f"Error processing {txt_file}: {str(e)}")
                
    except Exception as e:
        print(f"Fatal error: {str(e)}")

if __name__ == "__main__":
    main()

真的唐啊，格早就搞出来了，就直接是最简单的 NTRU，但是为啥规约出来的 f 的系数是 2 啊

害我看了好久，最后才发现是对的，真的是唐完了

exp

python

import re
import base64
import os
import sys
from gmssl import sm4
from Crypto.Util.Padding import pad,unpad
import binascii
from random import shuffle, randrange
from sage.all import *
from Crypto.Util.number import *
from tqdm import *
n= 49 
p = 3
q = 128  
d = 3
R = ZZ['x']
x = R.gen()
pubkey =  8*x**48 + 58*x**47 + 18*x**46 + 61*x**45 + 33*x**44 + 21*x**43 + 58*x**42 + 21*x**41 + 5*x**40 + 32*x**39 + 15*x**38 + 40*x**37 + 24*x**36 + 14*x**35 + 40*x**34 + 5*x**33 + x**32 + 48*x**31 + 21*x**30 + 36*x**29 + 42*x**28 + 8*x**27 + 17*x**26 + 54*x**25 + 39*x**24 + 38*x**23 + 14*x**22 + 22*x**21 + 26*x**20 + 22*x**18 + 7*x**17 + 29*x**16 + 53*x**15 + 50*x**14 + 49*x**13 + 21*x**12 + 47*x**11 + 50*x**10 + 32*x**9 + 14*x**8 + 50*x**7 + 18*x**6 + 9*x**5 + 61*x**4 + 10*x**3 + 9*x**2 + 11*x + 47
c = 31*x**48 - 14*x**47 + x**46 + 8*x**45 - 9*x**44 - 18*x**43 - 30*x**41 + 14*x**40 + 3*x**39 - 17*x**38 + 22*x**37 + 7*x**36 + 31*x**34 - 30*x**33 - 22*x**32 - 25*x**31 + 31*x**30 - 28*x**29 + 7*x**28 + 23*x**27 - 6*x**26 + 12*x**25 - 6*x**24 + 5*x**23 - 13*x**22 - 10*x**20 + 4*x**19 + 15*x**18 + 23*x**17 + 24*x**16 - 2*x**15 - 8*x**14 - 20*x**13 + 24*x**12 - 23*x**11 - 4*x**10 - 26*x**9 - 14*x**8 + 10*x**7 + 4*x**6 - 4*x**5 - 32*x**4 - 5*x**3 - 31*x**2 + 16*x + 11
c=R(c)
Rp = R.change_ring(Integers(p)).quotient(x**n - 1)
fp=Rp("-x^48 - x^46 + x^45 + x^43 - x^42 + x^41 + x^40 + x^36 - x^35 + x^34 - x^33 + x^32 - x^30 + x^29 - x^28 - x^27 - x^26 - x^25 - x^23 - x^22 + x^21 + x^20 + x^19 + x^18 - x^17 - x^16 - x^15 - x^14 - x^12 + x^9 - x^7 - x^6 - x^5 - x^4 + x^3 - x + 1")
#print(1/fp)

def invert_mod_prime(f, p):
    Rp = R.change_ring(Integers(p)).quotient(x**n - 1)
    return R(lift(1 / Rp(f)))

def mul(f,g):
    return (f * g) % (x**n-1)

def lift_mod(f, q):
    return R([((f[i] + q // 2) % q) - q // 2 for i in range(n)])
def poly_mod(f, q):
    return R([f[i] % q for i in range(n)])
def decrypt(e,pri_key):
    f,fp = pri_key
    a = lift_mod(mul(e,f),q)
    d = lift_mod(mul(a,fp),p)
    return d

def terms(poly_str):
    terms = []
    pattern = r'([+-]?\s*x\^?\d*|[-+]?\s*\d+)'
    
    matches = re.finditer(pattern, poly_str.replace(' ', ''))
    
    for match in matches:
        term = match.group()
        if term == '+x' or term == 'x':
            terms.append(1)
        elif term == '-x':
            terms.append(-1)
        elif 'x^' in term:
            coeff_part = term.split('x^')[0]
            exponent = int(term.split('x^')[1])
            if not coeff_part or coeff_part == '+':
                coeff = 1
            elif coeff_part == '-':
                coeff = -1
            else:
                coeff = int(coeff_part)
            terms.append(coeff * exponent)
        elif 'x' in term:
            coeff_part = term.split('x')[0]
            if not coeff_part or coeff_part == '+':
                terms.append(1)
            elif coeff_part == '-':
                terms.append(-1)
            else:
                terms.append(int(coeff_part))
        else:
            if term == '+1' or term == '1':
                terms.append(0)
                terms.append(-0)
    return terms

def gen_key(poly_terms):
    binary = [0] * 128
    for term in poly_terms:
        exponent = abs(term)
        if term > 0 and exponent <= 127:  
            binary[127 - exponent] = 1
    binary_str = ''.join(map(str, binary))
    hex_key = hex(int(binary_str, 2))[2:].upper().zfill(32)
    return hex_key   
def sm4_decrypt(key, ciphertext):
    assert len(key) == 16, "SM4 key must be 16 bytes"
    cipher = sm4.CryptSM4()
    cipher.set_key(key, sm4.SM4_DECRYPT)  # 设置为解密模式
    decrypted_data = cipher.crypt_ecb(ciphertext)
    plaintext = unpad(decrypted_data, 16)       # 去除填充
    return plaintext 

def get_key():
    for j in range(2 * n):
        try:
            f = R(list(M[j][:n]))
            g = R(list(M[j][n:]))
            fp = poly_mod(invert_mod_prime(f, p),p)
            print(f)
            m=decrypt(c,(f,fp))
            return m
            '''
            m=decrypt(c,(f,fp))
            poly_terms = terms(str(m))
            poly_terms=gen_key(poly_terms)
            sm4_key = binascii.unhexlify(poly_terms)
            ciphertext=bytes.fromhex("bf0cb5cc6bea6146e9c1f109df953a57daa416d38a8ffba6438e7e599613e01f3b9a53dace4ccd55cd3e55ef88e0b835")
            print(sm4_decrypt(sm4_key,ciphertext))
            '''
            #print(R(lift(1/fp)))
            #print(fp)
            #print(decrypt(c,(f,fp)))
            
            
        except Exception as e:
            # 如果需要，你可以记录或打印异常信息，帮助调试
            #print(f"Error occurred: {e}")
            pass
        
    


M = matrix(ZZ, 2*n, 2*n)

#hh = R(pubkey)
hh=poly_mod(R(pubkey),q)
for i in range(n): M[i,i] = 1

for i in range(n,2*n):
    M[i,i] = q

for i in range(n):
    for j in range(n):
            M[i, j + n] = hh[(n - i + j) % n]
  
    
#print(M)     
M = M.LLL()
#print(M)
m= get_key()
poly_str=str(m)
poly_terms = terms(poly_str)
poly_terms=gen_key(poly_terms)
print(poly_terms)
sm4_key = binascii.unhexlify(poly_terms)
ciphertext=bytes.fromhex("bf0cb5cc6bea6146e9c1f109df953a57daa416d38a8ffba6438e7e599613e01f3b9a53dace4ccd55cd3e55ef88e0b835")
print(sm4_decrypt(sm4_key,ciphertext))

*choice

题目

python

from Crypto.Util.number import bytes_to_long
from random import Random
from secret import flag

assert flag.startswith(b'XYCTF{') and flag.endswith(b'}')
flag = flag[6:-1]

msg = bytes_to_long(flag)
rand = Random()
test = bytes([i for i in range(255, -1, -1)])
open('output.py', 'w').write(f'enc = {msg ^ rand.getrandbits(msg.bit_length())}\nr = {[rand.choice(test) for _ in range(2496)]}')

题目把 choice 改了，要不然做不了，改了之后 choice 就和 getrandbit 没区别了

不要问我为什么会 division 还没搞出来 choice

因为我忘了第一次有一个 getrandbits(175) 了（

mmd

exp

python

from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *
import random
from Crypto.Util.number import *
enc = 5042764371819053176884777909105310461303359296255297
r = [224, 55, 218, 253, 150, 84, 208, 134, 18, 177, 244, 54, 122, 193, 249, 5, 121, 80, 230, 21, 236, 33, 226, 3, 120, 141, 212, 33, 69, 195, 78, 112, 0, 62, 64, 197, 10, 224, 64, 191, 17, 112, 196, 143, 209, 92, 10, 198, 174, 181, 96, 118, 175, 145, 111, 41, 113, 206, 137, 37, 56, 227, 252, 84, 18, 145, 81, 124, 202, 14, 255, 144, 200, 13, 230, 218, 208, 210, 222, 101, 211, 114, 222, 12, 190, 226, 62, 118, 87, 152, 118, 245, 196, 4, 92, 251, 238, 142, 114, 13, 113, 247, 171, 8, 138, 20, 169, 192, 221, 223, 60, 56, 188, 70, 184, 202, 195, 246, 71, 235, 152, 255, 73, 128, 140, 159, 119, 79, 1, 223, 239, 242, 60, 228, 205, 90, 210, 5, 165, 35, 176, 75, 21, 182, 220, 212, 240, 212, 77, 124, 52, 140, 85, 200, 207, 31, 177, 82, 76, 152, 128, 124, 205, 216, 252, 34, 27, 198, 186, 61, 161, 192, 158, 226, 40, 127, 69, 162, 24, 46, 208, 183, 99, 165, 1, 221, 184, 40, 147, 136, 236, 245, 228, 197, 86, 15, 201, 95, 115, 18, 131, 79, 86, 12, 122, 63, 200, 192, 244, 205, 229, 36, 86, 217, 249, 170, 5, 134, 99, 33, 214, 10, 120, 105, 233, 115, 230, 114, 105, 84, 39, 167, 18, 10, 77, 236, 104, 225, 196, 181, 105, 180, 159, 24, 4, 147, 131, 143, 64, 201, 212, 175, 203, 200, 19, 99, 24, 112, 180, 75, 222, 204, 204, 13, 210, 165, 135, 175, 132, 205, 247, 28, 178, 76, 240, 196, 240, 121, 132, 21, 8, 45, 203, 143, 206, 6, 11, 51, 47, 87, 88, 35, 63, 168, 251, 11, 254, 11, 46, 72, 210, 230, 184, 114, 88, 194, 99, 229, 144, 1, 226, 44, 133, 10, 42, 234, 112, 100, 248, 247, 66, 221, 72, 229, 236, 4, 65, 203, 65, 61, 23, 181, 190, 87, 1, 76, 113, 48, 178, 42, 175, 49, 78, 159, 104, 229, 213, 223, 13, 249, 216, 60, 144, 203, 156, 23, 129, 148, 87, 37, 79, 227, 141, 202, 210, 245, 236, 121, 129, 78, 7, 121, 42, 82, 184, 222, 96, 100, 189, 62, 102, 176, 198, 1, 153, 242, 23, 191, 197, 176, 115, 206, 122, 50, 104, 70, 170, 29, 52, 189, 157, 99, 82, 187, 201, 78, 25, 75, 126, 118, 160, 250, 53, 112, 143, 161, 251, 221, 44, 255, 232, 115, 182, 77, 31, 217, 228, 97, 112, 236, 21, 160, 127, 9, 220, 22, 97, 159, 239, 25, 140, 206, 210, 148, 105, 184, 41, 56, 92, 141, 3, 200, 165, 14, 161, 219, 177, 40, 189, 75, 48, 146, 130, 151, 100, 144, 239, 22, 19, 246, 166, 231, 228, 68, 254, 16, 99, 95, 32, 177, 216, 170, 125, 211, 100, 142, 251, 16, 64, 83, 161, 184, 242, 248, 239, 141, 171, 135, 48, 20, 34, 250, 13, 70, 236, 172, 22, 241, 171, 25, 18, 204, 36, 248, 253, 203, 138, 10, 130, 249, 15, 157, 244, 154, 41, 4, 231, 64, 20, 212, 126, 160, 48, 154, 171, 250, 199, 113, 32, 186, 126, 217, 3, 236, 115, 37, 174, 75, 222, 125, 55, 86, 65, 96, 56, 254, 226, 213, 244, 36, 199, 164, 160, 126, 191, 29, 50, 135, 234, 165, 122, 132, 68, 133, 129, 0, 220, 72, 87, 172, 93, 15, 131, 37, 119, 240, 43, 239, 105, 45, 244, 6, 34, 111, 151, 144, 54, 46, 159, 6, 5, 160, 32, 4, 180, 246, 39, 220, 85, 209, 145, 41, 88, 137, 110, 101, 113, 115, 204, 11, 53, 152, 177, 240, 193, 220, 136, 84, 221, 12, 43, 74, 122, 251, 236, 53, 175, 36, 46, 246, 181, 137, 246, 53, 189, 171, 240, 104, 8, 126, 56, 122, 245, 155, 130, 31, 16, 20, 212, 147, 33, 165, 82, 117, 244, 167, 235, 115, 244, 94, 173, 195, 34, 36, 33, 218, 39, 13, 90, 196, 172, 207, 105, 73, 255, 187, 221, 162, 242, 186, 122, 140, 241, 120, 98, 44, 81, 172, 201, 150, 238, 111, 147, 24, 214, 192, 125, 102, 157, 53, 219, 172, 123, 218, 222, 71, 138, 117, 188, 32, 104, 10, 188, 118, 58, 254, 36, 104, 212, 76, 209, 15, 6, 33, 149, 15, 225, 76, 8, 157, 48, 70, 127, 19, 126, 77, 216, 133, 132, 30, 33, 113, 117, 134, 238, 57, 20, 121, 26, 184, 229, 202, 90, 28, 42, 230, 42, 159, 19, 191, 162, 205, 241, 67, 177, 216, 191, 164, 146, 90, 228, 232, 149, 163, 135, 130, 193, 196, 178, 215, 216, 155, 238, 20, 36, 196, 153, 207, 177, 149, 40, 172, 139, 12, 134, 142, 154, 225, 179, 95, 248, 190, 8, 154, 246, 229, 102, 121, 197, 116, 135, 163, 128, 109, 112, 114, 143, 164, 134, 233, 45, 244, 22, 141, 211, 214, 122, 14, 93, 49, 251, 85, 95, 95, 191, 210, 245, 181, 142, 125, 110, 33, 195, 150, 197, 173, 86, 50, 127, 187, 129, 67, 119, 58, 134, 119, 36, 151, 136, 122, 157, 22, 171, 195, 48, 178, 232, 228, 177, 6, 124, 50, 163, 161, 32, 49, 197, 157, 188, 86, 208, 226, 208, 63, 173, 21, 192, 148, 194, 208, 251, 95, 117, 34, 116, 217, 130, 150, 97, 206, 101, 201, 88, 137, 163, 90, 104, 129, 4, 191, 99, 50, 115, 8, 145, 116, 250, 180, 193, 229, 128, 92, 55, 26, 6, 154, 68, 0, 66, 77, 126, 192, 170, 218, 252, 127, 192, 29, 107, 152, 231, 190, 202, 130, 116, 229, 193, 63, 13, 48, 220, 238, 126, 74, 232, 19, 242, 71, 159, 9, 196, 187, 111, 243, 81, 244, 193, 95, 166, 85, 22, 240, 32, 1, 114, 11, 64, 114, 149, 217, 207, 194, 1, 33, 245, 14, 101, 119, 32, 233, 214, 139, 71, 103, 125, 54, 17, 86, 140, 132, 221, 45, 227, 136, 203, 156, 223, 73, 43, 82, 190, 119, 22, 14, 115, 0, 192, 105, 147, 210, 146, 47, 89, 210, 18, 225, 126, 210, 240, 55, 219, 247, 106, 190, 50, 35, 13, 255, 236, 253, 82, 244, 117, 139, 1, 72, 182, 19, 170, 173, 59, 175, 10, 95, 66, 253, 178, 139, 45, 5, 24, 59, 9, 222, 58, 46, 79, 48, 39, 175, 196, 249, 249, 70, 126, 118, 69, 165, 155, 119, 67, 221, 20, 133, 16, 99, 41, 132, 11, 12, 35, 70, 87, 43, 197, 103, 33, 201, 3, 195, 142, 128, 135, 121, 26, 185, 2, 73, 235, 70, 219, 49, 227, 133, 241, 34, 6, 9, 109, 66, 50, 177, 114, 119, 101, 91, 144, 41, 246, 40, 81, 113, 203, 226, 87, 8, 0, 73, 212, 5, 95, 112, 230, 4, 28, 206, 93, 252, 30, 195, 197, 226, 165, 120, 3, 124, 169, 66, 227, 113, 55, 101, 135, 141, 71, 84, 202, 19, 145, 25, 92, 50, 80, 53, 63, 85, 184, 196, 93, 254, 47, 252, 182, 150, 115, 20, 181, 178, 87, 162, 50, 190, 228, 125, 240, 134, 10, 142, 173, 206, 250, 49, 186, 201, 118, 146, 246, 244, 199, 9, 55, 253, 123, 103, 200, 206, 79, 168, 216, 99, 192, 191, 236, 214, 248, 111, 115, 74, 155, 165, 150, 40, 86, 224, 240, 133, 69, 34, 52, 13, 63, 61, 116, 182, 144, 177, 101, 164, 77, 217, 65, 218, 150, 142, 249, 165, 160, 220, 120, 25, 36, 157, 134, 223, 11, 46, 121, 75, 182, 126, 104, 91, 204, 45, 49, 175, 10, 48, 83, 150, 96, 244, 10, 149, 76, 124, 189, 149, 200, 252, 175, 124, 146, 126, 230, 70, 194, 243, 63, 204, 224, 115, 140, 115, 110, 86, 22, 193, 5, 11, 18, 177, 159, 94, 160, 38, 188, 139, 89, 1, 200, 163, 138, 8, 140, 169, 54, 29, 225, 22, 5, 99, 144, 247, 239, 106, 77, 29, 141, 206, 89, 236, 4, 32, 104, 115, 206, 204, 15, 100, 66, 199, 15, 89, 24, 246, 99, 224, 207, 7, 205, 142, 203, 28, 87, 16, 110, 93, 72, 73, 206, 48, 59, 170, 152, 224, 2, 74, 9, 125, 140, 82, 206, 159, 0, 117, 237, 252, 47, 200, 75, 133, 68, 239, 109, 169, 25, 168, 202, 240, 5, 67, 125, 173, 233, 6, 148, 38, 182, 13, 141, 149, 39, 119, 189, 122, 49, 173, 153, 78, 103, 211, 65, 224, 52, 10, 35, 233, 88, 66, 43, 120, 255, 71, 169, 215, 250, 218, 205, 163, 164, 226, 46, 178, 25, 88, 59, 98, 199, 167, 134, 244, 167, 210, 20, 246, 159, 163, 252, 114, 5, 168, 52, 47, 177, 159, 255, 236, 166, 49, 36, 61, 10, 130, 135, 220, 101, 202, 69, 150, 100, 217, 98, 203, 217, 166, 33, 169, 203, 230, 194, 224, 15, 249, 205, 52, 41, 124, 191, 223, 148, 251, 147, 133, 85, 149, 214, 198, 5, 134, 91, 201, 191, 204, 152, 240, 37, 34, 236, 211, 182, 142, 207, 1, 188, 67, 87, 222, 220, 7, 78, 49, 129, 236, 98, 120, 217, 204, 77, 106, 89, 250, 182, 15, 18, 27, 143, 13, 27, 61, 223, 213, 196, 190, 24, 35, 104, 100, 220, 60, 194, 174, 169, 20, 167, 75, 162, 26, 253, 213, 59, 219, 187, 253, 160, 249, 61, 122, 113, 223, 55, 57, 198, 53, 138, 94, 154, 18, 132, 233, 183, 71, 7, 22, 50, 196, 181, 202, 103, 86, 31, 119, 83, 130, 165, 242, 170, 31, 35, 175, 117, 95, 89, 247, 221, 186, 47, 236, 241, 77, 194, 111, 148, 45, 101, 88, 41, 0, 33, 139, 15, 127, 156, 72, 234, 217, 170, 218, 216, 31, 4, 73, 150, 78, 49, 178, 13, 178, 46, 102, 93, 184, 110, 205, 132, 190, 43, 87, 194, 35, 188, 166, 9, 97, 184, 202, 113, 45, 150, 62, 106, 108, 19, 162, 85, 212, 188, 131, 38, 67, 23, 136, 208, 87, 63, 69, 6, 209, 242, 45, 13, 228, 14, 233, 8, 71, 43, 51, 89, 46, 195, 101, 132, 254, 154, 183, 220, 115, 221, 255, 174, 150, 65, 141, 176, 57, 144, 16, 115, 252, 144, 139, 52, 205, 224, 75, 190, 192, 2, 231, 30, 238, 149, 22, 200, 137, 244, 239, 185, 212, 145, 230, 200, 8, 249, 109, 26, 226, 195, 133, 140, 103, 50, 230, 180, 47, 196, 226, 105, 13, 239, 135, 20, 214, 152, 211, 208, 81, 213, 48, 187, 232, 77, 139, 16, 79, 204, 216, 56, 41, 41, 58, 192, 245, 1, 104, 85, 42, 107, 94, 142, 12, 247, 90, 254, 116, 72, 193, 219, 54, 247, 5, 28, 60, 140, 10, 185, 86, 148, 101, 198, 96, 181, 245, 61, 25, 186, 29, 57, 176, 188, 9, 239, 93, 198, 110, 248, 23, 87, 193, 161, 107, 40, 38, 186, 205, 148, 197, 127, 144, 69, 19, 47, 132, 82, 23, 170, 83, 224, 235, 49, 190, 44, 145, 65, 66, 141, 78, 1, 254, 24, 157, 7, 23, 227, 28, 81, 176, 22, 92, 139, 188, 48, 183, 229, 139, 205, 174, 131, 189, 241, 21, 146, 204, 58, 249, 167, 217, 174, 43, 41, 56, 181, 212, 42, 188, 6, 117, 93, 178, 160, 129, 15, 76, 150, 207, 245, 227, 247, 130, 171, 114, 204, 101, 176, 55, 43, 138, 149, 90, 124, 45, 96, 181, 221, 16, 121, 210, 51, 210, 164, 68, 64, 154, 167, 91, 69, 35, 153, 212, 10, 125, 235, 203, 166, 145, 9, 174, 86, 65, 70, 112, 194, 140, 92, 170, 49, 191, 157, 218, 199, 152, 151, 247, 208, 182, 209, 34, 245, 5, 173, 105, 175, 159, 71, 251, 198, 246, 214, 99, 58, 70, 154, 52, 39, 88, 149, 179, 202, 86, 240, 108, 200, 83, 250, 62, 213, 113, 138, 73, 106, 141, 192, 204, 90, 251, 208, 28, 124, 30, 134, 119, 144, 68, 23, 204, 181, 186, 76, 156, 71, 8, 104, 186, 87, 221, 134, 122, 72, 244, 203, 121, 181, 65, 90, 185, 131, 230, 133, 54, 158, 186, 168, 201, 178, 155, 172, 164, 22, 130, 111, 90, 209, 2, 167, 23, 176, 63, 139, 89, 63, 15, 238, 110, 204, 85, 36, 127, 68, 240, 177, 31, 2, 81, 147, 205, 192, 214, 173, 103, 130, 10, 100, 232, 125, 216, 163, 209, 171, 168, 243, 145, 6, 170, 41, 142, 250, 145, 57, 139, 224, 221, 189, 48, 141, 232, 146, 92, 216, 154, 126, 223, 8, 90, 82, 138, 221, 240, 223, 87, 209, 165, 17, 52, 154, 91, 12, 121, 212, 238, 46, 215, 217, 147, 136, 139, 251, 91, 39, 188, 244, 251, 52, 110, 22, 126, 200, 231, 153, 103, 203, 120, 219, 118, 172, 53, 141, 203, 75, 163, 150, 194, 27, 208, 9, 186, 6, 85, 46, 243, 135, 66, 40, 79, 206, 250, 20, 85, 123, 35, 164, 44, 85, 104, 66, 51, 177, 125, 189, 165, 226, 13, 75, 78, 225, 252, 226, 138, 81, 171, 172, 175, 122, 145, 68, 254, 37, 153, 39, 113, 237, 232, 220, 80, 193, 181, 21, 197, 186, 56, 202, 239, 213, 135, 41, 6, 85, 54, 135, 214, 95, 102, 23, 192, 153, 235, 110, 26, 14, 84, 220, 142, 236, 192, 8, 117, 205, 249, 92, 148, 149, 77, 235, 205, 232, 21, 48, 14, 84, 187, 124, 218, 166, 155, 183, 62, 10, 123, 53, 63, 79, 101, 193, 3, 61, 29, 39, 99, 22, 197, 75, 10, 165, 44, 215, 210, 181, 74, 235, 200, 247, 158, 187, 200, 102, 22, 150, 73, 42, 131, 28, 17, 180, 133, 205, 23, 228, 226, 219, 175, 207, 81, 53, 141, 114, 140, 59, 218, 169, 7, 219, 139, 75, 210, 97, 236, 157, 21, 109, 195, 128, 54, 5, 55, 217, 127, 49, 62, 59, 101, 95, 86, 255, 22, 186, 94, 151, 114, 93, 19, 198, 159, 174, 142, 132, 195, 157, 206, 161, 107, 255, 106, 196, 250, 191, 86, 221, 196, 36, 29, 37, 50, 224, 42, 20, 89, 212, 252, 191, 157, 237, 10, 157, 80, 42, 234, 180, 1, 183, 186, 239, 129, 14, 125, 114, 66, 203, 120, 114, 37, 214, 37, 73, 153, 182, 165, 87, 177, 75, 220, 210, 105, 154, 149, 114, 13, 202, 128, 55, 128, 96, 158, 150, 57, 86, 106, 127, 160, 57, 80, 255, 107, 241, 95, 121, 14, 110, 160, 119, 211, 150, 156, 185, 158, 221, 110, 76, 255, 119, 15, 245, 1, 238, 139, 100, 250, 220, 147, 193, 51, 144, 123, 139, 13, 26, 158, 95, 148, 251, 82, 227, 119, 92, 132, 219, 248, 239, 217, 101, 88, 121, 10, 148, 203, 156, 156]
def mt19937(bs, out):

    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    rng.getrandbits(175)
    zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
    print("solving...")
    
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    print("solved")
    print(long_to_bytes(pyrand.getrandbits(175)^enc))
test = bytes([i for i in range(255, -1, -1)])

ans=[]
for i in trange(len(r)):
    ans.append(255-r[i])
out=[]
assert len(ans)==624*4
print(type(ans[0]))  
for i in range(624*4):
    out.append(random.getrandbits(8))
print(type(out[0]))
mt19937(8,ans)

*复复复复数

题目

python

class ComComplex:
    def __init__(self, value=[0,0,0,0]):
        self.value = value
    def __str__(self):
        s = str(self.value[0])
        for k,i in enumerate(self.value[1:]):
            if i >= 0:
                s += '+'
            s += str(i) +'ijk'[k]
        return s
    def __add__(self,x):
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
    def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
        return ComComplex([a,b,c,d])
    def __mod__(self,x):
        return ComComplex([i % x for i in self.value])
    def __pow__(self, x, n=None):
        tmp = ComComplex(self.value)
        a = ComComplex([1,0,0,0])
        while x:
            if x & 1:
                a *= tmp
            tmp *= tmp
            if n:
                a %= n
                tmp %= n
            x >>= 1
        return a

from Crypto.Util.number import *
from secret import flag, hint

p = getPrime(256)
q = getPrime(256)
r = getPrime(256)
n = p * q * r

P = getPrime(512)
assert len(hint) == 20
hints = ComComplex([bytes_to_long(hint[i:i+5]) for i in range(0,20,5)])
keys = ComComplex([0, p, q, r])
print('hint =',hints)
print('gift =',hints*keys%P)
print('P =',P)

e = 65547
m = ComComplex([bytes_to_long(flag[i:i+len(flag)//4+1]) for i in range(0,len(flag),len(flag)//4+1)])
c = pow(m, e, n)
print('n =', n)
print('c =', c)

'''
hint = 375413371936+452903063925i+418564633198j+452841062207k
gift = 8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729+20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171i+22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868j+40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863k
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = 212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103+24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825i+45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125j+96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385k
'''

首先根据 hints 和 gifts 通过解线性同余方程组可以将 $p, q, r$ 解出来

然后根据 $ϕ (p)$ 是指比 $p$ 小且与 $p$ 互素的个数，因此 $ϕ (p) = p^{4} - 1$ ,就是去掉了 0

所以 $\phi(n)=(p^4-1)(q^4-1)(r^4-1)$

但是 $e$ 和 $ϕ$ 不互素

这里唐的一点是如果不把 $p$ 转成 $i n t$ 类型去算 $ϕ (p)$ 的话会发现是错的，我当时就是计算

d_{p} \equiv e^{- 1} \mod ϕ (p)

m_{1} = c^{d_{p}} \mod p

想得到正确结果，结果半天发现不了哪里错了😂

最后复现发现了这个问题，然后在 $G F (p)$ 开两次三次根即可

exp

python

from sage.all import *
from Crypto.Util.number import *
import math
class ComComplex:
    def __init__(self, value=[0,0,0,0]):
        self.value = value
    def __str__(self):
        s = str(self.value[0])
        for k,i in enumerate(self.value[1:]):
            if i >= 0:
                s += '+'
            s += str(i) +'ijk'[k]
        return s
    def __add__(self,x):
        return ComComplex([i+j for i,j in zip(self.value,x.value)])
    def __mul__(self,x):
        a = self.value[0]*x.value[0]-self.value[1]*x.value[1]-self.value[2]*x.value[2]-self.value[3]*x.value[3]
        b = self.value[0]*x.value[1]+self.value[1]*x.value[0]+self.value[2]*x.value[3]-self.value[3]*x.value[2]
        c = self.value[0]*x.value[2]-self.value[1]*x.value[3]+self.value[2]*x.value[0]+self.value[3]*x.value[1]
        d = self.value[0]*x.value[3]+self.value[1]*x.value[2]-self.value[2]*x.value[1]+self.value[3]*x.value[0]
        return ComComplex([a,b,c,d])
    def __mod__(self,x):
        return ComComplex([i % x for i in self.value])
    def __pow__(self, x, n=None):
        tmp = ComComplex(self.value)
        a = ComComplex([1,0,0,0])
        while x:
            if x & 1:
                a *= tmp
            tmp *= tmp
            if n:
                a %= n
                tmp %= n
            x >>= 1
        return a
def get_root3(p, Q):
    F = GF(p)  # 定义有限域GF(p)
    Q = (F(Q[0]), F(Q[1]), F(Q[2]), F(Q[3]))  # 将四元数转换为GF(p)中的元素

    def quaternion_mult(q1, q2):
        a1, b1, c1, d1 = q1
        a2, b2, c2, d2 = q2
        scalar = a1*a2 - b1*b2 - c1*c2 - d1*d2
        i = a1*b2 + b1*a2 + c1*d2 - d1*c2
        j = a1*c2 - b1*d2 + c1*a2 + d1*b2
        k = a1*d2 + b1*c2 - c1*b2 + d1*a2
        return (scalar, i, j, k)

    def quaternion_pow(q, n):
        result = (F(1), F(0), F(0), F(0))
        while n > 0:
            if n % 2 == 1:
                result = quaternion_mult(result, q)
            q = quaternion_mult(q, q)
            n = n // 2
        return result

    # 提取目标四元数的标量部分和向量部分
    W, X, Y, Z = Q
    S = W
    V = (X, Y, Z)
    N_V = (X**2 + Y**2 + Z**2)  # 向量部分的范数
    N_Q = (W**2 + N_V)        # 目标四元数的总范数

    solutions = []

    # Step 1: 检查 N_Q 是否为三次剩余
    try:
        cube_roots_NQ = N_Q.nth_root(3, all=True)
    except ValueError:
        cube_roots_NQ = []

    for n in cube_roots_NQ:
        # Step 2: 解三次方程 4*N_V*k**3 -3*n*k +1 = 0
        if N_V == 0:
            # 处理纯标量情况
            if X == 0 and Y == 0 and Z == 0:
                try:
                    s_roots = S.nth_root(3, all=True)
                    solutions.extend( (s, F(0), F(0), F(0)) for s in s_roots )
                except:
                    pass
            continue
        
        # R.<k> = PolynomialRing(F)
        R = PolynomialRing(F, 'k')
        k = R.gen()
        eq = 4*N_V * k**3 - 3*n * k + 1
        k_candidates = eq.roots(multiplicities=False)
        
        for k in k_candidates:
            # Step 3: 计算 s² = n - k²*N_V
            s_sq = n - k**2 * N_V
            if s_sq == 0:
                s_candidates = [F(0)]
            else:
                if not s_sq.is_square():
                    continue
                s_candidates = s_sq.sqrt(all=True)
            
            for s in s_candidates:
                # Step 4: 验证标量方程 s*(n -4k²*N_V) ≡ S mod p
                lhs = s * (n - 4*k**2*N_V)
                if lhs == S:
                    q = (s, k*X, k*Y, k*Z)
                    # 验证 q**3 是否等于 Q（避免计算误差）
                    if quaternion_pow(q, 3) == Q:
                        solutions.append(q)

    # 去重并输出
    solutions = list(set(solutions))
    # print(f"解为：{solutions}")
    return solutions

hint = [375413371936,452903063925,418564633198,452841062207]
gift = [8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729,20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171,22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868,40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863]
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = ComComplex([212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103,24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825,45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125,96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385])
A=Matrix(Zmod(P),[[hint[0],-hint[1],-hint[2],-hint[3]],[hint[1],hint[0],-hint[3],hint[2]],[hint[2],hint[3],hint[0],-hint[1]],[hint[3],-hint[2],hint[1],hint[0]]])
b=vector(Zmod(P),[gift[0],gift[1],gift[2],gift[3]])
solution = A.solve_right(b)
_,p,q,r=solution

assert p*q*r==n


p=int(p)
q=int(q)
r=int(r)    

phi=(p**4-1)*(q**4-1)*(r**4-1)
#print(int(p))
#p=63173373914948586508761871207488662566773264479285518327131522282352053209317
print(isPrime(int(p)))
e=int(65547)
print(math.gcd(e,p**4-1))   
dp = int(pow(int(e//9), -1, int(p**4-1)))

mp=pow(c,dp,int(p))
print(mp)

m3 = get_root3(p, [mp.value[0], mp.value[1], mp.value[2], mp.value[3]])
print(m3)
for mm3 in m3:
    m=get_root3(p,mm3)
    for i in m:
        flag=b''.join(long_to_bytes(int(j))for j in i)
        print(flag)

*prng_xxxx

题目

python

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from secret import flag, b, seed

class LCG:
    def __init__(self, seed, a, b):
        self.seed = seed
        self.a = a
        self.b = b
        self.m = 2**128

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

class lfsr:
    # 我被裁了/(ㄒoㄒ)/~~
    pass

a = 47026247687942121848144207491837523525
assert b < 2**128 and seed < 2**128
lcg = LCG(seed, a, b)
print([lcg.next() for _ in [0] * 64])
print(AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(flag, 16)))
# [17861431650111939539, 15632044669542972472, 18085804805519111109, 11630394250634164303, 10914687109985225138, 7348450425255618214, 10796029302647050328, 14267824433700366397, 9363967587530173835, 8995382728269798714, 3504283765121786984, 1312349325731613524, 10716889342831891752, 12298317818779713512, 8701992888199838445, 7261196699430834071, 4670657923849978944, 9833942603152121381, 18304734854303383637, 15945503654626665549, 6509330987395005461, 223169047706410182, 12990946817252956584, 3884858487227858459, 6366350447244638553, 10326924732676590049, 12989931141522347344, 9197940263960765675, 2481604167192102429, 1409946688030505107, 9263229900540161832, 266892958530212020, 14298569012977896930, 17318088100106133211, 4224045753426648494, 650161332435727275, 9488449142549049042, 8916910451165068139, 10116136382602356010, 6604992256480748513, 7375827593997920567, 1661095751967623288, 4143230452547340203, 4145435984742575053, 10465207027576409947, 16146447204594626029, 2807803679403346199, 10857432394281592897, 1494771564147200381, 2085795265418108023, 11756240132299985418, 13802520243518071455, 1191829597542202169, 16603089856395516862, 12517247819572559598, 14148806699104849454, 8174845389550768121, 15565523852832475714, 10046639095828632930, 15353735627107824646, 7003433641698461961, 11217699328913391211, 6392630836483027655, 7918524192972397836]
# b'l\x8bd,\xa3\xe7\x87*\xca\n\xd7\x11\xd6n=\xeaS`\xa4w\x94(\xb9\xf9\xb9\xc6\xe3\xc2\xfb\xdb\x80\xf6\x9f\xc7\xd1F"`{;V\xa7}Z\xc0\xc0\xf6<'

思路

这题似乎是个 paper ,我是跟着一个 Q&A 的思路复现的

整体思路如下

问题引入

由递推式 $X_{i + 1} = a * X_{i} + b (\mod 2^{128})$

可以写出通项公式

X_{i} = a^{i} * X_{0} + b * \sum_{k = 0}^{i - 1} a^{k} (\mod 2^{128})

然后随机化的结果是将 128 位 state 的高 64 位和低 64 位进行异或得到 64 位的随机输出

求解：

找到 $ω$

首先可以找到 m 数据量的一个向量 $ω$ ,满足 $| ω | < W$

\sum_{i = 1}^{m} ω_{i} a^{i} \equiv 0 (\mod 2^{\frac{n}{2} + k})

其中 $W$ 是一个界，为后面的判断提供帮助的，所以在能找到 $ω$ 的情况下， $W$ 越小越好

我们可以构造一个这样的格并使用 BKZ 去求解 $ω$

[\begin{matrix} 1 & 0 & 0 & \dots & 0 & K * a \\ 0 & 1 & 0 & \dots & 0 & K * a^{2} \\ 0 & 0 & 1 & \dots & 0 & K * a^{3} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & 1 & K * a^{m} \\ 0 & 0 & 0 & \dots & 0 & K * 2^{\frac{n}{2} + k} \end{matrix}]

格是 $m + 1$ 维的， $K$ 是一个足够大的数，也就是配平因子， $k$ 是后面要猜测的 bit 数

$ω$ 存在的大概的界是 $m \log_{2} (W) \approx \frac{n}{2} + k$

猜测 $k$ 位

得到 $ω$ 后可以猜测 $X_{0}$ 的低位，因为 $b$ 也未知，所以要同时猜测 $b$ 的低位

猜测的 $k b i t$ 的选取也有讲究,将在后面进行讲解

我们现在可以假设同时已知 $X_{0}$ 和 $b$ 的低 $k$ 位

∵ X_{i + 1} = a * X_{i} + b (\mod 2^{128})

∴ X_{i + 1_{h}} * 2^{64} + X_{i + 1_{l}} = a * (X_{i_{h}} * 2^{64} + X_{i_{l}}) + b (\mod 2^{128})

∴ X_{i + 1_{l}} = a * X_{i_{l}} + b_{l} (\mod 2^{64})

所以 $X$ 的低位也满足递增关系，于是我们可以得到所有 $X_{i}$ 的低 $k$ 位

根据输出的随机数进行按位异或就可以得到对应的高位

然后乘 $2^{\frac{n}{2}}$ 得到 $X_{i}^{*}$

判断条件

经过数学推导可以得到一个式子（可以自己推一下）

\sum_{i = 1}^{m} ω_{i} [X_{i + 1} - X_{i}] \equiv 0 (\mod 2^{\frac{n}{2} + k})

我们得到 $X_{i}^{*}$ 后可以计算

Z = \sum_{i = 1}^{m} ω_{i} [X_{i + 1}^{*} - X_{i}^{*}] \equiv 0 (\mod 2^{\frac{n}{2} + k})

选取 $Δ = min (Z, | 2^{\frac{n}{2} + k} - Z |)$

$Δ$ 越小，说明 $X_{i}^{*}$ 与 $X_{i}$ 越相近，猜测的结果越好

这里有一个范围

如果 $Δ \geq 2 m W * 2^{\frac{n}{2}}$ 则猜测是完全不可能正确的

否则，我们会有 $1 - 2 m W * 2^{- k}$ 的概率猜对

根据上述范围，进行初次猜测，假如我选的 $m$ 为 32 ,初次 $W = 2$ ，则猜对的概率是 $1 - \frac{128}{2^{k}}$ ，因此选取 $k = 8$ 或 $9$ 比较合适，我这里选的 $9$ ,概率大一点

不断重复以及优化技巧

后面有点类似于剪枝，就是猜测出 $k$ 位后，用 $k$ 位的可能结果一直往后猜，直至猜出所有的 bit

这里我遇到了一个问题，就是可能的结果太多

未央让我仔细看了看原文，说有一个滑动窗口的操作，意思是多用几组 $Y_{i}$ 进行条件判断( $Y_{i}$ 就是随机数输出 )

加上几轮滑动窗口进行调试后，可能的结果就大大减少了（几乎每一轮都是 16 个)

最后不断重复就 OK 了

整个流程 1h 左右吧

(每一轮调出来的参数都放在 exp 里了)

exp

python

from sage.all import *
from tqdm import *
import multiprocessing
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import *
ou=[17861431650111939539, 15632044669542972472, 18085804805519111109, 11630394250634164303, 10914687109985225138, 7348450425255618214, 10796029302647050328, 14267824433700366397, 9363967587530173835, 8995382728269798714, 3504283765121786984, 1312349325731613524, 10716889342831891752, 12298317818779713512, 8701992888199838445, 7261196699430834071, 4670657923849978944, 9833942603152121381, 18304734854303383637, 15945503654626665549, 6509330987395005461, 223169047706410182, 12990946817252956584, 3884858487227858459, 6366350447244638553, 10326924732676590049, 12989931141522347344, 9197940263960765675, 2481604167192102429, 1409946688030505107, 9263229900540161832, 266892958530212020, 14298569012977896930, 17318088100106133211, 4224045753426648494, 650161332435727275, 9488449142549049042, 8916910451165068139, 10116136382602356010, 6604992256480748513, 7375827593997920567, 1661095751967623288, 4143230452547340203, 4145435984742575053, 10465207027576409947, 16146447204594626029, 2807803679403346199, 10857432394281592897, 1494771564147200381, 2085795265418108023, 11756240132299985418, 13802520243518071455, 1191829597542202169, 16603089856395516862, 12517247819572559598, 14148806699104849454, 8174845389550768121, 15565523852832475714, 10046639095828632930, 15353735627107824646, 7003433641698461961, 11217699328913391211, 6392630836483027655, 7918524192972397836]
enc=b'l\x8bd,\xa3\xe7\x87*\xca\n\xd7\x11\xd6n=\xeaS`\xa4w\x94(\xb9\xf9\xb9\xc6\xe3\xc2\xfb\xdb\x80\xf6\x9f\xc7\xd1F"`{;V\xa7}Z\xc0\xc0\xf6<'
a = 47026247687942121848144207491837523525
print(len(ou))

k=18
m=32
n=128

K=2**20
def get_w(k,m,WW):
    mod=2**(64+k)
    M=Matrix(ZZ,m+1,m+1)
    for i in range(m):
        M[i,i]=1
    for i in range(m):
        M[i,-1]=K*a**(i+1) 
    M[-1,-1]=K*mod
    W=M.BKZ()

    for w in W:
        w = w[:-1]
        lhs = sum([w[i]*a**(i+1) for i in range(m)]) % 2**(n//2+k)
        if max(list(map(abs, w))) == WW and lhs == 0:
            print("w found")
            return w
    return None    

#多线程尝试，但不会写公用的存东西的
'''
def print_progress_bar(iteration, total, prefix='', length=40, fill='█'):
    percent = ("{0:.1f}").format(100 * (iteration / float(total)))
    filled_length = int(length * iteration // total)
    bar = fill * filled_length + '-' * (length - filled_length)
    sys.stdout.write(f'\r{prefix} |{bar}| {percent}% Complete')
    sys.stdout.flush()
def task(x):
    print_progress_bar(x + 1, 512, prefix='Progress', length=40)
    for b in range(2**k):
        ans=0
        out_h=[]
        for i in range(64):
            temp=x
            x=((a*x+b)%(2**k))^(ou[i]%(2**k))
            out_h.append(x*2**64+temp)
        cnt=0
        for t in range(10):
            for i in range(63):
                ans+=w[i]*(out_h[i+1]-out_h[i])*a**t
                ans=ans%mod
            delta=min(ans,mod-ans)
            if delta>=2*m*W*2**(n//2):
                pass
            else:
                cnt+=1
        if cnt==10:
            o.append((x,b))  
            
    
        
pool = multiprocessing.Pool(processes=16)  # 设置最多4个进程并行
    
    # 使用map方法并行化循环任务
pool.map(task, range(2**k))

    # 关闭进程池，等待所有进程完成
pool.close()
pool.join()

print("All tasks are finished.")  
print(o)       
'''   
#第一次尝试
''' 
now=None


for windows in trange(16):
    o=[]

    for x in range(2**k):
        for b in range(2**k):
            ans=0
            out_h1=[x]
            for i in range(64):
                out_h1.append(((a*out_h1[-1]+b)%(2**k)))
            out_h2 = [((ou[i] ^ out_h1[i]) % 2**k)*2**(n//2) for i in range(64)]    
            ans=sum(w[i-windows]*(out_h2[i+1]-out_h2[i])for i in range(windows,windows+m)) %mod
            delta=min(ans,abs(mod-ans))
            if int(delta)<2*m*WW*2**64:
                o.append((x,b))
    if now is None:
        now=set(o)
    else :
        now=now&set(o)
    print(len(now))

print(now)   
'''        


def guess(tt,out,w,WW,step,win):
    
    mod=2**(n//2+tt)
    all_now=[]
    for j in out:
        now1=None
        for windows in trange(win):
            oo=[]
            for t in range(2**step):
                for s in range(2**step):
                    x=j[0]+t*2**(tt-step)
                    b=j[1]+s*2**(tt-step)
                    ans=0
                    out_h11=[x]
                    for i in range(64):
                        out_h11.append(((a*out_h11[-1]+b)%(2**tt)))                  
                    out_h2 = [((ou[i] ^ out_h11[i]) % 2**tt)*2**(n//2) for i in range(64)]    
                    ans=sum(w[i-windows]*(out_h2[i+1]-out_h2[i])for i in range(windows,windows+m)) %mod
                    delta=min(ans,abs(mod-ans))
                    if int(delta)<2*m*WW*2**64:
                        oo.append((out_h11[0],b))
            if now1 is None:
                now1=set(oo)
            else :
                now1=now1&set(oo)
            print(len(now1))
            try:      
                if(len(now1)==0):
                    break
            except:
                pass          
        print(now1)
        all_now.append(now1)        
    return all_now 


now1=[(309, 69), (53, 69), (458, 255), (201, 67), (310, 1), (54, 257), (202, 255), (310, 257), (309, 325), (53, 325), (457, 67), (458, 511), (201, 323), (202, 511), (457, 323), (54, 1)]
now2={(216885, 89669), (85813, 220741), (216885, 220741), (85813, 89669),(176329, 167491), (45257, 36419), (176329, 36419), (45257, 167491),(216886, 157697), (216886, 26625), (85814, 26625), (85814, 157697),(176330, 235519), (45258, 235519), (45258, 104447), (176330, 104447)}
now2=list(now2)
now3={(96423734, 55470081), (96423734, 122578945), (29314870, 55470081), (29314870, 122578945),(37793994, 78747647), (37793994, 11638783), (104902858, 11638783), (104902858, 78747647),(29314869, 119234117), (96423733, 52125253), (96423733, 119234117), (29314869, 52125253),(104902857, 75402819), (37793993, 8293955), (37793993, 75402819), (104902857, 8293955)}
now3=list(now3)
now4={(67876376373, 12265938501), (33516638005, 12265938501), (67876376373, 46625676869), (33516638005, 46625676869),(35202838729, 61815557699), (843100361, 61815557699), (35202838729, 27455819331), (843100361, 27455819331),(67876376374, 26764797953), (33516638006, 26764797953), (67876376374, 61124536321), (33516638006, 61124536321),(843100362, 41954678783), (35202838730, 7594940415), (843100362, 7594940415), (35202838730, 41954678783)}
now4=list(now4)
now5={(11236477546697, 20952536485443), (11236477546697, 3360350441027), (28828663591113, 3360350441027), (27729151963337, 6384007417411), (27729151963337, 23976193461827), (10136965918921, 6384007417411), (10136965918921, 23976193461827), (28828663591113, 20952536485443),(25047406169910, 10540844738561), (25047406169910, 28133030782977), (6355708497718, 31156687759361), (7455220125494, 10540844738561), (7455220125494, 28133030782977), (23947894542134, 13564501714945), (23947894542134, 31156687759361), (6355708497718, 13564501714945)}
now5=list(now5)
now6={(17128433498763465, 6811536349630019), (17128433498763465, 15818735604371011), (8121234244022473, 6811536349630019), (8121234244022473, 15818735604371011),(9893164265459510, 3848661059397633), (885965010718518, 3848661059397633), (9893164265459510, 12855860314138625), (885965010718518, 12855860314138625)}
now6=list(now6)
now7={(3674051330923606217, 1123704243937513027), (5979894340137300169, 1123704243937513027), (8285737349350994121, 1123704243937513027), (3674051330923606217, 5735390262364900931), (1368208321709912265, 1123704243937513027), (5979894340137300169, 5735390262364900931), (8285737349350994121, 5735390262364900931), (1368208321709912265, 5735390262364900931),(3243477696717475638, 8353522370204297217), (5549320705931169590, 3741836351776909313), (7855163715144863542, 3741836351776909313), (937634687503781686, 3741836351776909313), (5549320705931169590, 8353522370204297217), (3243477696717475638, 3741836351776909313), (7855163715144863542, 8353522370204297217), (937634687503781686, 8353522370204297217)}
now7=list(now7)
print(len(now7))
#w=get_w(9,m,2)
#now1=guess(9,[(0,0)],w,2,9,16)
#w=get_w(18,m,3)
#now2=guess(18,noww,w,3,9,4)
#w=get_w(27,m,5)
#now3=guess(27,now2,w,5,9,3)
#w=get_w(36,m,5)
#now4=guess(36,now3,w,5,9,3)
#w=get_w(45,m,6)
#now5=guess(45,now4,w,6,9,3)
#w=get_w(54,m,7)
#now6=guess(54,now5,w,7,9,3)
#w=get_w(63,m,8)
#now7=guess(63,now6,w,8,9,3)
#w=get_w(64,m,10)
#now8=guess(64,now7,w,10,1,3)
now8={(12897423367778382025, 1123704243937513027), (3674051330923606217, 10347076280792288835), (3674051330923606217, 1123704243937513027), (12897423367778382025, 10347076280792288835),(5549320705931169590, 12965208388631685121), (5549320705931169590, 3741836351776909313), (14772692742785945398, 12965208388631685121), (14772692742785945398, 3741836351776909313)}
for x ,b in now8:
    t1=(a*x+b)%(2**64)
    x1=x+(x^ou[0])*(2**64)
    x2=t1+(t1^ou[1])*(2**64)
    bb=(x2-x1*a)%(2**128)
    if bb%(2**64)==b:
        d=inverse(a,2**128)
        seed=d*(x1-bb)%(2**128)
        key=md5(str(seed).encode()).digest()
        print(AES.new(key=key,mode=AES.MODE_ECB).decrypt(enc))

结语

还是太菜了😂，继续学习吧

XYCTF 2025 Crypto

division

题目

exp

complex_signin

题目

exp

reed

题目

非预期 exp

预期 exp

勒索病毒

题目

exp

*choice

题目

exp

*复复复复数

题目

exp

*prng_xxxx

题目

思路

问题引入

找到 ω

猜测 k 位

判断条件

不断重复以及优化技巧

exp

结语

微信扫一扫：分享

找到 $ω$

猜测 $k$ 位