强网杯 2025 初赛 wp
强网杯 2025 初赛 wp
check-little
N 和 c 有公因数
可直接将 N 分解1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, inverse
import gmpy2
from tqdm import *
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = "bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2"
p = GCD(N, c)
print(p)
q = N//p
d = inverse(3, (p-1)*(q-1))
key = pow(c, d, N)
cipher= AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC)
print(cipher.decrypt(bytes.fromhex(ciphertext)))
#flag{m_m4y_6e_divIS1b1e_by_p?!}
ezran
断点伪随机数预测
每次泄露 8 位，然后 3108 轮，完全足够来还原 state
之后根据伪随机数生成器的状态对 shuffle 求逆即可
考虑到存在多解，使用 gf2bv 将所有解遍历即可
1 | from gf2bv import LinearSystem |
sk
密钥生成元素
上面的都是 的
注意到题目的加密逻辑1
2
3
4
5
6
7
8
9
10
11
12
13
14def 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
P, Q 里面的元素均为 520 bit，而 upt**j%p 为 256 bit
可以用 cuso 对 upt**j%p进行求解 （造格的话应该要想怎么用到 p ，因为 cuso 的 bound，不设到 p 是解不出来的）
解出后可以根据这六个值去确定 pt
若存在多解的情况，将六个值分成三三，分别解出 pt 进行验证即可
最后得到的解应该是唯一的
拿到 pt 后生成一组新的私钥即可
exp:
1 | from random import randint |
Blurred
参考 NTRU 的生成逻辑1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def 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
首先会发现 f, g1, g2 都是很小的，且比较关键的一点是选取到 0 的概率更大，这会导致它们更趋近于 0
在商环上，有多项式
发现将 x=-1 代入后
其中 和 都是很小的量
而且后来题目将 q 增大，使得随机情况的 f、g 极大概率不会这么小
可以通过这个性质枚举 f ，通过计算出来的 g 是否很小来进行判断
成功判断 20000 多次后，就可以根据 coins 打 MT19937
最终成功恢复 key， 解得 flag
exp1:(接收信息)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from pwn import *
import re
from tqdm import *
from Crypto.Util.number import long_to_bytes
from sage.all import *
import re, ast
io = remote("39.106.40.37", 20488)
def center_lift(l):
return [x - q if x > q//2 else x for x in l]
def lift_mod(x):
return x-q if x > q//2 else x
def parse_int_list_bytes(b: bytes):
# b 形如 b'[123, 456, -789]'
b = b.strip()
assert b[:1] == b'[' and b[-1:] == b']'
if len(b) <= 2:
return []
parts = b[1:-1].split(b',')
out = []
for p in parts:
p = p.strip()
if p:
out.append(int(p)) # 直接把 bytes 转 int
return out
def mt19937(bs, out):
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = []
for o in out:
rng.getrandbits(8)
zeros.append((rng.getrandbits(16)>>8) ^ o)
zeros +=[mt[0] ^ 0x80000000]
print("solving...")
sol = lin.solve_all(zeros)
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
f = x**n + 1
out = []
pk_list = []
'''
for t in trange(20258):
io.sendlineafter(b"c :", b"1")
io.recvuntil(b'Hints:')
# 读第一个列表（先到 '[', 再到对应 ']'）
io.recvuntil(b'[', drop=False)
lst1_bytes = b'[' + io.recvuntil(b']', drop=False)
# 读第二个列表
io.recvuntil(b'[', drop=False)
lst2_bytes = b'[' + io.recvuntil(b']', drop=False)
pk1 = parse_int_list_bytes(lst1_bytes)
pk2 = parse_int_list_bytes(lst2_bytes)
pk1_list.append(pk1)
pk2_list.append(pk2)
'''
out = []
for i in trange(20251):
if i % 100 == 0:
for j in range(min(100, 20251-i)):
io.sendline(b"1")
tmp = io.recvuntil(b'Hints:')
pk1, pk2 = io.recvline().split(b'] [')
pk1, pk2 = eval(pk1+b']'), eval(b'['+pk2)
bound = 160
ans = 1
h1 = lift_mod(int((Q(pk1)).lift()(x = -1)))
h2 = lift_mod(int((Q(pk2)).lift()(x = -1)))
for f in range(-bound, bound):
if f == 0:
continue
g1 = f*h1 %q
g2 = f*h2 %q
if abs(lift_mod(g1)) <= bound and abs(lift_mod(g2)) <= bound and (h1*lift_mod(g2) - h2*lift_mod(g1)) % q == 0:
ans = 0
out.append(0)
break
if ans == 1:
out.append(1)
'''
bound = 120
tmp = 1
dif = 1
h1 = lift_mod(int((Q(pk1)).lift()(x = -1)))
h2 = lift_mod(int((Q(pk2)).lift()(x = -1)))
for f in range(-bound, bound):
if f == 0:
continue
g1 = f*h1 %q
g2 = f*h2 %q
if abs(lift_mod(g1)) <= bound and abs(lift_mod(g2)) <= bound and (h1*lift_mod(g2) - h2*lift_mod(g1)) % q == 0:
tmp = 0
out.append(0)
break
if tmp == 1:
out.append(1)
'''
print(str(out))
io.sendlineafter(b"c :", b"2")
io.recvuntil(b'Flag:')
enc_flag = eval(io.recvline()[:-1])
print(enc_flag)
'''
with open("/home/qwb2025/ntru_out.txt", "w") as f:
for pk in pk_list:
f.write(pk.decode())
f.write("\n")
'''
exp2:(打 MT19937)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from pwn import *
import re
from tqdm import *
from Crypto.Util.number import long_to_bytes
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import pad, unpad
from tqdm import *
#c = b'm\x07y\xda\xddDy5\xd717\xc7Sm_z\xee!^\x1d\xce\x04\xd6Y\xf0\x1a<\xb75q\x08Q\xcf\xf0\xa4\xc8ht?S&\x8a\x92,\xf6\x9f@5'
c = b'>he=\x83\x08\xde\xf1s\x94\x17\xae\x9c69\t\xed\xb5\x8f\xbd9\x8c\xa4\xce\x9e\xfaO\xca\x17\xb2x&\xfb\x91\xbf\x85\xab(\xe9\xbf\t\x04\xe6\x0e\xfc\xfaI\xed'
import ast
import numpy as np
'''
rows, cols = 20255, 1031
dtype = np.int32 # 若数值可能超32位，改为 np.int64
pk1_list = np.memmap('data.int32.memmap', dtype=dtype, mode='w+', shape=(rows, cols))
pk2_list = np.memmap('data.int32.memmap', dtype=dtype, mode='w+', shape=(rows, cols))
pat = re.compile(r'\[([^\]]*)\]\s+\[([^\]]*)\]')
with open('/home/qwb2025/ntru_out.txt', 'r', encoding='utf-8') as f:
for i, line in enumerate(f):
if i % 2 == 0:
continue # 只处理奇数行（从0开始计数）
s = line.strip()
if not s:
raise ValueError(f'第 {i} 行是空行')
m = pat.search(s)
if not m:
raise ValueError(f'第 {i} 行未匹配到两个列表：{s[:120]}...')
left_txt, right_txt = m.group(1), m.group(2)
# 以逗号分隔解析为数值（矢量化、很快），允许空格
a = np.fromstring(left_txt, sep=',', dtype=dtype)
b = np.fromstring(right_txt, sep=',', dtype=dtype)
if a.size != cols or b.size != cols:
raise ValueError(f'第 {i} 行列数不符：got ({a.size}, {b.size}), expected ({cols}, {cols})')
pk1_list[i//2, :] = a
pk2_list[i//2, :] = b
print(len(pk1_list), len(pk2_list))
'''
def mt19937(bs, out):
lin = LinearSystem([32] * 624)
mt = lin.gens()
rng = MT19937(mt)
zeros = []
for o in out:
zeros.append((rng.getrandbits(1)) ^ int(o))
zeros +=[mt[0] ^ 0x80000000]
print("solving...")
sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()
for j in trange(20251):
veri = pyrand.getrandbits(1)
if veri != out[j]:
print("wrong!")
return
print("recovering the flag...")
key = pyrand.getrandbits(256)
SHA = SHA256.new()
SHA.update(str(key).encode())
KEY = SHA.digest()
cipher = AES.new(KEY, AES.MODE_ECB)
flag = unpad(cipher.decrypt(c), 16)
print(flag)
def center_lift(l):
return [x - q if x > q//2 else x for x in l]
def lift_mod(x):
return x-q if x > q//2 else x
def change(a):
if a == 1:
return 0
else:
return 1
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)
f = x**n + 1
out = ''
'''
for pk1, pk2 in tqdm(zip(pk1_list, pk2_list)):
bound = 150
tmp = 1
pk1 = pk1.tolist()
pk2 = pk2.tolist()
h1 = lift_mod(int((Q(pk1)).lift()(x = -1)))
h2 = lift_mod(int((Q(pk2)).lift()(x = -1)))
for f in range(-bound, bound):
if f == 0:
continue
g1 = f*h1 %q
g2 = f*h2 %q
if abs(lift_mod(g1)) <= bound and abs(lift_mod(g2)) <= bound and (h1*lift_mod(g2) - h2*lift_mod(g1)) % q == 0:
tmp = 0
out.append(0)
break
if tmp == 1:
out.append(1)
'''
'''
for pk1, pk2 in tqdm(zip(pk1_list, pk2_list)):
out.append(distinct(pk1.tolist(), pk2.tolist()))
'''
with open("/home/qwb2025/exp2_out.txt", "w") as f:
for v in out:
f.write(str(v) + ",")
print(len(out))
mt19937(1, out)
#flag{b3c8e1c4-6f4b-4d7e-bf6f-7e4030e9d8fd}
总结
这次强网杯除了零解题都打出来了，相比去年来说有了些进步，继续加油 ☝️🤓☝️