目录

janken vs kurenaif

pqpq 以前写过了，官方方法一样

witches_symmetric_exam

this is not lsb

insufficient CVP

BBB

当时仅pqpq差点完成，有个小错。其它都无从下手。终于看到wp一一试一下。原文

janken vs kurenaif

这个情况第一回见，题目给出一个种子，并通过种子生成666个[0,1,2]的随机数，来玩石头-剪刀-布，要求给出一个种子，生成的随机数都是对应的[1,2,0]。

python的随机数使用梅森旋转MT19937来生成，以前的题基本都是复现序列，通过已知的随机数部分来恢复state，从而得到与原题相同的伪随机数。这个题是在一个不满秩的情况下求种子。

import os
import signal
import random
import secretsFLAG = os.getenv("FLAG", "fake{cast a special spell}")def janken(a, b):return (a - b + 3) % 3signal.alarm(1000)
print("kurenaif: Hi, I'm a crypto witch. Let's a spell battle with me.")witch_spell = secrets.token_hex(16)
witch_rand = random.Random()
witch_rand.seed(int(witch_spell, 16))
print(f"kurenaif: My spell is {witch_spell}. What about your spell?")your_spell = input("your spell: ")
your_random = random.Random()
your_random.seed(int(your_spell, 16))for _ in range(666):witch_hand = witch_rand.randint(0, 2)your_hand = your_random.randint(0, 2)if janken(your_hand, witch_hand) != 1:print("kurenaif: Could you come here the day before yesterday?")quit()print("kurenaif: Amazing! Your spell is very powerful!!")
print(f"kurenaif: OK. The flag is here. {FLAG}")

第一步就是先求 state

from pwn import *
import randomio = remote("janken-vs-kurenaif.seccon.games", 8080)
context.log_level = 'debug'io.recvuntil(b"kurenaif: My spell is ")
u_spell = io.recvuntil(b'.', drop= True).decode()print(f"{u_spell = }")
#u_spell = 'df74f6c5c096355a87ec544c1ac865e8'u_rand = random.Random()
u_rand.seed(int(u_spell, 16))u_hand = [u_rand.randint(0,2) for _ in range(666)]
i_hand = [(i+1)%3 for i in u_hand]#solve prng
from Untwister import Untwister as _Untwister
import logging
logging.disable()# Superclass Untwister to obtain PRNG state after seeding
# instead of PRNG state after outputs generated
class Untwister(_Untwister):def __init__(self):super().__init__()self.first_MT = self.MT# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L201# Index is 624 after seedingself.index = 624def get_random(self):# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L232# First MT state is set to 0x80000000 after seedingself.solver.add(self.first_MT[0] == 0x80000000)print(self.solver.check())model = self.solver.model()state = [model[x].as_long() if model[x] is not None else 0for x in self.first_MT]result_state = (3, tuple(state+[624]), None)rand = random.Random()rand.setstate(result_state)return randut = Untwister()
for me in i_hand:res = bin(me)[2:].zfill(2) + "?" * 30  #fill to 32bitsut.submit(res)
ut_rand = ut.get_random()
ut_rand_state = ut_rand.getstate()[1][:-1]# sanity check
for me in i_hand:assert me == ut_rand.randint(0, 2)

这里边用到一个模块Untwister 可以到github下载，其实本身很短，直接放在这。

