清明大部分时间出去玩了，没咋打，写了几道简单的
Division
题目：
# -*- 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')
随机数预测
choose == '1'时，输入'1'，返回的就是random.getrandbits(32)，以此进行随机数预测
choose == '2'时，预测rand1和rand2
exp：
from Crypto.Util.number import *
from Crypto.Util.number import *
from random import *
from tqdm import *
from pwn import *
r = remote("47.93.96.189",'28876')
######################################################## part1 recover MT and get seed
RNG = Random()
def construct_a_row(RNG):
row = []
for _ in range(624):
# 获取 8 位随机数,右移 6 位只保留前 2 位
bits = RNG.getrandbits(32)
# 转换为二进制并填充到 2 位
row += list(map(int, bin(bits)[2:].zfill(32)))
return row
L = []
for i in trange(0,19968):
state = [0]*624
temp = "0"*i + "1"*1 + "0"*(19968-1-i)
for j in range(624):
state[j] = int(temp[32*j:32*j+32],2)
RNG.setstate((3,tuple(state+[624]),None))
L.append(construct_a_row(RNG))
L = Matrix(GF(2),L)
print(L.nrows(), L.ncols())
R = []
# c = []
for i in range(624):
r.recvuntil(b": >>>")
r.sendline(b'1')
r.recvuntil(b": >>>")
r.sendline(b'1')
r.recvuntil(b'=')
k = r.recvline()
print(k)
gift = eval(k.strip().decode())
print(gift)
R += list(map(int, (bin(((gift)))[2:].zfill(32))))
print(len(R))
R = vector(GF(2),R)
s = L.solve_left(R)
print(s)
r.interactive()
s =
init = "".join(list(map(str,s)))
state = []
for i in range(624):
state.append(int(init[32*i:32*i+32],2))
RNG1 = Random()
RNG1.setstate((3,tuple(state+[624]),None))
for i in range (624):
k = RNG1.getrandbits(32)
rand1 = RNG1.getrandbits(11000)
rand2 = RNG1.getrandbits(10000)
correct_ans = rand1 // rand2
print(correct_ans)
Complex_signin
题目：
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'
'''
有：
则有两个式子的实部相等：
使用二元copper算出x，y
exp：
from Crypto.Util.number import *
import gmpy2
import itertools
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
e = 3
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
R.<x,y> = PolynomialRing(Zmod(n))
f = (mh[0]+x)**3-3*(mh[0]+x)*(mh[1]+y)**2-C[0]
res = small_roots(f,(2^129,2^129),m=3,d=4)
y = (res)
print(y)
# [(200140573956551184845123803212115015633, 62109784561410747979732334460991877433)]
from Crypto.Cipher import ChaCha20
import hashlib
re = 3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745762043102992820636089665887925419408029649
im = 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550422285594849620684268131197026134044985
# print(mh[0]+200140573956551184845123803212115015633)
# print(mh[1]+62109784561410747979732334460991877433)
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'
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(re + im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').decrypt(enc)}")
# XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}
reed
题目：
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)
这题的a和b都是随机的，我们可以输入一个seed，然后使这个a和b是已知的，就成功了
只需要让
random.seed(x**2 + 1)
y = random.randint(self.a, self.b)
## 这里如果y == x 那么整个随机数的list就是[x]
random.seed(y**2 + 1)
z = random.randint(self.a, self.b)
## 这里如果z == x 那么整个随机数的list就是[x, y]
random.seed(z**2 + 1)
k = random.randint(self.a, self.b)
## 这里如果k == x 那么整个随机数的list就是[x, y, z]
## 以此类推爆破即可
exp：
import string
import random
for x in range (1145140,19198100):
if x % 100000 == 0: # 每 100000 次打印进度
print(x)
x1 = x**2+1
y1 = x1
random.seed(y1)
y1 = random.randint(1145140, 19198100)
if y1**2+1 == x1: # 如果第一次就匹配，直接返回
print(1, x)
break
random.seed(y1**2+1)
y1 = random.randrange(1145140, 19198100)
if y1**2+1 == x1:
print(2, x)
break
random.seed(y1**2+1)
y1 = random.randrange(1145140, 19198100)
if y1 ** 2 + 1 == x1:
print(3, x)
break
# 2,7234044
那么我们只需要传入的seed，就可以知道a和b是[17593903,7234044]中的随机一个，再排列组合尝试解密即可
import string
import random
from Crypto.Util.number import *
table = string.ascii_letters + string.digits
c = []
tmp = [17593903,7234044]
t_m = []
str = ''
for i in c:
t_m.append ((i - tmp[0])*inverse(tmp[0],19198111)%19198111)
print(t_m)
for i in t_m:
str += (table[i])
print('XYCTF{'+str+'}')
# XYCTF{114514fixedpointissodangerous1919810}
*勒索病毒
题目：
给了一个exe，使用pyinstxtractor反编译，打开task发现加密代码
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
N = 49
p = 3
q = 128
d = 3
assert q > (6 * d + 1) * p
R.<x> = ZZ[]
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的私钥来加密sm4，但是发现这道题反编译出来的文件中有私钥了，所以就非预期直接就能解，我在这里写一下预期怎么做，其实就是多了一个多项式的ntru的解密
造格：
(I是单位矩阵)
exp:
import random
from Crypto.Util.number import *
Zx.<x> = ZZ[]
# R.<x> = ZZ[]
def balancedmod(f,q):
g = list( ((f[i] + q//2) % q) - q//2 for i in range(n) )
return Zx(g)
def cyclicconvolution(f, g):
return (f*g) % (x^n-1)
def invertmodprime(f,p):
T = Zx.change_ring(Integers(p)).quotient(x^n-1)
return Zx(lift(1 / T(f)))
def invertmodpowerof2(f,q):
assert q.is_power_of(2)
g = invertmodprime(f,2)
while True:
r = balancedmod(cyclicconvolution(g,f),q)
if r == 1: return g
g = balancedmod(cyclicconvolution(g,2 - r),q)
def encrypt(message, publickey):
r = rpoly()
return balancedmod(cyclicconvolution(publickey, r) + message, q)
def decrypt(cipher,f,fp):
# cipher=Zx(cipher)
a=balancedmod(cyclicconvolution(f, cipher), q)
m=balancedmod(cyclicconvolution(fp, a),p)
return m
def attack(publickey):
recip3 = lift(1/Integers(q)(3))
publickeyover3 = balancedmod(recip3 * publickey,q)
M = matrix(2 * n)
for i in range(n):
M[i,i] = q
for i in range(n):
M[i+n,i+n] = 1
c = cyclicconvolution(x^i,publickeyover3)
for j in range(n):
M[i+n,j] = c[j]
M = M.LLL()
for j in range(2 * n):
try:
f = Zx(list(M[j][n:]))
f3 = invertmodprime(f,3)
return (f,f3)
except:pass
return (f,f)
n = 49
p = 3
q = 128
d = 3
assert q>(6*d+1)*p
h = 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
e = 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
encrypted_flag = "bf0cb5cc6bea6146e9c1f109df953a57daa416d38a8ffba6438e7e599613e01f3b9a53dace4ccd55cd3e55ef88e0b835"
# publickey,secretkey = keypair()
donald = attack(h.coefficients(sparse=False))
m = decrypt(e,donald[0],donald[1])
print(str(Zx(m)))
# -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
算出来和enc.txt的一模一样
然后解rc4
exp：
from gmssl import sm4
import binascii
import re
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 terms(poly_str):
terms = []
pattern = r'([+-]?\s*x\^?\d*|[-+]?\s*\d+)'
matches = re.finditer(pattern, poly_str.replace(' ', ''))
for match in matches:
print(match)
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 sm4_decrypt(key_hex, ciphertext_hex):
key = binascii.unhexlify(key_hex)
cipher = sm4.CryptSM4()
cipher.set_key(key, sm4.SM4_DECRYPT)
ciphertext = binascii.unhexlify(ciphertext_hex)
plaintext = cipher.crypt_ecb(ciphertext)
return plaintext
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)
m = " -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"
m_ = terms(m)
hex_key = gen_key(m_)
encrypted_flag = "bf0cb5cc6bea6146e9c1f109df953a57daa416d38a8ffba6438e7e599613e01f3b9a53dace4ccd55cd3e55ef88e0b835"
flag = sm4_decrypt(hex_key, encrypted_flag)
print(flag)
参考：
XYCTF25 不知道 WP
2022DASCTF7月赋能赛
*复复复复数
题目：
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
'''
四元数除法算出p, q, r
四元数的欧拉函数：
m较小直接modp下求解
exp：
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 inv(l,mod):
inv_len=inverse(sum(i**2 for i in l),mod)
return ComComplex([l[0]*inv_len%mod,-l[1]*inv_len%mod,-l[2]*inv_len%mod,-l[3]*inv_len%mod])
from Crypto.Util.number import *
hints = [375413371936,452903063925,418564633198,452841062207]
gift = [8123312244520119413231609191866976836916616973013918670932199631084038015924368317077919454611785179950870055560079987034735836668109705445946887481003729,20508867471664499348708768798854433383217801696267611753941328714877299161068885700412171,22802458968832151777449744120185122420871929971817937643641589637402679927558503881707868,40224499597522456323122179021760594618350780974297095023316834212332206526399536884102863]
P = 8123312244520119413231609191866976836916616973013918670932199631182724263362174895104545305364960781233690810077210539091362134310623408173268475389315109
n = 408713495380933615345467409596399184629824932933932227692519320046890365817329617301604051766392980053993030281090124694858194866782889226223493799859404283664530068697313752856923001112586828837146686963124061670340088332769524367
c = ComComplex([212391106108596254648968182832931369624606731443797421732310126161911908195602305474921714075911012622738456373731638115041135121458776339519085497285769160263024788009541257401354037620169924991531279387552806754098200127027800103,24398526281840329222660628769015610312084745844610670698920371305353888694519135578269023873988641161449924124665731242993290561874625654977013162008430854786349580090169988458393820787665342793716311005178101342140536536153873825,45426319565874516841189981758358042952736832934179778483602503215353130229731883231784466068253520728052302138781204883495827539943655851877172681021818282251414044916889460602783324944030929987991059211909160860125047647337380125,96704582331728201332157222706704482771142627223521415975953255983058954606417974983056516338287792260492498273014507582247155218239742778886055575426154960475637748339582574453542182586573424942835640846567809581805953259331957385])
e=65547
inv=ComComplex.inv(hints,P)
gifts=ComComplex(gift)
keys=inv*gifts%P
print(keys)
_,p,q,r=keys.value
d=inverse(e,(q**4-q**3-q**2+q)//3)
m=pow(c,d,q)
for i in m.value:
print(long_to_bytes(i).decode(),end='')
# flag{Quaternion_15_ComComComComplexXXX!!!?}
choice
题目：
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函数是啥
def choice(self, seq):
"""Choose a random element from a non-empty sequence."""
# As an accommodation for NumPy, we don't use "if not seq"
# because bool(numpy.array()) raises a ValueError.
if not len(seq):
raise IndexError('Cannot choose from an empty sequence')
return seq[self._randbelow(len(seq))]
问gpt知道
知道是生成八位的随机数，那就是简单的随机数预测了，不多说了
prng_xxxx(未解决)
题目：
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<'