check-little
题唔系噉出㗎大佬……
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os
flag, key = open('secret').read().split('\n')
e = 3
while 1:
p = getPrime(1024)
q = getPrime(1024)
phi = (p - 1) * (q - 1)
if phi % e != 0:
break
N = p * q
c = pow(key, e, N)
iv = os.urandom(16)
ciphertext = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).encrypt(pad(flag.encode(),16)).hex()
f = open('output.txt', 'w')
f.write(f'N = {N}\n')
f.write(f'c = {c}\n')
f.write(f'iv = {iv}\n')
f.write(f'ciphertext = {ciphertext}\n')一眼小公钥RSA，尝试开根没有办法得到\(key\)，后来注意到加密用的是\(key\)的高16字节（即高128位），所以在想是否可能只恢复高128位，但是也没找到方法，后面拿已知数据逐个和\(N\)求gcd，发现\(c\)居然和\(N\)不互质，那搞到的应该就是\(N\)的一个质因数了，直接解RSA就能得到\(key\)，从而恢复flag：
from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import iroot, gcd
N = ...
c = ...
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ct = bytes.fromhex("bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2")
e = 3
p = gcd(N, c)
q = N // p
phi = (p - 1) * (q - 1)
d = inverse(3, phi)
key = pow(c, d, N)
print(AES.new(long_to_bytes(key)[:16], AES.MODE_CBC, iv).decrypt(ct))总之就是很无语……
ezran
from Crypto.Util.number import *
from random import *
f = open('flag.txt', 'r')
flag = f.read().encode()
gift=b''
for i in range(3108):
r1 = getrandbits(8)
r2 = getrandbits(16)
x=(pow(r1, 2*i, 257) & 0xff) ^ r2
c=long_to_bytes(x, 2)
gift+=c
m = list(flag)
for i in range(2025):
shuffle(m)
c = "".join(list(map(chr,m)))
f = open('output.txt', 'w')
f.write(f"gift = {bytes_to_long(gift)}\n")
f.write(f"c = {c}\n")可以看到题目首先生成了3108组数据，分别记为\(r_{i,1},r_{i,2}\)（其中\(0\le i<3108\)），有：
$$
x_i=[(r_{i,1}^{2i}\mod{257})\&255]\oplus r_{i,2}
$$
因为\(r_{i,2}\)为16-bit整数，而\([(r_{i,1}^{2i}\mod{257})\&255]\)很明显为8-bit整数，所以可以知道\(x_{i}\)的高8位肯定是\(r_{i,2}\)的高8位，所以我们其实可以确定\(3108\times8=24864\)位，远远大于\(19968\)位，那么理论上我们是可以恢复出MT19937的状态的，所以可以通过gf2bv写出如下求解代码：
from Crypto.Util.number import *
from gf2bv import *
from gf2bv.crypto.mt import *
from tqdm import *
import sys
sys.set_int_max_str_digits(10000000)
gift = "..."
gift = int(gift)
c = ")9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u"
giftstr = long_to_bytes(gift)
s = [giftstr[i: i+2] for i in range(0, len(giftstr), 2)]
LS = LinearSystem([32] * 624)
mt = LS.gens()
RNG = MT19937(mt)
tmp = []
for x in s:
RNG.getrandbits(8)
tmp.append((RNG.getrandbits(16) >> 8) ^ x[0])
tmp.append(mt[0] ^ 0x80000000)
sols = LS.solve_all(tmp)
for sol in sols:
rng = MT19937(sol).to_python_random()
try:
for i in range(3108):
r1 = rng.getrandbits(8)
r2 = rng.getrandbits(16)
assert (pow(r1, 2*i, 257) & 0xff) ^ r2 == bytes_to_long(s[i])
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)]
print(flag)
break
except:
pass可以求解出flag：flag{7hE_numbEr_0f_biT5_i5_Enou9h_@L5o_ThE_r4nk_must_3n0ugh}
当然，根据类似同济大学第二届网络安全新生赛CatCTF的Random game一题的分析方法可以获得更多已知位，这里不过多赘述.
sk（赛后复现）
很遗憾比赛的时候没做出来
复现docker镜像：triodelzx0916/qwb2025sk
from random import randint
from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
from math import gcd
import signal
from secret import flag
def gen_coprime_num(pbits):
lbits = 2 * pbits + 8
lb = 2**lbits
ub = 2**(lbits + 1)
while True:
r = randint(lb, ub)
s = randint(lb, ub)
if gcd(r, s) == 1:
return r, s
def mult_mod(A, B, p):
result = [0] * (len(A) + len(B) - 1)
for i in range(len(A)):
for j in range(len(B)):
result[i + j] = (result[i + j] + A[i] * B[j]) % p
return result
def gen_key(p):
f = [randint(1, 2**128) for i in ":)"]
h = [randint(1, 2**128) for i in ":("]
R1, S1 = gen_coprime_num(p.bit_length())
R2, S2 = gen_coprime_num(p.bit_length())
B = [[randint(1, p - 1) for i in ":("] for j in ":)"]
P = []
for b in B:
P.append(mult_mod(f, b, p))
Q = []
for b in B:
Q.append(mult_mod(h, b, p))
for i in range(len(P)):
for j in range(len(P[i])):
P[i][j] = P[i][j] * R1 % S1
Q[i][j] = Q[i][j] * R2 % S2
sk = [(R1, S1), (R2, S2), f, h, p]
pk = [P, Q, p]
return sk, pk
def encrypt(pk, pt):
P, Q, p = pk
pt = bytes_to_long(pt)
PP = 0
QQ = 0
for i in range(len(P)):
u = randint(1, p)
for j in range(len(P[0])):
PP = PP + P[i][j] * (u * pt**j % p)
QQ = QQ + Q[i][j] * (u * pt**j % p)
return PP, QQ
def decrypt(sk, ct):
RS1, RS2, f, h, p = sk
R1, S1 = RS1
R2, S2 = RS2
P, Q = ct
invR1 = inverse(R1, S1)
invR2 = inverse(R2, S2)
P = (P * invR1 % S1) % p
Q = (Q * invR2 % S2) % p
f0q = f[0] * Q % p
f1q = f[1] * Q % p
h0p = h[0] * P % p
h1p = h[1] * P % p
a = f1q + p - h1p % p
b = f0q + p - h0p % p
pt = -b * inverse(a, p) % p
pt = long_to_bytes(pt)
return pt
signal.alarm(30)
p = getPrime(256)
sk, pk = gen_key(p)
ticket = long_to_bytes(randint(1, p))
enc_ticket = encrypt(pk, ticket)
print(pk)
print(enc_ticket)
for i in range(2):
op = int(input("op>").strip())
if op == 1:
msg = input("pt:").strip().encode()
ct = encrypt(pk, msg)
print(f"ct: {ct}")
elif op == 2:
user_input = input("ct:").strip().split(" ")
if len(user_input) == 2:
ct = [int(user_input[0]), int(user_input[1])]
else:
print("invalid ct.")
break
user_input = input("your f:").strip().split(" ")
if len(user_input) == 2:
user_f = [int(user_input[0]), int(user_input[1])]
else:
print("invalid f.")
break
user_input = input("your h:").strip().split(" ")
if len(user_input) == 2:
user_h = [int(user_input[0]), int(user_input[1])]
else:
print("invalid h.")
break
user_input = input("your R1 S1:").strip().split(" ")
if len(user_input) == 2:
user_r1s1 = [int(user_input[0]), int(user_input[1])]
else:
print("invalid R1 S1.")
break
user_input = input("your R2 S2:").strip().split(" ")
if len(user_input) == 2:
user_r2s2 = [int(user_input[0]), int(user_input[1])]
else:
print("invalid R2 S2.")
break
pt = decrypt((user_r1s1, user_r2s2, user_f, user_h, p), ct)
if pt == ticket:
print(flag)
else:
print(pt.hex())
else:
print("invalid op.")
break
print("bye!")因为给我们的只有公钥\(P,Q,p\)，我们跟踪一下密钥生成的步骤：
def mult_mod(A, B):
result = [0] * (len(A) + len(B) - 1)
for i in range(len(A)):
for j in range(len(B)):
result[i + j] = (result[i + j] + A[i] * B[j])
return result
f = [var(f'f{i}') for i in range(2)]
h = [var(f'h{i}') for i in range(2)]
R1, S1 = var('R1 S1')
R2, S2 = var('R2 S2')
B = [[var(f'B{i}{j}') for j in range(2)] for i in range(2)]
pt = var('pt')
u = var('u')
P = []
for b in B:
P.append(mult_mod(f, b))
Q = []
for b in B:
Q.append(mult_mod(h, b))
print(P)
print(Q)可以得到在还未乘上\(R_1,R_2\)的时候有：
P = [[B00*f0, B01*f0 + B00*f1, B01*f1], [B10*f0, B11*f0 + B10*f1, B11*f1]]
Q = [[B00*h0, B01*h0 + B00*h1, B01*h1], [B10*h0, B11*h0 + B10*h1, B11*h1]]因为\(R_1,S_1,R_2,S_2\)未知，所以我们只知道\(P,Q\)最终是一个\(2\times3\)的矩阵（其实看输出也能看出来），再通过如下代码跟踪加密函数：
P = [[var(f"P{i}{j}") for j in range(3)] for i in range(2)]
Q = [[var(f"Q{i}{j}") for j in range(3)] for i in range(2)]
pt = var("pt")
u = var("u")
PP = 0
QQ = 0
for i in range(len(P)):
# u = randint(1, p)
for j in range(len(P[0])):
PP = PP + P[i][j] * (u * pt**j)
QQ = QQ + Q[i][j] * (u * pt**j)
print(PP)
print(QQ)可以得到：
PP = P02*pt^2*u0 + P12*pt^2*u1 + P01*pt*u0 + P11*pt*u1 + P00*u0 + P10*u1
QQ = Q02*pt^2*u0 + Q12*pt^2*u1 + Q01*pt*u0 + Q11*pt*u1 + Q00*u0 + Q10*u1按原代码整理可得：
$$
\begin{aligned}
PP&=P_{02}\cdot (pt^2\cdot u_0\mod{p})+P_{12}\cdot (pt^2\cdot u_1 \mod{p})+P_{01}\cdot (pt\cdot u_0\mod{p})+P_{11} \cdot (pt \cdot u_1\mod{p}) + P_{00} \cdot (u_0\mod{p})+P_{10}\cdot (u_1\mod{p})\\
QQ&=Q_{02}\cdot (pt^2\cdot u_0\mod{p})+Q_{12}\cdot (pt^2\cdot u_1 \mod{p})+Q_{01}\cdot (pt\cdot u_0\mod{p})+Q_{11} \cdot (pt \cdot u_1\mod{p}) + Q_{00} \cdot (u_0\mod{p})+Q_{10}\cdot (u_1\mod{p})
\end{aligned}
$$
很显然存在线性关系，可以构造如下方程组：
$$
\begin{aligned}
PP&=P_{02}x_{02}+P_{12}x_{12}+P_{01}x_{01}+P_{11}x_{11}+P_{00}x_{00}+P_{10}x_{10}\\
QQ&=Q_{02}x_{02}+Q_{12}x_{12}+Q_{01}x_{01}+Q_{11}x_{11}+Q_{00}x_{00}+Q_{10}x_{10}
\end{aligned}
$$
预期有\(x_{ij}=u_{i}pt^{j}\mod{p}\)，尝试构造数据用cuso求解：
from random import *
from Crypto.Util.number import *
from math import *
from sage.all import *
import cuso
def gen_coprime_num(pbits):
lbits = 2 * pbits + 8
lb = 2 ** lbits
ub = 2 ** (lbits + 1)
while True:
r = randint(lb, ub)
s = randint(lb, ub)
if gcd(r, s) == 1:
return r, s
def mult_mod(A, B, p):
result = [0] * (len(A) + len(B) - 1)
for i in range(len(A)):
for j in range(len(B)):
result[i + j] = (result[i + j] + A[i] * B[j]) % p
return result
def gen_key(p):
f = [randint(1, 2 ** 128) for i in ":)"]
h = [randint(1, 2 ** 128) for i in ":("]
R1, S1 = gen_coprime_num(p.bit_length())
R2, S2 = gen_coprime_num(p.bit_length())
B = [[randint(1, p - 1) for i in ":("] for j in ":)"]
P = []
for b in B:
P.append(mult_mod(f, b, p))
Q = []
for b in B:
Q.append(mult_mod(h, b, p))
for i in range(len(P)):
for j in range(len(P[i])):
P[i][j] = P[i][j] * R1 % S1
Q[i][j] = Q[i][j] * R2 % S2
sk = [(R1, S1), (R2, S2), f, h, p]
pk = [P, Q, p]
return sk, pk
def encrypt(pk, pt):
P, Q, p = pk
pt = bytes_to_long(pt)
PP = 0
QQ = 0
for i in range(len(P)):
u = randint(1, p)
for j in range(len(P[0])):
PP = PP + P[i][j] * (u * pt ** j % p)
QQ = QQ + Q[i][j] * (u * pt ** j % p)
return PP, QQ
def decrypt(sk, ct):
RS1, RS2, f, h, p = sk
R1, S1 = RS1
R2, S2 = RS2
P, Q = ct
invR1 = inverse(R1, S1)
invR2 = inverse(R2, S2)
P = (P * invR1 % S1) % p
Q = (Q * invR2 % S2) % p
f0q = f[0] * Q % p
f1q = f[1] * Q % p
h0p = h[0] * P % p
h1p = h[1] * P % p
a = f1q + p - h1p % p
b = f0q + p - h0p % p
pt = -b * inverse(a, p) % p
pt = long_to_bytes(pt)
return pt
p = getPrime(256)
sk, pk = gen_key(p)
ticket = long_to_bytes(randint(1, p))
enc_ticket = encrypt(pk, ticket)
x = [[var(f"x{i}{j}") for j in range(3)] for i in range(2)]
PP, QQ = enc_ticket
P, Q, p = pk
f1 = sum([P[i][j] * x[i][j] for i in range(2) for j in range(3)]) - PP
f2 = sum([Q[i][j] * x[i][j] for i in range(2) for j in range(3)]) - QQ
relations = [f1, f2]
bounds = {x[i][j]: (0, p - 1) for i in range(2) for j in range(3)}
roots = cuso.find_small_roots(relations, bounds)
# print(roots)
for root in roots:
u0 = root[x[0][0]]
pt_u0 = root[x[0][1]]
u1 = root[x[1][0]]
pt_u1 = root[x[1][1]]
pt0 = long_to_bytes(pt_u0 * inverse(u0, p) % p)
pt1 = long_to_bytes(pt_u1 * inverse(u1, p) % p)
if pt0 == pt1:
pt = pt0
print(pt == ticket)
break多次运行发现确实可以解出明文，那么我们可以在获得明文之后自己构造密钥对对明文进行加密，再将密文和自己构造的私钥扔回靶机就可以了：
from random import *
from Crypto.Util.number import *
from math import *
from sage.all import *
import cuso
from pwn import *
io = remote("127.0.0.1", 1145)
def gen_coprime_num(pbits):
lbits = 2 * pbits + 8
lb = 2 ** lbits
ub = 2 ** (lbits + 1)
while True:
r = randint(lb, ub)
s = randint(lb, ub)
if gcd(r, s) == 1:
return r, s
def mult_mod(A, B, p):
result = [0] * (len(A) + len(B) - 1)
for i in range(len(A)):
for j in range(len(B)):
result[i + j] = (result[i + j] + A[i] * B[j]) % p
return result
def gen_key(p):
f = [randint(1, 2 ** 128) for i in ":)"]
h = [randint(1, 2 ** 128) for i in ":("]
R1, S1 = gen_coprime_num(p.bit_length())
R2, S2 = gen_coprime_num(p.bit_length())
B = [[randint(1, p - 1) for i in ":("] for j in ":)"]
P = []
for b in B:
P.append(mult_mod(f, b, p))
Q = []
for b in B:
Q.append(mult_mod(h, b, p))
for i in range(len(P)):
for j in range(len(P[i])):
P[i][j] = P[i][j] * R1 % S1
Q[i][j] = Q[i][j] * R2 % S2
sk = [(R1, S1), (R2, S2), f, h, p]
pk = [P, Q, p]
return sk, pk
def encrypt(pk, pt):
P, Q, p = pk
pt = bytes_to_long(pt)
PP = 0
QQ = 0
for i in range(len(P)):
u = randint(1, p)
for j in range(len(P[0])):
PP = PP + P[i][j] * (u * pt ** j % p)
QQ = QQ + Q[i][j] * (u * pt ** j % p)
return PP, QQ
_pk = io.recvline().strip().decode()
pk = eval(_pk)
P, Q, p = pk
_ct = io.recvline().strip().decode()
ct = eval(_ct)
PP, QQ = ct
x = [[var(f"x{i}{j}") for j in range(3)] for i in range(2)]
f1 = sum([P[i][j] * x[i][j] for i in range(2) for j in range(3)]) - PP
f2 = sum([Q[i][j] * x[i][j] for i in range(2) for j in range(3)]) - QQ
relations = [f1, f2]
bounds = {x[i][j]: (0, p - 1) for i in range(2) for j in range(3)}
roots = cuso.find_small_roots(relations, bounds)
for root in roots:
u0 = root[x[0][0]]
pt_u0 = root[x[0][1]]
u1 = root[x[1][0]]
pt_u1 = root[x[1][1]]
pt0 = long_to_bytes(pt_u0 * inverse(u0, p) % p)
pt1 = long_to_bytes(pt_u1 * inverse(u1, p) % p)
if pt0 == pt1:
pt = pt0
break
sk, pk = gen_key(p)
new_ct = encrypt(pk, pt)
io.sendlineafter(b'op>', b"2")
# [(R1, S1), (R2, S2), f, h, p]
io.sendlineafter(b'ct:', f'{new_ct[0]} {new_ct[1]}'.encode())
io.sendlineafter(b'your f:', f'{sk[2][0]} {sk[2][1]}'.encode())
io.sendlineafter(b'your h:', f'{sk[3][0]} {sk[3][1]}'.encode())
io.sendlineafter(b'your R1 S1:', f'{sk[0][0]} {sk[0][1]}'.encode())
io.sendlineafter(b'your R2 S2:', f'{sk[1][0]} {sk[1][1]}'.encode())
io.interactive()可以得到flag（有概率不成功）：
Blurred（赛后复现）
挺好的一道样本区分题
复现docker镜像：triodelzx0916/blurred
from sage.all import *
from sage.misc import prandom
import random
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
flag = b"flag{*****************************}"
def sample(rand):
return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))
def GenNTRU():
f = [sample(prandom) for _ in range(n)]
g1 = [sample(prandom)for _ in range(n)]
g2 = [sample(prandom) for _ in range(n)]
g1x = Q(g1)
g2x = Q(g2)
while True:
fx = Q(f)
try:
h1 = g1x / fx
h2 = g2x / fx
return (h1.lift(), h2.lift(), fx)
except:
prandom.shuffle(f)
continue
for _ in range(20259):
c = int(input("c :"))
if c == 1:
coin = random.getrandbits(1)
if coin == 0:
pk1, pk2, fx = GenNTRU()
else:
pk1, pk2, fx = Q.random_element().lift(), Q.random_element().lift(), Q([sample(prandom) for _ in range(n)])
print("Hints:", pk1.list(), pk2.list())
elif c == 2:
SHA = SHA256.new()
SHA.update(str(random.getrandbits(256)).encode())
KEY = SHA.digest()
cipher = AES.new(KEY, AES.MODE_ECB)
flag = pad(flag, AES.block_size)
print("Flag:", cipher.encrypt(flag))
else:
break有20259次交互机会，对于每次交互，若选择2会通过random.getrandbits生成密钥来加密flag并发出；若选择1，则会通过random.getrandbits生成一个1 bit的随机数作为硬币的值，若硬币值为0则通过GenNTRU生成\(pk_1, pk_2, f_x\)，若硬币值为1则直接生成两个商环\(\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^n+1}\)上的多项式作为\(pk_1,pk_2\)，然后随机生成一个三元多项式\(f_x\)，观察GenNTRU可以看到该函数首先生成了三个随机三元多项式\(g_1,g_2,f_x\)，然后计算\(h_1=g_1/f_x,h_2=g_2/f_x\)，经过处理后分别作为\(pk_1,pk_2\)，很明显这样生成的是NTRU的样本，那么我们的任务就是区分NTRU样本和随机样本，刚开始我的思路就是直接构造NTRU格尝试规约看看是否能规约出\((f_x,g_1)\)，但是这里的\(n=1031\)，太大了，在有限时间内很难规约出目标向量，而且这样我们只能用到生成样本\((pk_1,pk_2)\)中的一个多项式，并不会用到另外一个多项式（如果用到的话计算时间更长了），所以只能想另外一种方法，而我们很容易可以知道对于任意正奇数\(k\) ，有：
$$
x^{k}+1=(x+1)\left[\sum_{i=0}^{k-1}(-1)^{i}x^{i}\right]
$$
因为我们并不需要将\(f_x\)恢复出来，只需要区分出多项式样本是来自GenNTRU还是随机样本，所以我们可以考虑在\(\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x+1}\)上进行区分，我们知道，在\(\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x+1}\)中，有\(x=-1\)，那么必然的，对于\(\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^n+1}\)中的一个多项式\(f\)，必然有\(f\mod{x+1}=f(-1)\in \frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x+1}\)，所以我们可以通过映射：
$$
\phi:\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^n+1}\rightarrow\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x+1},f(x)\mapsto f(-1)
$$
将商环\(\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^n+1}\)中的所有多项式映射到\(\frac{(\mathbb{Z}/q\mathbb{Z})[x]}{x+1}\)中，从而对于GenNTRU生成的样本，有：
$$
\begin{cases}
g_1=h_1f_x\\
g_2=h_2f_x\\
\end{cases}\rightarrow
\begin{cases}
g_1(-1)\equiv h_1(-1)f_x(-1)\pmod{q}\\
g_2(-1)\equiv h_2(-1)f_x(-1)\pmod{q}\\
\end{cases}
$$
根据上式可以构造格：
$$
\pmb{B}=\left(\begin{matrix}
1&h_{1}(-1)&h_{2}(-1)\\
&q&\\
&&q
\end{matrix}\right)
$$
预期有\((f_x(-1),k_1,k_2)\pmb{B}=(f_x(-1),g_{1}(-1),g_{2}(-1))\)，按照GenNTRU的生成规则我们可以知道若\(f_x,h_1,h_2\)是GenNTRU中给出的样本，那么其对应的\(f_{x},g_{1},g_{2}\)都是三元多项式，此时上述格规约出的短向量\((f_x(-1),g_{1}(-1),g_{2}(-1))\)也会相对较短，而若\(f_x,h_1,h_2\)是随机多项式样本，那么通过同样方法规约出的短向量会很长，可以通过下述代码进行测试：
from sage.all import *
from sage.misc import prandom
import random
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
def sample(rand):
return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))
def GenNTRU():
f = [sample(prandom) for _ in range(n)]
g1 = [sample(prandom)for _ in range(n)]
g2 = [sample(prandom) for _ in range(n)]
g1x = Q(g1)
g2x = Q(g2)
while True:
fx = Q(f)
try:
h1 = g1x / fx
h2 = g2x / fx
return (h1.lift(), h2.lift(), fx)
except:
prandom.shuffle(f)
continue
n1 = []
for _ in range(1000):
h1, h2, f = GenNTRU()
H1 = ZZ(h1(-1))
H2 = ZZ(h2(-1))
L = matrix(ZZ, [[1, H1, H2], [0, q, 0], [0, 0, q]])
res = L.LLL()[0]
n1.append(res.norm()**2)
print(min(n1), max(n1))
n2 = []
for _ in range(1000):
h1, h2 = Q.random_element().lift(), Q.random_element().lift()
H1 = ZZ(h1(-1))
H2 = ZZ(h2(-1))
L = matrix(ZZ, [[1, H1, H2], [0, q, 0], [0, 0, q]])
res = L.LLL()[0]
n2.append(res.norm()**2)
print(min(n2), max(n2))经过多次测试我们可以知道，随机样本规约出来的短向量范数的平方最小值也远远大于GenNTRU中给出的样本规约出来的短向量范数的平方的最大值，所以我们可以通过编写如下样本区分器：
def diff(h1, h2, q, bound):
H1 = ZZ(h1(-1))
H2 = ZZ(h2(-1))
L = matrix(ZZ, [[1, H1, H2], [0, q, 0], [0, 0, q]])
res = L.LLL()[0]
if res.norm() ** 2 < bound:
return 0
return 1通过如下代码可以测试上述区分器的区分成功率：
from sage.all import *
from sage.misc import prandom
import random
from tqdm import trange
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
def sample(rand):
return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))
def GenNTRU():
f = [sample(prandom) for _ in range(n)]
g1 = [sample(prandom)for _ in range(n)]
g2 = [sample(prandom) for _ in range(n)]
g1x = Q(g1)
g2x = Q(g2)
while True:
fx = Q(f)
try:
h1 = g1x / fx
h2 = g2x / fx
return (h1.lift(), h2.lift(), fx)
except:
prandom.shuffle(f)
continue
def diff(h1, h2, q, bound):
H1 = h1(-1)
H2 = h2(-1)
L = matrix(ZZ, [[1, H1, H2], [0, q, 0], [0, 0, q]])
res = L.LLL()[0]
if res.norm() ** 2 < bound:
return 0
return 1
success = 0
for _ in trange(100000):
coin = random.getrandbits(1)
if coin == 0:
pk1, pk2, fx = GenNTRU()
else:
pk1, pk2, fx = Q.random_element().lift(), Q.random_element().lift(), Q([sample(prandom) for _ in range(n)])
if diff(pk1, pk2, q, 10000) == coin:
success += 1
print(success / 100000)测试可以知道在bound设置为10000的时候区分率可以达到100%，那么我们就可以用这个区分器达到区分样本的效果，这样我们就可以获得最多20258个coin值，结合gf2bv就可以恢复出MT19937的状态，从而预测出加密flag用的密钥，用预测出的密钥来解密就可以得到flag：
from sage.all import *
from sage.misc import prandom
from tqdm import trange
from pwn import *
from gf2bv import *
from gf2bv.crypto.mt import *
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
def diff(h1, h2, q, bound):
H1 = h1(-1)
H2 = h2(-1)
L = matrix(ZZ, [[1, H1, H2], [0, q, 0], [0, 0, q]])
res = L.LLL()[0]
if res.norm() ** 2 < bound:
return 0
return 1
p = remote("127.0.0.1", 12345)
coins = []
for _ in trange(19938):
p.sendlineafter(b"c :", b"1")
p.recvuntil(b"Hints: ")
h1 = Q(eval(p.recvuntil(b"]").strip().decode())).lift()
h2 = Q(eval(p.recvuntil(b"]").strip().decode())).lift()
coins.append(diff(h1, h2, q, 10000))
p.sendlineafter(b"c :", b"2")
p.recvuntil(b"Flag: ")
ct = eval(p.recvline().strip().decode())
# print(coin)
LS = LinearSystem([32] * 624)
mt = LS.gens()
mt19937 = MT19937(mt)
tmp = []
for coin in coins:
tmp.append(mt19937.getrandbits(1) ^ coin)
tmp.append(mt[0] ^ 0x80000000)
for res in LS.solve_all(tmp):
_rng = MT19937(res)
rng = _rng.to_python_random()
try:
for _ in trange(19938):
trash = rng.getrandbits(1)
SHA = SHA256.new()
SHA.update(str(rng.getrandbits(256)).encode())
KEY = SHA.digest()
cipher = AES.new(KEY, AES.MODE_ECB)
print(cipher.decrypt(ct))
except:
pass有概率成功：