#https://raw.githubusercontent.com/icemonster/symbolic_mersenne_cracker/main/main.py
from z3 import *
from random import Random
from itertools import count
from time import time
import logginglogging.basicConfig(format='STT> %(message)s')
logger = logging.getLogger()
logger.setLevel(logging.DEBUG)SYMBOLIC_COUNTER = count()class Untwister:def __init__(self):name = next(SYMBOLIC_COUNTER)self.MT = [BitVec(f'MT_{i}_{name}', 32) for i in range(624)]self.index = 0self.solver = Solver()#This particular method was adapted from https://www.schutzwerk.com/en/43/posts/attacking_a_random_number_generator/def symbolic_untamper(self, solver, y):name = next(SYMBOLIC_COUNTER)y1 = BitVec(f'y1_{name}', 32)y2 = BitVec(f'y2_{name}' , 32)y3 = BitVec(f'y3_{name}', 32)y4 = BitVec(f'y4_{name}', 32)equations = [y2 == y1 ^ (LShR(y1, 11)),y3 == y2 ^ ((y2 << 7) & 0x9D2C5680),y4 == y3 ^ ((y3 << 15) & 0xEFC60000),y == y4 ^ (LShR(y4, 18))]solver.add(equations)return y1def symbolic_twist(self, MT, n=624, upper_mask=0x80000000, lower_mask=0x7FFFFFFF, a=0x9908B0DF, m=397):'''This method models MT19937 function as a Z3 program'''MT = [i for i in MT] #Just a shallow copy of the statefor i in range(n):x = (MT[i] & upper_mask) + (MT[(i+1) % n] & lower_mask)xA = LShR(x, 1)xB = If(x & 1 == 0, xA, xA ^ a) #Possible Z3 optimization here by declaring auxiliary symbolic variablesMT[i] = MT[(i + m) % n] ^ xBreturn MTdef get_symbolic(self, guess):name = next(SYMBOLIC_COUNTER)ERROR = 'Must pass a string like "?1100???1001000??0?100?10??10010" where ? represents an unknown bit'assert type(guess) == str, ERRORassert all(map(lambda x: x in '01?', guess)), ERRORassert len(guess) <= 32, "One 32-bit number at a time please"guess = guess.zfill(32)self.symbolic_guess = BitVec(f'symbolic_guess_{name}', 32)guess = guess[::-1]for i, bit in enumerate(guess):if bit != '?':self.solver.add(Extract(i, i, self.symbolic_guess) == bit)return self.symbolic_guessdef submit(self, guess):'''You need 624 numbers to completely clone the state.You can input less than that though and this will give you the best guess for the state'''if self.index >= 624:name = next(SYMBOLIC_COUNTER)next_mt = self.symbolic_twist(self.MT)self.MT = [BitVec(f'MT_{i}_{name}', 32) for i in range(624)]for i in range(624):self.solver.add(self.MT[i] == next_mt[i])self.index = 0symbolic_guess = self.get_symbolic(guess)symbolic_guess = self.symbolic_untamper(self.solver, symbolic_guess)self.solver.add(self.MT[self.index] == symbolic_guess)self.index += 1def get_random(self):'''This will give you a random.Random() instance with the cloned state.'''logger.debug('Solving...')start = time()self.solver.check()model = self.solver.model()end = time()logger.debug(f'Solved! (in {round(end-start,3)}s)')#Compute best guess for statestate = list(map(lambda x: model[x].as_long(), self.MT))result_state = (3, tuple(state+[self.index]), None)r = Random()r.setstate(result_state)return r

得到state后可以验证真能生成指定的序列。

第二步是根据这个state计算种子，这个用z3来实现，在复现过程中发现计算这东西不是每次都成功，有的数据可能会运算很久也不出结果。所以不行的时候可以重来换个spell。这块也是没有能力写的，只能原文复制下来。然后保存后用。

