强网杯2025
CRYPTO
check-little
e很小,开始还以为是小e,使用维纳攻击发现找不到d。分析现有数据,突然发现n和c有公因子=>p或者q
from Crypto.Util.number import *
from Crypto.Cipher import AES
n = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
e = 3
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
p = GCD(n,c)
q = n // p
key = long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n))
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = 'bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2'
print(AES.new(key = key[:16], iv = iv, mode = AES.MODE_CBC).decrypt(ciphertext = bytes.fromhex(ciphertext)))
# b'flag{m_m4y_6e_divIS1b1e_by_p?!}\x01'ezran
方法一
类似:
https://tangcuxiaojikuai.xyz/post/69eaef2e.html
https://github.com/Cat-Training-Force/CatCTF-2024/blob/main/Crypto/Random%20game/README.md
改下参数发现出不来,查看解空间维度有30多维。把现有的解空间基向量加上解出的特解尝试构造合适的解:
from Crypto.Util.number import *
from itertools import product
from random import *
from tqdm import *
gift0 =
c = ")9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u"
gift = long_to_bytes(gift0)
gift = [int.from_bytes(gift[i:i+2]) for i in range(0, len(gift), 2)]
RNG = Random()
def construct_a_row(RNG):
row = []
for i in range(len(gift)):
RNG.getrandbits(8)
row += list(map(int, (bin(RNG.getrandbits(16) >> 8)[2:].zfill(8))))
return row
L = []
k = 19968
for i in trange(k):
state = [0]*624
temp = "0"*i + "1"*1 + "0"*(k-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)
R = []
for i in range(len(gift)):
R += list(map(int, (bin(gift[i] >> 8)[2:].zfill(8))))
R = vector(GF(2),R)
s0 = L.solve_left(R)
t = L.left_kernel().basis()
l = len(t)
ss = product([0,1], repeat=l)
k = 0
for s in ss:
k+=1
s_tmp = s0
for i in range(l):
s_tmp+=t[i]*s[i]
init = "".join(list(map(str,s_tmp)))
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(3108):
RNG1.getrandbits(8)
RNG1.getrandbits(16)
x = [i for i in range(len(c))]
for i in range(2025):
RNG1.shuffle(x)
flag = ""
for i in range(len(c)):
flag += c[x.index(i)]
print(flag)
if 'flag{' in flag:
print(k)
break
# flag{7hE_numbEr_0f_biT5_i5_Enou9h_@L5o_ThE_r4nk_must_3n0ugh}(some_noise_to_make_sure_you_get_it)方法二
使用gf2bv解决:https://github.com/maple3142/gf2bv
from gf2bv.crypto.mt import MT19937
from gf2bv import LinearSystem
c = ")9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u"
# 从gift中提取出状态,gift[i]为16位数字
gift = [26511, 54008, 13307, 8478, 2141, 61223...]
def mt19937(out):
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = []
for i in range(len(gift)):
rng.getrandbits(8)
tmp = rng.getrandbits(16) >> 8
zeros.append(tmp^out[i])
zeros.append(mt[0] ^ 0x80000000)
return lin.solve_all(zeros)
out = [gift[i]>>8 for i in range(len(gift))]
statu = mt19937(out)
for s in statu:
RNG0 = MT19937(s)
RNG = RNG0.to_python_random()
for _ in range(3108):
RNG.getrandbits(8)
RNG.getrandbits(16)
x = [i for i in range(len(c))]
for i in range(2025):
RNG.shuffle(x)
flag = ""
for i in range(len(c)):
flag += c[x.index(i)]
if 'flag{' in flag:
print(flag)
break
# flag{7hE_numbEr_0f_biT5_i5_Enou9h_@L5o_ThE_r4nk_must_3n0ugh}(some_noise_to_make_sure_you_get_it)Blurred
fi∗hi=gimod(xn+1),x+是xn+的一个因子,则有fi′∗hi′=gi′mod(x+1)成立
构造格L100h1′p0h2′0p,存在格点A(f,k1,k2),能够使得AL=(f,g1′,g2)并且∣AL∣=f2+g1′2+g2′2<3∗(p2)1/3,故通过LLL算法可以得到AL。
此时AL中均为小量,其绝对值之和不大,但是随机生成的h没有这个特征,可以据此判断得到coin的序列,然后利用MT19937得到AES的key
#part 1
from sage.all import *
from pwn import *
from tqdm import trange
q = 1342261
n = 1031
PR = PolynomialRing(GF(q), "x")
x = PR.gens()[0]
io = remote("127.0.0.1", 1337)
tmp = ''
for _ in trange(19968):
io.recvuntil(b"c : ")
io.sendline(b"1")
io.recvuntil(b"Hints: ")
res = io.recvline().decode().strip().split("] [")
h1 = eval(res[0] + "]")
h2 = eval("[" + res[1])
h1_ = GF(q)(PR(h1)%(x+1))
h2_ = GF(q)(PR(h2)%(x+1))
L = Matrix(ZZ, [
[1, h1_, h2_],
[0, q, 0],
[0, 0, q]
])
L = L.LLL()
res = L[0]
if(res.norm() < 100):
tmp+='0'
else:
tmp+='1'
print(tmp,file=open("tmp.txt","a"))
io.recvuntil(b"c :")
io.sendline(b"2")
print(io.recvline(),file=open("tmp.txt","a"))
io.close()# part 2 (此处序列和flag为复现时自行构造)
tmp = '010011110110110011001100110101000110101011000101000100101011101011000001001101100000101011111000111110100101001100001001011101000110001001111100000001100101111111010110001000111001010000000001101101001001111110011100100000101101111100000100001010100011000001011110011000110110000001011100000101011010111000011110001011100111101000110111111110010011010011110100100001011111010110010101101110011010001001001001001001010101101000100010011011101001111011011111110001000111111111110000011101100101101011011010101010011001100101110011110101100001100000010111001101111001010010110100011010100101010010111001010110101000101110100111100110011110111000000001010111110110001010111100001010111010000001101110111011111001001100101010000011110011001101101001001011100101110111011110101100000001110110100110000011110011000100011011100110111101010110100101110101010010100000101010011100110100110111111000011101100011101111000100100000000101100101101011111001101100001000101010101000011010110110000100101001010001001101000000010000010001010000100100100100111101010101101100100100110001000010000110000101111011101010010101100100000000100101001100000111000100011101110010101111111011011001100111100010101110011000010001100010011110111000001011101001100111100001101001110110110110101100101000001100100101110110010110001000000101001111000001110101110001010010001001011100000111100000111010000011110111000100001010001110110000001101001001010011010101001101000100000011001011001001101100010101111100111100000011001011001111001000110000101001110110111000111001011010001010001110010011010110110100000110001011000101000100001100000010100101000110001110000000011001111000000100110011001111000110001101110110011100001001011111010100010101100111111001000110100101000110001110000010111011110010100111111000010111100010101100111011100111010101110001110011001110000000101000101011011011101101010110010110101111010001010101100001011010110110110110010011111110100010111100000001110000000101110110011111101010010011100000011000111101011101100110111111010100001000101001010100101111100010000011001110001000011001000001000010100101110011001100001111100111100100100111010110100001001101011100101000101101110011010001010100000001101100000110111010001111110001111001010011101101110110110010001111101011001100010111000110110111011111000001101101011000110110110101010101100101001110100111000011001100010011011000000011100111101111110111000111010101001010100000011100110110000000100101100010001101010010101011000101010011010100100000011111010001101000001110001000111101001011000100110101001010110101101010000000110110110001110011111101111000010001011100000110011111000010011110000001010011100110000010010110100100111011100110001101100011011000101101100111100011111010100000110000101110111010111111001101011001000000001110101101000110111000100110101011001110000010110000001011000101001110111010000011111011000011110101010011100110100010111011011100010000101010111000001110101001100011000001110101100010111111000110101100000101100100110010000100001000000010111111110100101101101001000110101000101000111011010011110100111001010110000001100110001110101101101011010010111011110000010000111111101110110111000110001111111010101011111111011101000011110100101100111101100000011111100111001010111010011011011000010110110001100100001101111111000001001111100101110110010001101001010010011011001111010000010100001101000111100001111101111001000010110010110001111100110011111110111100001110001000100111111010111000110101000101010111110101111010010111101000001010101001000110000000001000011111001101000101001111010101100000111010001110111111011001010101001110000011010010111111100001001100000000010111010101110101110010110000010110011000000101001000110010000011100010100010110000100011111101010011011101011010000110001000111001110111111010100010000001110010001000001111000011111110010100110011000011001100010110000111010010011011010011101101101000010100101111001001101100111010111110100110100001110000111101101010000111101111001100101111001001100111100000010110011110111110111001010101101111111001001010111111010110001111011000001011111010010100011100111111001010001000000110000001011000110000011110100110001110000001000100001101000101010010111000001010010101010001100011011111101101001101101011111100100010111000000100011001101010101101110100001111110101101010000001111110010011100010001101110110000110101100000010011110000010011100000010011100000001000011100100000101100101001100001101001111110111000110110111111101010010001011000010011010110111010111011100011010100100110010010010110100000100001001111000010110100010110000000101010000100011011111101011000100001010111001100101101101101010100101000001110111111001011101001011010011101101100100001100101100100000010011110011010110111100010001101000101000000011011010000000100011100011101100101010011101010000110100000001111100010101000011110000000110010001000100110000100101110100110010110000101101010010000011111011000000010110100001100111100011011011010111001100100010001111011000010000110010010110111110010000110011000011000010111010011111010111100111011010011000110111000010010011011110011011000111000000001010111010110100110011011001000101011001010100010010101010101100100100101010100110110001001110010011110111100000011011100100111101110101101100010011010100110110001000111001011100100000110111000011011100111001011001101101011100010110011001101010101011101101101011110101111101111011111001010101100101010101001000111011000100000000100111000110111010000010100010010110001001011011000001001010110111000100101111001010101100010100001011111000000001111110001100110111111110111000011010100011011000001100010011011110101000100100000011001111111100100010000001100110110100001100011101001111111101000111101111010010000110010111111101111110111000110000101101110011110100000011011011000001111101101001000001101101110000111000111101000111110100100000111101111011101101111110111111011100010001101000010010100001001111110111111110010110000010011011101111011111110100010110110000001010011000101110010111100100111011011000101000000111101000100010010100011101111110011101000111110110010111111000110000011101001100001110011111111011111000110100011101100110110100010001000000111100000100110001011110111110101111000001110001100111011110001111011110110111000110000101100101010011100110100010011101001000111111000101110110100100101001000111000101011101100110011010000110101110101111001010110011001111100101011010111010001110011011100100001000000110010100001011100110010100000011011011100100010001100111011100001101011010111011000100000010110100110100001110010001011011111001000000001000100001001010000100101001000110111100110011011011001010000100010110011101111001100000110111001010100011111000000010101001111001000011001010011000011000010011101001100001100010111101111010011011111011101000101110000100101000101000111010011010010101001001001001111001100101000100001011111000011010110101001011100110001010000101110000010110000000110111000111110111110010010010001010110101110011101011011100011011011101111100100010010010010110010011001000011100101111001000101011001000001000110011100111100100101110110110001001011011010001001000101100110001010111001001101101010101100101101101011000010011100111011010101110010001011101111110000101100110111011001111010111010111110001001100001010000001011111011101000000000100000001000001101010111011011111110011100101000010101101001100101111110001110000011111001111000110011101101101010110000110111101100000101001011011011010111010111011110001111111111010100101010001010010101011100101000010011001011000101110101010101010111010101110011110001101110011100001111001001111110000000111111010111100000011000011101111010111110100001011010110111101100110011001100111100001001110001101101100110010011100011001010000001110010101011100111000101000110110010001001100111010110000101010110101110001111001100110001101011100000000100111010100101110010000011111111110010000010000011100001101001010110110101100000100110110011011010011011011010010111110101100110010000111111000001010011111011111101111011010111110011011000000010111100101110011111000010110110000011001000101100001111101100001010000100100001001101010010110101001111000110000010010001100100111110010101010000011100101100011111110010111011110110111111100010001110100100111101001010111010011110000111110100010010101010010011110100100101111011110100001000010001110100001110111010111000010001100000000101110001100010000001111011000001000101111001101101111001110000110010010101001100011111010010110110010001010111011011010010110010001001001111011011100110001001010011001010011110110101100101101000111110110010000110101001101011111010011000101001110110101001010101000111101010011111100100000111010100100100010011001111010110000100011100010100001111100001101101000001000110100010101000110001001000000000000000000101101000010010010111011001001000010100111011011011011100100011100011111110101111100100001111000011101101001100111111010010110011010001010000110111100010100000010000101111011101110000110111101110011010001111111011011011110100111111000001000110001010111000000011000001111000110010010001111001011010000111011111110100001100101000100110011110101111001001111101011011110111011110010011100000000011101011001110011101001110000000101000110111010100001101100110100000111110010001101000111000100010000111101010111111000001000110000111111110110100011001100001011101111001101110100011011011111100100010100011100100110001100011111001000000100110110111000110110101101000101100111100110100000111010001001011011110011000001110001111010111101111011000011011100111011010100010110000110010010010111101110011000000000111101000011101011101010010001000010010110001111010000010010110100011100010100001001010011110100001111111010001011101110111101111011111100111111111111110110001001110001010001110010100111001011111001010111011001010101010100110110010000010111001110011100111100010100111111010001111010101010011100101101011011011010000011100010101010000010100101100010010000101011000100010111111100111100010010111100101111110011101011111100100110001001110000101101000000110000101001000001101001110000111101010110011101100100100110001010010010111001101010010100011011000001100010110011010100100011101111010111010000001011111110010011101010111000101111111011101001000100101111101001101110110001011000101011000100011001001101110010000010000110111110010010000100010100110000110010011111010001110010111010100010000010011011110101111101011000111101111111001101001101111111000111011010000111101010100010011000101111010111110000111100011011101001110010110110011111011111101110111101111100101011111101001010000101101110110111100011010010001101000101011110111111011011101100001001011101010010001011011110101000101100011110100110001111011111110100011000001001000100101100011000011111111000000101001111011001111100010011010110000111011110011111011001010000010100010100101001011111001111000100110010100010101110001000011001100010111110010011101001011111111000110100001000011101110101000111011101001111000000010111010101110111110111000111110110101100010100111010000010101001011111100000111011100100110111011011111111000001100110001110110000010100100010111001011111111011110110000110010000001001011010010011101010111011000000010111111111001000100001110011100100111001001010010011011101101110101010100011011010010011101010000101001011111011001110000100001001100111010111001001001110110000101111001100100110101100001100011011101000100000010010010111100011110011110000101110001110100111110010010101101000110001111111100101110010101001001000010110000001100011001011101001000101010000010100100011111010111011011101110000011101010100010000000000100110001001000010001101010001010010110001101110010101111010010001111100101111001010111001001100110010100001100011010001010001010100011011101101100000110111001111100111011110001110001100111001010111110000010101111000101011010111000000000100001111100010010011001010011001111010111111111110100100011101100101011100000100000000010011110000100000011011011011100001010000010010011111111001110000010010100101110110110010011100110110111111010111010110100011110010001000110000101010100000000101000100011000100000101001001010100000110101011000111000000010100100101100011000010010100100100000100100010010001111100101111010100010110001100110100000101001111011111110101011100011100010010100110000011110110011001000101110001111110010111101001101010010110111101000100011001001011110011111100001001000001010010001000000110111100010100111001110001111101110010111010111111101111111101111000100101010100011000011001100011011101010001101001000000000110101001111111000110101111100100001001011011010111010110011100000011111101001010010100110110010010101011110010001110010101000010100111111010101101101111110101111011101001000010000100000001010000010001010011110010011011000000010110100010110111111101110010100010100010010101010000011111100101011111101011010111101111010100010110100100101110001011000011111001000101100000011100101111010011011100001011011001010010000100111010100100010001110110101011101011100011111111011101101111011011111101101010100011111010011011111100110010101000111001100010011010011100001101111011001010010100011100111000000110100100110001101100101001011001000000000001010100001010111101000001110011011111011000110100011110111100010111001110011101010100100000001000011011001001101101000001101111001101110101111110010000011111110100110001010101011101010100100011111101011011110010101001111111011000001100001011010001100110110010100001001100010000111000000010100000100010001111101001001100111111111001111110010110100101000011010110101010111100100100110100101101110010100111010001100001101100010110111010111000101100111011110101110000001110100101101101101100000111101001110011111000111101100010010100101001100111010111000101010001101111110001111000011001010110000010111011011010101101001110101001100101110100000111000001000011011100000011111010001101111001001011100000110100100101011111011000001010011111011100110110010010011001110001000000001010011101111110011110000100010100010011100110111111010111011011110100101100010010000111011110001111111001111001011100100000111101100111110111010111011011001011000111100000111000111010011000110100011011111101110001100111110010100111010100111001000010000000000011111011010001100110001000111011100000100011010010111110011100111100101110001110001111100010110100111001111100000011110101000110101000110111001011100101101111110001100000011010100011010010011010101000110100110110101011000010001010111001110110000101011011110101110011000010001001110001011010100110010100101010001110000111110010010110001100101100001000010000001011011010001011010110001100101010110001110100011101010100010110011111010010000001010010101001010011100010101100000000100100000001000011110101101001010011010011110011110000011000011111100010110111100000110011110000010111011010111101010001101000100011100101000100111010111011111000110101001101001100111101100101110001000001100011110000110010110100010011101100111001110110000011100000001011001101011101110111100101000100001000010110001010101101100111100000100100010011000011110010011110010011011101101000010011100110011011101000010000011110011100000111111001100010011110110110001110110010101001100001110100010000101101001010010000110111001010001110110100011001100111001001111000000101100101010010000011000101111100011101110101100010111010111101010000100000001110001111111001111010100001000000101001110010011100011110101101000100110010010101110000110011011011001100010001000011011100100010100101010011101110101111100010100001001110011011000101100001001011001110000011101111111110000100001010010010101000110101010000011110011001011010001011110111111111100000111111010010110100011010111010000101010101100110110101011010111100100111110101101001011000001010011111100010110101111110111011100011111101101011111111101011000110100100111010110100011110011101000011000111111110001011011011001100111110101000111101111011001110010100110001011001000001010001101111101100001111001111110010001010010110010100011000100000101000001101111101001110011011110101101001001110110101110110011010000110011111100101001101010000111111000110000110101100100000100101111111001001001110111011111000100101000111111011001000000110110100101010001100101111110011010011100100110000000110010111010101000101101000101100111111010010101010100101000000100111111101000001100010110111110111110001010100111011111111011101001011010000100101110100000110000111001011111101011010110001111111101000110010110010101000000000001010111010110010110011001110010100101000011000011111001100101001110011000011001010100010000110000101110001011101100110100111001001010000000100110000000001100000111110111001011110011100011111010110100011011010011001100110011101110010001000001011010000100101011111110011010000000001010111110111100010011010010111111110111010000110010000001010111001110111100111110001110000001111111101101010000010001010101010101010100110100000100011000000100111010101110111111010110010001010100001001111010000000001010010011011010000000100111110000100010100010011011111010100111001110100010010001011101101101100011110000001101101011001110001011011001111011000011001010110101011010110010000000010110110100000101101010101101000011010110001101110101111111101111110110011001110111101001001001000011111000110011110000001010110110011101001010000011010001011100111101000010001101010010010101110001000001001001110101110110011010111001011111111101011010001010111101000110010111110000011001011100111010110110101101101000110010010000110101000011100001011101101101010010111000001001100110100101001100010010110001111000100001111100100001000111111011100100101011000101111011010011011000000010110010100101010100111111010000010001010001101000111111001011110001100100010000001110110001100010000000100100101110000011001001001000011101110001101001011000101110000110001111111110110010000000101101010011101001110111010111000010111100110101011111100111001001001111011011010001011110001101101110110101000000010000100110000010100001001001110010110100100110011111101010011010001000000100110100110000111101101100111011011000001010110111000010101010001100111101100110100110010101111100000100010010111010110010100110000011011100100111000101110101001011010010001110000101001101101000111100110100010011110011101010000011001010001001000100010110011001100110100100101010011101100011011111001000001111111111100110101000110100111110100001101100100111001000011110011011110111111110111101000111010001010011111100001100011011110010010101100100101010111001001101111010011001101000101100011111011011001111110111111011111100010000011000101001011010110011011100110000011011110101010000110010110100110010111000100010000000111111000100101011101001110011010111011110110010100101110011001010011010111011001001010100010111011010011011110010010111111100110010000000111111011010011100011011111100111100110010101000010111000010010010010000101000111001110010011110010111111010110000000000001101010000100010101000010010110110100011111100111011001001010110001000111111110110010111010000100010010011100111110110110000001101000010111000111100001111100000001011010100110001011011110001101101110010111010110101101001001111011001010000010110000001110000100000000010001100111100010000000010100000001100000101111100010000000010110011101001010101001001000000101001000111101000010010001110000100110010001011111111101011001111011001011010000110000100010010010101101010011100110001011111000010001100000101100011111011110010110011101001010110000111110110011110010011001110110011110011111011011010110111100101111110000011111010100011011111100001111001110010011010011010110101000011011100000111001101010001100001010000111110001110101000111101100111111100010001111000000110010011111110010011010011000011011000100100010001101111001110110010110101110011111101000100001110011101100111111001101111000100000010011010110100111101101110111011111010001110011001110011000001111011110010111110111101101111101000001010101111010101001100101001101110110001001000111011001010010010111011110000111111001011011101011010010010000111100111100011011000110000010000011010000010100011'
enc = b'\n&\xb6\x92\xc7\x00\xef\x91\xf8\x9c\x0f\xa7\x82\x954L\xf7Zt\xb1\x8d\xe3l\xd07\x82J]\xb1\xd9\xca\x9e$\x92\xea\xe6$\xe2\xc8@\x86O\xa5\xf7\x86\x88\xa9\xfb'
from gf2bv.crypto.mt import MT19937
from gf2bv import LinearSystem
def mt19937(out):
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = [rng.getrandbits(1) ^ o for o in out]
return lin.solve_one(zeros)
out = [int(i) for i in tmp]
statu = mt19937(out)
RNG = MT19937(statu)
for _ in range(19968): RNG.getrandbits(1)
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
SHA = SHA256.new()
SHA.update(str(RNG.getrandbits(256)).encode())
KEY = SHA.digest()
cipher = AES.new(KEY, AES.MODE_ECB)
print("Flag:", cipher.decrypt(enc))
# Flag: b'flag{04a675fc-5e61-44bd-8a02-65f734369bbb}\x06\x06\x06\x06\x06\x06'