第十八届全国大学生信息安全竞赛暨第二届“长城杯”铁人三项赛初赛 Crypto WriteUp

References:

rasnd

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import os

FLAG = os.getenv("FLAG").encode()
flag1 = FLAG[:15]
flag2 = FLAG[15:]

def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print(n)
    print(c)
    print(hint1)
    print(hint2)


def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print(n)
    print(c)
    print(hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")

首先解crypto1

hint1=x1∗p+y1∗q−0x11hint1=x1*p+y1*q-0x11

hint2=x2∗p+y2∗q−0x514hint2=x2*p+y2*q-0x514

hint1+0x114≡x1∗pmod  qhint1+0x114\equiv x1*p \mod q

hint2+0x514≡x2∗pmod  qhint2+0x514\equiv x2*p \mod q

令H1=hint1+0x1144,H2=hint2+0x514H1=hint1+0x1144,H2=hint2+0x514

x2H1≡x1H2mod  qx2H1\equiv x1H2 \mod q

由于x1x1和x2x2很小，直接爆破

再解crypto2，开始在hint = pow(514*p - 114*q, n - p - q, n)卡住了，后面想到

hint=(514∗p−114∗q)n−p−qmod  nhint = (514*p - 114*q)^{n - p - q} \mod n

其中n−p−q=φ(n)−1n-p-q=\varphi(n)-1

xn−p−q≡xφ(n)−1≡x−1≡hintmod  nx^{n-p-q}\equiv x^{\varphi(n)-1}\equiv x^{-1}\equiv hint \mod n

通过计算模逆元B并构建方程组求解

n=p∗q514p−114q=hint−1mod  nn=p*q\\514p-114q=hint^{-1}\mod n

from math import isqrt,gcd
from gmpy2 import invert

n1 = 24539946854122990446981875831056228150220008041208993612488752858394072486012112612210683586208430589598625359746822760104544528664142117485453453266763750534133016709899922464125403453541176995893521183168813887960386721698732938992384696582185635420231303837698968961289861842138999279960554574525409604917165120620206953702766106613841400260893600717789467521112604985075364855823317449561162565653063704757008367074533819124680959368835282226257956495259158885152205043237129155635030983657194245460992843575755346865947732570365620394550573393915503734603739695227789754514753202543450284745010160795490285272777
c1 = 21048433549113075754870972297696499634421351160621430463983805879915182430653035264222286060371807909650479930547893165879008262892924350202171626441920402233720852951211412573591903231501356204827154975652080227996888464750220241209857969564421573183951272018577753592011880582679319519474478996643265180609491983532874172074760729546132317938497809920768271820532214596590340922886718418624979348727457606129953854252795292142980026487353110746160083460625260172652524042651664672402194075041748358642185004835584990018818705471307651851419756864970170561486806789385532018812979860426152286402168931652643675307996
hint1 = 1652119644161067281546868856405780644146374543314471967439412848712336478894450321286558346776432435821911816290163545705601758822325032706738297851932769205631370467641393272550511934157031704640210029469976509510421263923683425701310071412260076622478674351204205688104802422292505995617924710199912410648555002365618065695566741047787280849
hint2 = 3045799978047656967548349664060033742958064196035914296332173078014730534928446553167276968097164155768305305781714547733842335304206630802464882966562605391984831268016807840861319354996173778130214963664090158056160729354686805577614412331064285108317599714122827241813361627415315462916042370519410820492772430826773490648902271649820694672655938704060831877298671006895487058645975608626611971139442995034272772943364957473474775738982071726444931353711926872

n2 = 17127697909223316782894824520231296428881866946343647536895967484403436526047427051724396404849584615272545140597294017803492209557830331596471615619036937222950609991138124095210144319395883117157711702068912918019781337598937658089336789868728274967712908384868824017083637909180800632553234893415787363308932798886213237407964348227793763793511717378574216166360078976953920381492848524352062176336906628126801211257791682508380631025502399935117693753475891295958038484732255829618172076571753454960659357189890702753135839961007507073184172644550551726036021840035915945368623439760827404619003986798373059423051
c2 = 13363630853776126042344393499220686461253336951637286738591296683696691465325100680696933787316262246835956276404087799459704761701714440362409429868329114011758554504872807446408396599838732780221805690847769666137476119959355851568539109255966707910893376685689464941543635529516961346911431619034475099036056095960572059165240279406222437546855266580429643372512590098642833468101596991104462328303082199894570168740254570952834904813794055605118371032367239611483877299515489012695927859311214414757009192795034586377994442797603628491618597908709464844831889371430543512024792545190135864308432839958799401282366
hint = 4101011063508949839817823833947819235243587691527797378271907273398974481201255035301204911896588697871274874028179532680609556153856538932390053254578894067610054585870866078723500039484752957455899716431798233140939241216385850765665191997827282278656578974979079361281857791631181595531970870729515467767591388551133763611875900253588128511766805789105524403324614777218668342370134482827700794207017239301056077781932423255710110396542381858535109287809030352308561044405757534644147780991239977921301228508548857954363998594621860335598935568408141080770093415092184199567997988977656823923638362645661161700922

e = 0x10001

def long_to_bytes(n):
    return n.to_bytes((n.bit_length() + 7) // 8, byteorder='big')
    
def solve_1(n1, c1, hint1, hint2):
    hint1 += 0x114
    hint2 += 0x514
    for x1 in range(1,2**11):
        for x2 in range(1,2**11):
            f = x2*hint1-x1*hint2
            if gcd(f,n1)!=1:
                p1 = gcd(f,n1)
                q1 = n1//p1
                break
    return p1,q1

def solve_2(n, c, hint):
    A,B,C = (114, invert(hint, n), -514 * n)
    D = isqrt(B**2-4*A*C)
    L = [(-B + D) // (2 * A), (-B - D) // (2 * A)]
    for q in L:
        if n%q == 0:
            p = n // q
            return p, q

def decrypt(n,e,c,p,q):
    phi = (p - 1) * (q - 1)
    d = invert(e, phi)
    m = pow(c, d, n)
    return long_to_bytes(m)
    
p1, q1 = solve_1(n1,c1,hint1,hint2)
p2, q2 = solve_2(n2,c2,hint)
flag1 = decrypt(n1,e,c1,p1,q1)
flag2 = decrypt(n2,e,c2,p2,q2)
flag = flag1 + flag2
print(flag)

赛后在群里听说是板子题，乐，我怎么就没搜到

2022 赣育杯 CTF — Crypto Lost_N wp_ctf 丢失的n与d-CSDN博客

fffffhash

import os
from Crypto.Util.number import *
def giaogiao(hex_string):
	base_num = 0x6c62272e07bb014262b821756295c58d
	x = 0x0000000001000000000000000000013b
	MOD = 2**128
	for i in hex_string:
		base_num = (base_num * x) & (MOD - 1) 
		base_num ^= i
	return base_num


giao=201431453607244229943761366749810895688

print("1geiwoligiaogiao")
hex_string = int(input(),16)
s = long_to_bytes(hex_string)

if giaogiao(s) == giao:
	print(os.getenv('FLAG'))
else:
	print("error")

对一个自定义的类hash函数，尝试了很久逆算法，应该要用格

# sage
TARGET = 201431453607244229943761366749810895688
h0 = 0x6c62272e07bb014262b821756295c58d
p = 0x0000000001000000000000000000013b
MOD = 2**128

n = 16
M = Matrix.column([p^(n - i - 1) for i in range(n)] + [-(TARGET - h0*p^n), MOD])
M = M.augment(identity_matrix(n+1).stack(vector([0] * (n+1))))
Q = Matrix.diagonal([2^128] + [2^4] * n + [2^8])
M *= Q
M = M.BKZ()
M /= Q
for r in M:
    if r[0] == 0 and abs(r[-1]) == 1:
        r *= r[-1]
        good = r[1:-1]
        print(good)
        break
inp = []
y = int(h0*p)
t = (h0*p^n + good[0] * p^(n-1)) % MOD
for i in range(n):
    for x in range(256):
        y_ = (int(y) ^^ int(x)) * p^(n-i-1) % MOD
        if y_ == t:
            print('good', i, x)
            inp.append(x)
            if i < n-1:
                t = (t + good[i+1] * p^(n-i-2)) % MOD
                y = ((int(y) ^^ int(x)) * p) % MOD
            break
    else:
        print('bad', i)
print(bytes(inp).hex())
# 020101081b04390001051a020a3d0f0f

这个是赛后看其他密码爷的wp学

听说是板子题？？？典

Challenges_2023_Public/crypto/fnv/solve/solution_joseph_LLL.sage at main · DownUnderCTF/Challenges_2023_Public

这个DownunderCTF 2023比赛怎么老被国内抄题，记得好像强网杯apbq这个题第二部分也是抄这个比赛，以后要多打打CTF Time了

见多识广的师傅们说看这个x = 0x0000000001000000000000000000013b参数就知道是FNV-128bit算法

3F/Fnv1a128: FNV-1a 「 128-bit 」 High-Speed implementations 🚀 using LX4Cnh etc.

babypqc

import ctypes
from random import getrandbits
import signal
import socketserver
from sympy import nextprime
import numpy as np  
from Crypto.Util.number import *
import ast


def ll_to_polylist(l):
    return list(map(list, list(l)))

class Dilithium:
    def __init__(self):
        self.dilithium_lib = ctypes.CDLL("./dilithium/libpqcrystals_dilithium2_ref.so")
        self.pk_buf = ctypes.c_buffer(1312)
        self.sk_buf = ctypes.c_buffer(2560)
        self.Q = 8380417
        self.N = 256
        self.dilithium_lib.pqcrystals_dilithium2_ref_keypair(self.pk_buf, self.sk_buf)

    def sign_message(self, message: bytes) -> bytes:
        SIGNLEN = 2420
        MLEN = len(message)
        sm_buf = ctypes.create_string_buffer(SIGNLEN + MLEN)
        m_buf = ctypes.create_string_buffer(message)
        smlen_buf = ctypes.c_size_t()
        self.dilithium_lib.pqcrystals_dilithium2_ref(sm_buf, ctypes.byref(smlen_buf), m_buf, MLEN, self.sk_buf)
        return sm_buf.raw[:smlen_buf.value]

    def verify_sign(self, message: bytes, signature: bytes) -> bool:
        msg_buf = ctypes.create_string_buffer(len(signature))
        msg_len = ctypes.c_size_t()
        sm_buf = ctypes.create_string_buffer(signature)
        result = self.dilithium_lib.pqcrystals_dilithium2_ref_open(msg_buf, ctypes.byref(msg_len), sm_buf, len(signature), self.pk_buf)
        return result == 0 and message == msg_buf.raw[:msg_len.value]


class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)
    

    def timeout_handler(self, signum, frame):
        raise TimeoutError
    

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass


    def recvline(self, msg = None):
        if msg:
            self.request.sendall(msg.encode('latin-1'))
        try:
            data = b""
            while True:
                chunk = self.request.recv(1)
                if not chunk:
                    break
                data += chunk
                if chunk == b'\n':
                    break
        except:
            pass

        line = data.strip().decode()
        return line

        
    def generate_prime(self, BITS):
        a = getrandbits(BITS)
        b = a << 282
        c = nextprime(b)
        return c
    

    def generate_coefs(self, BITS, LEN):
        return [getrandbits(BITS) for _ in range(LEN)]
    

    def get_sk(self):
        poly_t = ctypes.c_int32 * self.dilithium.N
        polyvec_t = poly_t * 4
        rho = ctypes.c_buffer(32)
        tr = ctypes.c_buffer(64)
        key = ctypes.c_buffer(32)
        t0 = polyvec_t()
        s1 = polyvec_t()
        s2 = polyvec_t()
        self.dilithium.dilithium_lib.pqcrystals_dilithium2_ref_unpack_sk(rho, tr, key, t0, s1, s2, self.dilithium.sk_buf)
        return ll_to_polylist(s1), ll_to_polylist(s2)


    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(40)
        self.dosend("welcome to my crypto system!")
        delta = 1184
        beta = 256
        tau = 704
        self.m = getrandbits(beta)
        self.dilithium = Dilithium()

        p = self.generate_prime(delta)
        q = self.generate_prime(delta)
        N = [p * q]
        ROUND = 25
        for _ in range(ROUND):
            d = getrandbits(704)
            N.append((p + d) * (q + d))
        self.dosend("N = " + str(N))
        s1, s2 = self.get_sk()
        s1 = np.array([i for j in s1 for i in j])
        s2 = np.array([i for j in s2 for i in j])
        H = []
        for i in range(ROUND * ROUND):
            tmp = np.array(self.generate_coefs(32, 1024))
            H.append(int(tmp.dot(s1) % self.dilithium.Q ))
            tmp = np.array(self.generate_coefs(32, 1024))
            H.append(int(tmp.dot(s2) % self.dilithium.Q))

        self.dosend("this is your hint!")
        self.dosend("H = " + str(H))
        self.dosend("another gift: you can choose one message to sign")
        m = int(self.recvline("m: "))
        signature = self.dilithium.sign_message(long_to_bytes(m))
        assert self.dilithium.verify_sign(long_to_bytes(m), signature)
        self.dosend("this is your signature")
        self.dosend("sinature = " + signature.hex())
        num = self.generate_coefs(4, 1)[0]
        self.dosend("you need to give me some signatures in hex format!")
        signatures = ast.literal_eval(self.recvline("signatures: "))
        assert len(list(set(signatures))) == len(signatures)
        answers = sum([self.dilithium.verify_sign(long_to_bytes(self.m), bytes.fromhex(sinature.zfill(len(signature) + len(signature)%2))) for sinature in signatures])
        if answers == num:
            self.dosend("congrats! you got the flag!")
            with open("flag.txt") as f:
                self.dosend(f.read())
        else:
            self.dosend("sorry, you failed!")
            exit()
        


class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 13337
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()



最后只有两解，赛后听群友说了非预期解法

第一次随便输
第二次输入 []
就有 1/16 的概率拿到 flag

因为当signatures为[]，assert len(list(set(signatures))) == len(signatures)也能被通过

此时answer = 0

num是由self.generate_coefs(4, 1)[0]产生

def generate_coefs(self, BITS, LEN):
        return [getrandbits(BITS) for _ in range(LEN)]

即在0-15间产生一个随机数

如果恰好随机数num = 0，此时answer = 0，通过，得到flag

LWEWL

from Crypto.Util.number import *
from random import randint
from secret import flag

assert flag.startswith(b'flag{') and flag.endswith(b'}')
flag = flag[5:-1]
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]

class LWE:
    def __init__(self, lwe_dim, lwe_num_samples, lwe_plaintext_modulus, lwe_ciphertext_modulus, rlwe_dim, rlwe_modulus):
        self.lwe_dim = lwe_dim
        self.lwe_num_samples = lwe_num_samples
        self.lwe_plaintext_modulus = lwe_plaintext_modulus
        self.lwe_ciphertext_modulus = lwe_ciphertext_modulus
        self.lwe_secret_key = self.distribution(0, self.lwe_ciphertext_modulus - 1, self.lwe_dim)
        self.rlwe_dim = rlwe_dim
        self.rlwe_modulus = rlwe_modulus

    def distribution(self, lbound, rbound, dim):
        return [randint(lbound, rbound) for _ in range(dim)]

    def lwe_encrypt(self, message):
        a = self.distribution(0, lwe_ciphertext_modulus - 1, self.lwe_dim)
        e = self.distribution(-15, 15, 1)[0]
        return a, sum([a[i] * self.lwe_secret_key[i] for i in range(self.lwe_dim)]) + message + e * lwe_plaintext_modulus

    def lwe_keygen(self):
        A = []
        B = []
        for _ in range(self.lwe_num_samples):
            sample = self.lwe_encrypt(0)
            A.append(sample[0])
            B.append(sample[1])
        return A, B

    def encrypt(self, message, lwe_pubkey1, lwe_pubkey2):
        const = vector(ZZ, self.distribution(-1, 1, self.lwe_num_samples))
        e = self.distribution(-15, 15, 1)[0]
        return const * matrix(GF(lwe_ciphertext_modulus), lwe_pubkey1), const * vector(GF(lwe_ciphertext_modulus), lwe_pubkey2) + message + e * lwe_plaintext_modulus

    def rlwe_sample(self, flag):
        P.<x> = PolynomialRing(Zmod(self.rlwe_modulus))

        while True:
            monomials = [x^i for i in range(self.rlwe_dim + 1)]
            c = self.distribution(0, self.rlwe_modulus - 1, self.rlwe_dim) + [1]
            f = sum([c[i] * monomials[i] for i in range(self.rlwe_dim + 1)])
            PR = P.quo(f)
            if f.is_irreducible():
                break
        a = self.distribution(0, self.rlwe_modulus - 1, self.rlwe_dim)
        e = self.distribution(-5, 5, self.rlwe_dim)
        s = [flag[i] for i in range(len(flag))]
        b = PR(a) * PR(s) + PR(e)
        return a, b, f, self.rlwe_modulus

lwe_dimension = 2**9
lwe_num_samples = 2**9 + 2**6 + 2**5 + 2**2
lwe_plaintext_modulus = next_prime(256)
lwe_ciphertext_modulus = next_prime(1048576)
rlwe_dim = 64
rlwe_modulus = getPrime(128)

lwe = LWE(lwe_dimension, lwe_num_samples, lwe_plaintext_modulus, lwe_ciphertext_modulus, rlwe_dim, rlwe_modulus)
lwe_pubkey1, lwe_pubkey2 = lwe.lwe_keygen()
lwe_public_key = [lwe_pubkey1, lwe_pubkey2]
lwe_cipher1 = []
lwe_cipher2 = []
for flag_char in flag1:
    tmp1, tmp2 = lwe.encrypt(flag_char, lwe_pubkey1, lwe_pubkey2)
    lwe_cipher1.append(tmp1)
    lwe_cipher2.append(tmp2)

lwe_ciphertext = [lwe_cipher1, lwe_cipher2]
save(lwe_public_key, "lwe_public_key")
save(lwe_ciphertext, "lwe_ciphertext")

rlwe_ciphertext = lwe.rlwe_sample(flag2)
save(rlwe_ciphertext, "rlwe_ciphertext")

LWE问题

听说又是原题？

Dicectf2023 membrane
NSSCTF Round18 New Year Ring3