#2.get seed
from z3 import *prng_N = 624def u32(x):return x & 0xffffffff# Note that LShR is used instead of ">>" operator
# unsigned 32 bit integers use logical bitshift, not arithmetic bitshift.# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L186
def init_genrand(s):mt = [0 for _ in range(prng_N)]mt[0] = BitVecVal(s, 32)mti = 1while mti < prng_N:mt[mti] = u32(1812433253 * (mt[mti-1] ^ LShR(mt[mti-1], 30)) + mti# 1812433253 * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti)mti += 1return mt, mti# https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L209
def init_by_array(init_key):key_length = len(init_key)mt, mti = init_genrand(19650218)i, j = 1, 0k = prng_N if prng_N > key_length else key_lengthwhile k:mt[i] = u32((mt[i] ^ ((mt[i-1] ^ LShR(mt[i-1], 30)) * 1664525)) + init_key[j] + j)i, j = i + 1, j + 1if i >= prng_N:mt[0] = mt[prng_N-1]i = 1if j >= key_length:j = 0k -= 1k = prng_N - 1while k:mt[i] = u32((mt[i] ^ ((mt[i-1] ^ LShR(mt[i-1], 30)) * 1566083941)) - i)i += 1if i >= prng_N:mt[0] = mt[prng_N-1]i = 1k -= 1mt[0] = 0x80000000;return mtseed_vars = [BitVec(f"seed_{i}", 32) for i in range(624)
]
seed_rand_state = init_by_array(seed_vars)s = Solver()
for a, b in zip(seed_rand_state, ut_rand_state):s.add(a == b)
print('check:',s.check())model = s.model()
print(f"{model = }")
seed_init_key = [model[x].as_long() if model[x] is not None else 0for x in seed_vars
]
print(f"{seed_init_key[:10] = }")

最后把所有计算得到的key连起来（每个32位，4字节，一个非常长的数）

#3,get my spell 
seed_rand_seed = sum([x * (2 ** (idx * 32))for idx, x in enumerate(seed_init_key)])
print("seed_rand_seed =", hex(seed_rand_seed)[2:52], "...")seed_rand = random.Random()
seed_rand.seed(seed_rand_seed)# sanity check
assert seed_rand.getstate()[1][:-1] == ut_rand_state
for me in i_hand:assert me == seed_rand.randint(0, 2)print(f"I spell:{hex(seed_rand_seed)[2:]}")io.sendline(f"{hex(seed_rand_seed)[2:]}".encode())
print(io.recvall().decode())

pqpq 以前写过了，官方方法一样

witches_symmetric_exam

题目很明了，题目先将secret_spell用AES_GCM加密，然后将tag,nonce与cipher连一起，再进行AES_OFB方式加密，返回iv+cipher。

后台提供解密功能，但仅返回错在哪。

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from flag import flag, secret_spellkey = get_random_bytes(16)
nonce = get_random_bytes(16)def encrypt():data = secret_spellgcm_cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)gcm_ciphertext, gcm_tag = gcm_cipher.encrypt_and_digest(data)  #CTR+消息验证码（?）ofb_input = pad(gcm_tag + gcm_cipher.nonce + gcm_ciphertext, 16)ofb_iv = get_random_bytes(16)ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)  #OFB ciphertext = ofb_cipher.encrypt(ofb_input)return ofb_iv + ciphertextdef decrypt(data):ofb_iv = data[:16]ofb_ciphertext = data[16:]ofb_cipher = AES.new(key, AES.MODE_OFB, iv=ofb_iv)try:m = ofb_cipher.decrypt(ofb_ciphertext)temp = unpad(m, 16)   #从最后一位paddingexcept:return b"ofb error"try:gcm_tag = temp[:16]gcm_nonce = temp[16:32]gcm_ciphertext = temp[32:]gcm_cipher = AES.new(key, AES.MODE_GCM, nonce=gcm_nonce)plaintext = gcm_cipher.decrypt_and_verify(gcm_ciphertext, gcm_tag)except:return b"gcm error"if b"give me key" == plaintext:your_spell = input("ok, please say secret spell:").encode()if your_spell == secret_spell:return flagelse:return b"Try Harder"return b"ok"print(f"ciphertext: {encrypt().hex()}")
while True:c = input("ciphertext: ")print(decrypt(bytes.fromhex(c)))

这显然是个padding oracle的题，ofb和gcm都是通过与固定的流异或来得到密文。通过尾部爆破看解密状态得到加密用的流。

如果padding为1字节那么尾字节就是01，当用0-255爆破时，恰好没报错的那个数与1异或就是加密流的最后一个字节，依次向前两字节就是0202，直到16。

第一段我还是明白的，leak_enc用来爆破加密流，每次发送256种情况，然后从返回中取状态，这样可以加快爆破速度，每次recvuntil是非常费时的。

from pwn import *context.log_level = "error"r = remote("witches-symmetric-exam.seccon.games", 8080)
context.log_level = 'debug'r.recvuntil(b"ciphertext: ")
enc = bytes.fromhex(r.recvline().decode())
print(f"{len(enc)  = }")
print(f"{enc.hex() = }")#get ofb stream
def bxor(*args):if len(args) == 1:return args[0]a, b = args[0], args[1:]return bytes([i ^ j for i, j in zip(a, bxor(*b))])def query(xs):r.sendline("\n".join([x.hex() for x in xs]).encode())ress = []for _ in xs:r.recvuntil(b"ciphertext: ")res = r.recv(5).strip().decode()if "b'ofb" in res:ress.append("pad")elif "b'gcm" in res:ress.append("gcm")elif "o', p" in res:ress.append("spell")elif "b'ok'" in res:ress.append("ok")else:raise ValueError(res)return ressdef leak_enc(pln):enc = [0 for _ in range(16)]for pos in range(16):print(".", end="", flush=True)expected_padding = ([0] * 16 + [pos+1] * (pos+1))[-16:]found = []probe = [0] * 16xs = []for i in range(256):probe[15-pos] = itry_block_ofb = pln + bxor(enc, expected_padding, probe)xs.append(try_block_ofb)#每次发送256个，然后再取返回信息，加快爆破速度ress = query(xs)for i, res in enumerate(ress):if res == "gcm":found.append(i)if len(found) != 1:raise ValueError("???", pos, found)enc[15-pos] = found[0]print()return bytes(enc)

然后把4段的加密流得到，异或得到gcm的tag,nonce,cipher_gcm

#get ofb
from Crypto.Util.Padding import unpadofb_iv = enc[:16]
ofb_enc = enc[16:]print(f"{ofb_iv.hex()     = }")ofb_stream = ofb_iv
for block in range(4):ofb_stream += leak_enc(ofb_stream[-16:])
ofb_stream = ofb_stream[16:]print(f"{ofb_stream.hex() = }")ofb_dec = bxor(ofb_enc, ofb_stream)
gcm_tag, gcm_nonce, gcm_enc = ofb_dec[:16], ofb_dec[16:32], unpad(ofb_dec[32:], 16)print(f"{gcm_tag.hex()    = }")
print(f"{gcm_nonce.hex()  = }")
print(f"{gcm_enc.hex()    = }")

第三步是爆破 gcm的流，这块目前还不大明白，慢慢来，GCM需要计算tag，tag是通过h0和密文通过_ghash_clmul方法运算得到，除了这个ofb,gcm基本上一样。

#GCM parameters
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Cipher._mode_gcm import _GHASH as GHASH, _ghash_clmul as ghash_c# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L223-L226
h0 = leak_enc(b"\x00" * 16)
print(f"{h0.hex() = }")# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L232-L236
nonce = gcm_nonce
fill = (16 - (len(nonce) % 16)) % 16 + 8
ghash_in = (nonce + b'\x00' * fill + long_to_bytes(8 * len(nonce), 8))
j0 = GHASH(h0, ghash_c).update(ghash_in).digest()
print(f"{j0.hex() = }")#Decrypt GCM
# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L239-L245
# nonce_ctr = j0[:12]
# iv_ctr = (bytes_to_long(j0) + 1) & 0xFFFFFFFF
# nonce_iv_bytes = nonce_ctr + bytes.fromhex(hex(iv_ctr)[2:].zfill(8))
block_one_ctr = bytes.fromhex(hex(int(j0.hex(), 16) + 1)[2:].zfill(32))
block_two_ctr = bytes.fromhex(hex(int(j0.hex(), 16) + 2)[2:].zfill(32))gcm_stream = leak_enc(block_one_ctr) + leak_enc(block_two_ctr)
gcm_pln = bxor(gcm_stream, gcm_enc)
secret_spell = gcm_pln
print(f"{secret_spell = }")

得到secret_spell就可以包装gcm,ofb包了，发送即返回flag

#3, encode 'give me key'from Crypto.Util.Padding import padsigner = GHASH(h0, ghash_c)
token_dec = b"give me key"# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L372-L379
# > encrypt and digest > encrypt
token_enc = bxor(token_dec, gcm_stream)
msg_len = len(token_enc)
# signer.update(token_enc) # defer to later for block alignment# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L459-L462
# > encrypt and digest > digest
signer.update(token_enc + b"\x00" * (16 - msg_len))
signer.update(long_to_bytes(8 * 0, 8) + long_to_bytes(8 * msg_len, 8))
tag_dec = signer.digest()# https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py#L465
# > encrypt and digest > digest > self._tag_cipher.encrypt
j0_stream = leak_enc(j0)
tag_enc = bxor(tag_dec, j0_stream)print(f"{tag_enc.hex() = }")payload = ofb_iv + bxor(pad(tag_enc + gcm_nonce + token_enc, 16), ofb_stream)
print(f"{payload.hex() = }")r.sendline(payload.hex().encode())
r.sendline(secret_spell)
flag = r.recvuntil(b"}").decode().strip()
print(flag)#SECCON{you_solved_this!?I_g1ve_y0u_symmetr1c_cipher_mage_certificate}

this is not lsb

LSB都整来，对于c = m^e mod n 来说，不断的将m乘2(c*2^e mod n)判断末位是0还是1，以确定2m与n的关系。这个题有点类似，返回的不是末位而是第1位是不是0xff

from Crypto.Util.number import *
#from flag import flag
flag = bytes_to_long(b'A'*55)
p = getStrongPrime(512)
q = getStrongPrime(512)
print(p,q)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)d = pow(e, -1, phi)print(f"n = {n}")
print(f"e = {e}")
print(f"flag_length = {flag.bit_length()}")# Oops! encrypt without padding!
c = pow(flag, e, n)
print(f"c = {c}")# padding format: 0b0011111111........
def check_padding(c):padding_pos = n.bit_length() - 2m = pow(c, d, n)return (m >> (padding_pos - 8)) == 0xFFwhile True:c = int(input("c = "))print(check_padding(c))

 看了WP，感觉啊，还可以这样。方法依然是二分法。

先确定flag的上下边界（已知flag以SECCON{开头，后补全0和全1），然后确定一个除法的最小值：int('00'+'1'*8+'0'*(b.bit_length()-10),2),然后每发送 dec//flag_md(上下边界的中间值)的e 次幂再乘c ，当返回是0xff时则说明flag在上半部（比一半大）。修改边界循环即可。

from pwn import *context.log_level = "error"# ====== Get parameters ======r = remote("this-is-not-lsb.seccon.games", 8080)
r.recvuntil(b"n = ")
n = int(r.recvline().strip().decode())
r.recvuntil(b"e = ")
e = int(r.recvline().strip().decode())
r.recvuntil(b"flag_length = ")
flag_length = int(r.recvline().strip().decode())
r.recvuntil(b"c = ")
c = int(r.recvline().strip().decode())print(f"{n           = }")
print(f"{e           = }")
print(f"{flag_length = }")
print(f"{c           = }")def query(k):y = (pow(k, e, n) * c) % nr.recvuntil(b"c = ")r.sendline(f"{y}".encode())res = r.recvline().decode().strip()if res == "True":return Trueelif res == "False":return Falseelse:raise ValueError(res)dec_lb = int("0011111111".ljust(n.bit_length(), "0"), 2)
dec_ub = int("0011111111".ljust(n.bit_length(), "1"), 2)
flag_lb = int((b"SECCON{"+ b"\x00" * 48).hex(), 16)
flag_ub = int((b"SECCON{"+ b"\xff" * 48).hex(), 16)# ====== Binary search ======while flag_ub - flag_lb > 10:flag_md = (flag_lb + flag_ub) // 2coef = dec_lb // flag_mdif query(coef):print("-", end="", flush=True)flag_lb = flag_mdelse:print("+", end="", flush=True)flag_ub = flag_md
print()
flag = bytes.fromhex(hex(flag_lb)[2:])
print(f"{flag = }")

insufficient CVP

又是一个看着大概认识又不会的题。求系数用格基约减。但这里差一点，就是有两个未知的情况。

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG# f(x,y,z) = a1*x + a2*x^2 + a3*x^3
#          + b1*y + b2*y^2 + b3*y^3
#          + c*z + s mod p
def calc_f(coeffs, x, y, z, p):ret = 0ret += x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]ret += y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]ret += z * coeffs[6]ret += coeffs[7]return ret % pp = getPrime(512)# [a1, a2, a3, b1, b2, b3, c, s]
coeffs = [randint(0, 2**128) for _ in range(8)]key = 0
for coeff in coeffs:key <<= 128key ^= coeffcipher_text = bytes_to_long(FLAG) ^ key
print(cipher_text)shares = []
for _ in range(4):x = randint(0, p)y = randint(0, p)z = randint(0, 2**128)w = calc_f(coeffs, x, y, z, p)packed_share = ((x,y), w)shares.append(packed_share)print(p)
print(shares)

这里4个x,y已经给出，但z没给，假设没有6，7两个系数的情况下用

这里多的c7,c7,z都只有128位，与已知的x,y,p的512比很小，这里先将其忽略求出近似值，将右侧的单位对角阵乘2^128，在左上与w之间补一个对角阵p，并在最后加一列写一个极大值，这样可以用CVP算法求得前6个参数*2^128的挖值，再除去2^128即可得到前6个参数。

#read msg
f = open('output.txt')
cipher_text = int(f.readline())
p = int(f.readline())
shares = eval(f.readline())'''| A  B  O |    A= x0,x1,... y0^3,y1^3,...
M = | C  O  O |    B= I*2^128    C= I*p| D  E  L |    D= -w0,-w1..  L= largeE= O,  对M进行格基约减后，得到的前6个参数
'''
r, c = 11, 11
two_127 = 2**127
two_128 = 2**128
large = 2**1024A = matrix(ZZ, 6,4)
B = identity_matrix(ZZ,6)*2^128
C = identity_matrix(ZZ,4)*p 
D = matrix(ZZ, 1,4)
L = matrix(ZZ, 1,1, [large])
for i in range(4):xi,yi = shares[i][0]A[0,i],A[1,i],A[2,i] = xi, xi**2, xi**3A[3,i],A[4,i],A[5,i] = yi, yi**2, yi**3  D[0,i] = -shares[i][1]M = block_matrix(3, [[A,B,zero_matrix(ZZ,6,1)],[C,zero_matrix(ZZ,4,6),zero_matrix(ZZ,4,1)],[D,zero_matrix(ZZ,1,6),L]])vec = vector(ZZ,11)
for i in range(6):vec[i] = two_127*two_128
vec[10] = large # https://jgeralnik.github.io/writeups/2021/08/12/Lattices/
def closest_vector(B, target):# Babai's Nearest Plane algorithmM = B.LLL()G = M.gram_schmidt()[0]small = targetfor _ in range(1):for i in reversed(range(M.nrows())):c = ((small * G[i]) / (G[i] * G[i])).round()small -= M[i] * creturn target - smallcv = closest_vector(M, vec)
assert cv[10] == largefor idx, cvi in enumerate(cv):print(f"cv[{idx}] = {cvi}")coeffs = [i//two_128 for i in cv[4:10]]
czs = [int((w - (x * coeffs[0] + pow(x, 2, p) * coeffs[1] + pow(x, 3, p)*coeffs[2]+ y * coeffs[3] + pow(y, 2, p) * coeffs[4] + pow(y, 3, p)*coeffs[5]))%p) for (x,y),w in shares]  #模值需要转整c6 = gcd(czs[1]-czs[0], czs[2]-czs[0])
c7 = czs[0]%c6 coeffs += [c6,c7]key = 0
for coeff in coeffs:key <<= 128key ^^= coeff
flag = cipher_text ^^ key
flag = bytes.fromhex(hex(flag)[2:])#SECCON{Unfortunately_I_could_not_come_up_with_a_more_difficult_problem_than_last_year_sorry...-6fc18307d3ed2e7673a249abc2e0e22c}

这里在求czs的时候没有用WP里的方法，而是直接用的式子，在sage里由于作了取模，所以czs[1]-czs[0]会自动取模得到模p的值，从而无法用gcd，所以在取模后需要用int对数字进行转换，转成数字型再运算。看别人几句话就写出来，自己一练才发现功夫还着得远。

BBB

最后一个BBB就相对简单点了，远端是个RNG，a,p已知，b可以输入，那这个RNG就可以控制了，但运算次数不定，在10-100之间。要求输入5个种子，用生成的值作为e，并且每次都生成n，并对flag加密后返回。

from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from math import gcd
from secret import FLAG
from os import urandomassert len(FLAG) < 100def generate_key(rng, seed):e = rng(seed)while True:for _ in range(randint(10,100)):e = rng(e)p = getPrime(1024)q = getPrime(1024)phi = (p-1)*(q-1)if gcd(e, phi) == 1:breakn = p*qreturn (n, e)def generate_params():p = getPrime(1024)a = randint(0, p-1)return (p,a)def main():p,a = generate_params()print("[+] The parameters of RNG:")print(f"{a=}")print(f"{p=}")b = int(input("[+] Inject [b]ackdoor!!: "))rng = lambda x: (x**2 + a*x + b) % pkeys = []seeds = []for i in range(5):seed = int(input("[+] Please input seed: "))seed %= pif seed in seeds:print("[!] Same seeds are not allowed!!")exit()seeds.append(seed)n, e = generate_key(rng, seed)if e <= 10:print("[!] `e` is so small!!")exit()keys.append((n,e))flag = bytes_to_long(FLAG + urandom(16))for n,e in keys:c = pow(flag, e, n)print("[+] Public Key:")print(f"{n=}")print(f"{e=}")print("[+] Cipher Text:", c)if __name__ == "__main__":main()

思路也简单，首先就是这个题n肯定是没法分解，给5组值也就是用中国剩余定理了，这就要求e要相同，当然e必需相同，不然rng会出来不确定的值。

首先通过输入b来确定e，也就是让f(x)==x 由于有要求e必需大于10所以这里e选11，先求得b

这样不管运行多少次都能保证结果是11也就能确定e

然后要求输入5组x那就要算出 f(x1) == e,f(x2)== x1,...

因为前边有10次运算，并且大概率这个运算会超过20次，所以空间很大，不行就重爆破。

当然这里因为有x^2所以每步都可能有两个解，凑够4个即可。

最后将得到的c,n用 crt得到m再开11次方。

from pwn import *io = remote('BBB.seccon.games', 8080)
context.log_level = 'debug'io.recvuntil(b'a=')
a = int(io.recvline().strip())io.recvuntil(b'p=')
p = int(io.recvline().strip())#rng(11) = 11^2 + a*11 + b mod p
P. = PolynomialRing(Zmod(p), 'x')
e = 11
eq = e^2 + a*e + x - e
b = eq.roots()[0][0]
print(f'{b=}')#rng(a1) = a2 ;rng(a2) = a3 ; ... rng(a4) = 11; rng(11) = 11
ra = [e]
while len(ra)<5:eq = x^2 + a*x + b - ra[-1]d = eq.roots()for j,_ in d:if j not in ra:ra.append(j)print(f"{j = }")io.sendlineafter(b'[+] Inject [b]ackdoor!!:', str(b).encode())
for i in range(5):io.sendlineafter(b"[+] Please input seed: ", str(ra[i]).encode())n_a ,e_a ,c_a = [], [], []
for i in range(5):io.recvuntil(b'n=')n_a.append(int(io.recvline().strip()))io.recvuntil(b'[+] Cipher Text: ')c_a.append(int(io.recvline().strip()))f11 = crt(c_a,n_a)
m = f11.nth_root(11)
flag = bytes.fromhex(hex(m)[2:])
print(flag)