强网杯2025

发表于

爽玩

check-little

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from Crypto.Cipher import AES

e = 3
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = 'bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2'

p = GCD(N, c)
q = N // p
d = inverse(e, (p - 1) * (q - 1))
key = pow(c, d, N)
print(AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).decrypt(bytes.fromhex(ciphertext)))

对 nn 和 cc 计算 gcd⁡\gcd 发现有公因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from Crypto.Cipher import AES

e = 3
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = 'bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2'

p = GCD(N, c)
q = N // p
d = inverse(e, (p - 1) * (q - 1))
key = pow(c, d, N)
print(AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).decrypt(bytes.fromhex(ciphertext)))

ezran

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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")

分析代码知道 xx 和 r2r_2 的高 8 位一样，然后可以用 gf2bv 求，由于多解所以用 solve_all

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
from sage.all import *
from Crypto.Util.number import *
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from output import gift, c

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(bs) >> 8 ^ int(o))
    zeros.append(mt[0] ^ int(0x80000000))
    for sol in lin.solve_all(zeros):

        rng = MT19937(sol)
        pyrand = rng.to_python_random()
        yield pyrand


def ins(s, rng, rounds = 2025):
    a = list(s)
    n = len(a)
    sw = []

    for _ in range(rounds):
        for i in range(n - 1, 0, -1):
            j = rng.randrange(i + 1)   
            sw.append((i, j))

    for i, j in reversed(sw):
        a[i], a[j] = a[j], a[i]

    if isinstance(s, (bytes, bytearray)):
        return bytes(a)
    return ''.join(a)

gift = long_to_bytes(gift)
g = [gift[2 * i:2 * i + 2][0] for i in range(len(gift) // 2)]

for rng in mt19937(16, g):
    gg=b''
    for i in range(3108):
        r1 = rng.getrandbits(8)
        r2 = rng.getrandbits(16)
        x=(pow(r1, 2*i, 257) & 0xff) ^ r2
        cc=long_to_bytes(x, 2)
        gg+=cc
    if gg == gift:
        print(ins(c, rng))

sk

题目

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
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!")

注意加密代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

如果把 u * pt**j % p 看作一个整体，那就是一个小值，可以考虑用格(我这里用的cuso)打出来，然后就可以拿到 ticket 了，之后自己走一遍流程加密一下 ticket 然后传回去就好了

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
from sage.all import *
from Crypto.Util.number import *
from cuso import find_small_roots
from pwn import process, remote
from chal import gen_key, encrypt, decrypt

# r = process(['python', 'chal.py'])
r = remote('47.104.146.31', 7777)
r.sendlineafter(b'team token:', b'icq61cd73d6c5db567dc74bb9cac87e6')
# r.interactive()
pk = eval(r.recvline())
enc_ticket = eval(r.recvline())
Pc, Qc = enc_ticket
P, Q, p = pk

pt_2_u1, pt_2_u2, pt_u1, pt_u2, u1, u2 = var('pt_2_u1, pt_2_u2, pt_u1, pt_u2, u1, u2')

W = [pt_2_u1, pt_2_u2, pt_u1, pt_u2, u1, u2]

PP = 0
QQ = 0

PP = P[0][0] * u1 + P[0][1] * pt_u1 + P[0][2] * pt_2_u1 + P[1][0] * u2 + P[1][1] * pt_u2 + P[1][2] * pt_2_u2 - Pc
QQ = Q[0][0] * u1 + Q[0][1] * pt_u1 + Q[0][2] * pt_2_u1 + Q[1][0] * u2 + Q[1][1] * pt_u2 + Q[1][2] * pt_2_u2 - Qc

bounds = {}
for w in W:
    bounds[w] = (0, p)

roots = find_small_roots([PP, QQ], bounds)

for root in roots:
    u1_, u2_, pt_u1_, pt_u2_ = root[u1], root[u2], root[pt_u1], root[pt_u2]
    pt1 = pt_u1_ * inverse(u1_, p) % p
    pt2 = pt_u2_ * inverse(u2_, p) % p
    if pt1 == pt2:
        pt = pt1
        break

print(pt)

ticket = long_to_bytes(pt)
sk, pk = gen_key(p)
(R1, S1), (R2, S2), f, h, p = sk
new_ticket = encrypt(pk, ticket)
assert decrypt(sk, new_ticket) == ticket

r.sendlineafter(b'op>', b'2')
r.sendlineafter(b'ct:', str(new_ticket[0]) + ' ' + str(new_ticket[1]))
r.sendlineafter(b'your f:', str(f[0]) + ' ' + str(f[1]))
r.sendlineafter(b'your h:', str(h[0]) + ' ' + str(h[1]))
r.sendlineafter(b'your R1 S1:', str(R1) + ' ' + str(S1))
r.sendlineafter(b'your R2 S2:', str(R2) + ' ' + str(S2))

r.interactive()

Blurred

题目

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
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

如果当 x = -1 时，商换可以约去，变成

pki(−1)≡gi(−1)⋅f(−1)−1mod  qpk_i(-1)\equiv g_i(-1)\cdot f(-1)^{-1}\mod q

由于 gig_i 和 ff 是稀疏多项式，所以 x = -1 时也是小值，因此 pki(−1)pk_i(-1) 可能在区间 [−q2,q2][-\frac q2,\frac q2] 附近

而 coin=1coin=1 的时候似乎没有这个性质

然后由于之前老附件的 qq 太小了，区分度不大因此写了个代码训练了个模型，成功率只有 89%

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
import random, time
import numpy as np
from sage.all import PolynomialRing, Zmod, randint, inverse_mod
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split, StratifiedKFold
from sklearn.metrics import accuracy_score, confusion_matrix, roc_auc_score
import joblib

# ============== 全局参数（按需调） ==============
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)

SEED = 42
random.seed(SEED); np.random.seed(SEED)

# 只用合法同态点（非常关键）
TEST_XS = [-1]         # 只保留 -1

# 小 F 搜索残差阈值（越大越稳但稍慢；建议 140~200）
R_smallF = 160

# 比值一致性 |a*V1 - b*V2| 搜索界（建议 60~80）
B_ratio = 70

# 训练集规模（大样本稳阈值）
N_POS = 20000
N_NEG = 20000
TEST_SIZE = 0.2
N_FOLDS = 5

# 自动挑阈值时的网格与约束
ALPHA_GRID = (1.0, 1.5, 2.0, 3.0, 4.0, 6.0, 8.0)
TARGET_TOTAL_ERR = 0.35   # 总错误率目标 ≤ 1.44%
FP_BUDGET = 0.007           # FP 预算（≤ 0.7%）
CLASS_PRIOR = (0.5, 0.5)    # 如已知先验，可改成 (p_coin0, p_coin1)

# XGBoost / LightGBM 可选
XGB_OK = False; LGB_OK = False
try:
    import xgboost as xgb
    XGB_OK = True
except Exception:
    pass
if not XGB_OK:
    try:
        import lightgbm as lgb
        LGB_OK = True
    except Exception:
        pass

# ============== 基础工具 ==============
def lift_centered_int(a, q):
    a = int(a) % q
    return a if a <= q//2 else a - q

def eval_at_point(pk_list, t):
    # 评估 pk(t) in Z_q；这里我们只在 t=-1 用，同态成立
    V, p = 0, 1
    for c in pk_list:
        V += int(c)*p
        p = (p*t) % q
    return lift_centered_int(V, q)

# ============== 强化：小残差交集候选 F ==============
def smallF_candidates_intersection(V1, V2, R=R_smallF):
    """
    枚举 δ in [-R,R] 上的同余类：
      S1 = { F ≡ δ1 * V1^{-1} (mod q) }
      S2 = { F ≡ δ2 * V2^{-1} (mod q) }
    取 S1 ∩ S2，返回：
      - match_cnt: 交集类数量
      - min_abs_F: 交集中“最小 |F| 的代表”（F 取中心代表）
      - min_max_delta: 令该 F 成立的最小 max(|δ1|,|δ2|)
    随机公钥几乎无交集；结构公钥常有交集，且有小 |F|。
    """
    if V1 % q == 0 or V2 % q == 0:
        # 极端强信号：某边本身很小/为0时（随机几乎不出现）
        return 1, 0, 0

    inv1 = int(inverse_mod(V1 % q, q))
    inv2 = int(inverse_mod(V2 % q, q))

    # 用字典记录类 -> best |δ|
    cls1 = {}
    for d1 in range(-R, R+1):
        F1 = (d1 * inv1) % q
        b1 = abs(d1)
        if F1 not in cls1 or b1 < cls1[F1]:
            cls1[F1] = b1

    match_cnt, min_abs_F, min_max_delta = 0, None, None

    for d2 in range(-R, R+1):
        F2 = (d2 * inv2) % q
        if F2 in cls1:
            match_cnt += 1
            # 该同余类的最小 |F| 中心代表
            F_cent = lift_centered_int(F2, q)
            # 该匹配的代价：max(|δ1|,|δ2|)
            cost = max(cls1[F2], abs(d2))
            if (min_abs_F is None) or (abs(F_cent) < abs(min_abs_F)):
                min_abs_F = F_cent
            if (min_max_delta is None) or (cost < min_max_delta):
                min_max_delta = cost

    if min_abs_F is None:
        # 无交集
        return 0, q, R+1
    return match_cnt, abs(min_abs_F), min_max_delta

# ============== 其他弱特征（保留但只在 t=-1） ==============
def smallF_score(V1, V2, R=R_smallF):
    # 仍保留“扫 F”得到 best_s（辅助弱特征）
    best = (10**9, None)
    for F in range(-R, R+1):
        if F == 0: continue
        Y1 = lift_centered_int(F*V1, q)
        if abs(Y1) >= best[0]: continue
        Y2 = lift_centered_int(F*V2, q)
        s = max(abs(Y1), abs(Y2))
        if s < best[0]:
            best = (s, abs(F))
            if s == 0: break
    return best

def ratio_consistency(V1, V2, B=B_ratio):
    # min |a*V1 - b*V2|_c, |a|,|b|<=B
    best = 10**9
    for a in range(-B, B+1):
        for b in range(-B, B+1):
            if a==0 and b==0: continue
            r = lift_centered_int(a*V1 - b*V2, q)
            ar = abs(r)
            if ar < best:
                best = ar
                if ar == 0: return 0
    return best

def coeff_stats(pk_list):
    cs = [lift_centered_int(c, q) for c in pk_list]
    m = sum(cs)/n
    msq = sum(c*c for c in cs)/n
    # 更细 bins 强化“靠近0”的比例特征
    bins = [q//64, q//32, q//16, q//8]
    fracs = [sum(1 for c in cs if abs(c)<=b)/n for b in bins]
    linf = max(abs(c) for c in cs)
    return [m, msq] + fracs + [linf]

def decision_feature_absF(pk1_list, pk2_list, R=R_smallF):
    # 兼容你原 decision：命中不同 |F| 的个数 & 最小 |F|
    V1 = eval_at_point(pk1_list, -1)
    V2 = eval_at_point(pk2_list, -1)
    hits = []
    for F in range(-R, R+1):
        if F==0: continue
        Y1 = lift_centered_int(F*V1, q)
        if abs(Y1) > R: continue
        Y2 = lift_centered_int(F*V2, q)
        if abs(Y2) > R: continue
        if (V1*Y2 - V2*Y1) % q == 0:
            hits.append(abs(F))
    if hits:
        uniq = sorted(set(hits))
        return [len(uniq), min(uniq)]
    return [0, 0]

# ============== 特征提取：只在 t=-1 汇总（强 + 若干弱） ==============
def extract_features(pk1_list, pk2_list):
    feats = []
    # 核心同态点
    V1 = eval_at_point(pk1_list, -1)
    V2 = eval_at_point(pk2_list, -1)

    # 强特征：交集候选 F
    match_cnt, min_absF_inter, min_max_delta = smallF_candidates_intersection(V1, V2, R_smallF)
    feats += [match_cnt, min_absF_inter, min_max_delta]

    # 辅助弱特征
    s, bestF = smallF_score(V1, V2, R_smallF)
    feats += [s, (bestF if bestF else 0)]
    feats += [ratio_consistency(V1, V2, B_ratio)]

    # 原始点值（缩放）
    feats += [V1/(q/2), V2/(q/2)]

    # 系数统计（更细 bins）
    feats += coeff_stats(pk1_list)
    feats += coeff_stats(pk2_list)

    # 你的 decision 两个特征
    feats += decision_feature_absF(pk1_list, pk2_list, R_smallF)

    return feats

def extract_features_plus(pk1_list, pk2_list):
    return extract_features(pk1_list, pk2_list)

# ============== 数据生成（coin=0 / coin=1） ==============
def GenNTRU_once():
    while True:
        f  = [randint(-1, 1) for _ in range(n)]
        g1 = [randint(-1, 1) for _ in range(n)]
        g2 = [randint(-1, 1) for _ in range(n)]
        fx  = Q(f); g1x = Q(g1); g2x = Q(g2)
        try:
            h1 = (g1x / fx).lift()
            h2 = (g2x / fx).lift()
            return [int(c) % q for c in h1.list()], [int(c) % q for c in h2.list()]
        except Exception:
            continue

def RandPK_once():
    pk1 = Q.random_element().lift()
    pk2 = Q.random_element().lift()
    return [int(c) % q for c in pk1.list()], [int(c) % q for c in pk2.list()]

def build_dataset(N0, N1, use_plus=True, verbose=True):
    X, y = [], []
    if verbose: print(f"[+] Generating coin=0 (NTRU) : {N0}")
    for i in range(N0):
        pk1, pk2 = GenNTRU_once()
        X.append(extract_features_plus(pk1, pk2) if use_plus else extract_features(pk1, pk2))
        y.append(1)
        if verbose and (i+1) % 500 == 0: print(f"  - {i+1}/{N0}")

    if verbose: print(f"[+] Generating coin=1 (random): {N1}")
    for i in range(N1):
        pk1, pk2 = RandPK_once()
        X.append(extract_features_plus(pk1, pk2) if use_plus else extract_features(pk1, pk2))
        y.append(0)
        if verbose and (i+1) % 500 == 0: print(f"  - {i+1}/{N1}")

    return np.array(X, float), np.array(y, int)

# ============== 模型（XGB→LGB→RF） ==============
def train_xgb(X_tr, y_tr, X_va, y_va):
    clf = xgb.XGBClassifier(
        n_estimators=600, max_depth=6, learning_rate=0.06,
        subsample=0.9, colsample_bytree=0.9,
        reg_lambda=1.0, reg_alpha=0.0,
        objective='binary:logistic', eval_metric='auc',
        random_state=SEED, n_jobs=4
    )
    clf.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], verbose=False)
    return clf

def train_lgb(X_tr, y_tr, X_va, y_va):
    clf = lgb.LGBMClassifier(
        n_estimators=800, num_leaves=63, learning_rate=0.05,
        subsample=0.9, colsample_bytree=0.9,
        reg_lambda=1.0, random_state=SEED, n_jobs=4
    )
    clf.fit(X_tr, y_tr, eval_set=[(X_va, y_va)], eval_metric='auc', verbose=False)
    return clf

def train_rf(X_tr, y_tr):
    clf = RandomForestClassifier(
        n_estimators=800, max_depth=None,
        min_samples_split=2, min_samples_leaf=1,
        n_jobs=4, random_state=SEED
    )
    clf.fit(X_tr, y_tr)
    return clf

def kfold_train(X, y, n_folds=5):
    skf = StratifiedKFold(n_splits=n_folds, shuffle=True, random_state=SEED)
    models, oof = [], np.zeros(len(y))
    for i,(tr,va) in enumerate(skf.split(X,y),1):
        X_tr, X_va, y_tr, y_va = X[tr], X[va], y[tr], y[va]
        print(f"[+] Fold {i}/{n_folds} (XGB priority)")
        if XGB_OK: clf = train_xgb(X_tr, y_tr, X_va, y_va)
        elif LGB_OK: clf = train_lgb(X_tr, y_tr, X_va, y_va)
        else: clf = train_rf(X_tr, y_tr)
        models.append(clf)
        if hasattr(clf,"predict_proba"):
            p = clf.predict_proba(X_va)[:,1]
        else:
            # 保障分数
            if hasattr(clf,"decision_function"):
                df = clf.decision_function(X_va)
                p = (df-df.min())/(df.max()-df.min()+1e-9)
            else:
                p = clf.predict(X_va).astype(float)
        oof[va] = p
        auc = roc_auc_score(y_va, p)
        print(f"    fold AUC = {auc:.4f}")
    return models, oof

# ============== 阈值自动调优（带 FP 约束） ==============
def tune_threshold_by_cost(y_true, probs, alpha_fp=2.0, target_fp_rate=None):
    best_t, best_acc, best_cost, best_cm = 0.5, -1.0, 1e18, None
    for t in np.linspace(0.01,0.99,99):
        y_pred = (probs>=t).astype(int)
        cm = confusion_matrix(y_true, y_pred, labels=[1,0])
        TP,FN = cm[0,0], cm[0,1]
        FP,TN = cm[1,0], cm[1,1]
        fp_rate = FP / max(FP+TN, 1)
        if (target_fp_rate is not None) and (fp_rate>target_fp_rate):
            continue
        acc  = accuracy_score(y_true, y_pred)
        cost = alpha_fp*FP + FN
        if target_fp_rate is not None:
            if acc>best_acc:
                best_acc, best_t, best_cm = acc, t, cm
        else:
            if cost<best_cost:
                best_cost, best_t, best_cm = cost, t, cm
    if best_cm is None:
        # 回退：无阈值满足 FP 约束，按成本挑
        for t in np.linspace(0.01,0.99,99):
            y_pred = (probs>=t).astype(int)
            cm = confusion_matrix(y_true, y_pred, labels=[1,0])
            TP,FN = cm[0,0], cm[0,1]
            FP,TN = cm[1,0], cm[1,1]
            acc  = accuracy_score(y_true, y_pred)
            cost = alpha_fp*FP + FN
            if cost<best_cost:
                best_cost, best_t, best_cm = cost, t, cm
                best_acc = acc
    return best_t, (best_acc, best_cm)

def auto_pick_alpha_threshold(y_true, oof_probs,
                              alpha_grid=ALPHA_GRID,
                              target_total_err_rate=TARGET_TOTAL_ERR,
                              fp_budget_ratio=FP_BUDGET):
    best = None
    for a in alpha_grid:
        t, (acc, cm) = tune_threshold_by_cost(y_true, oof_probs, alpha_fp=a, target_fp_rate=fp_budget_ratio)
        TP,FN = cm[0,0], cm[0,1]
        FP,TN = cm[1,0], cm[1,1]
        err_rate = (FP+FN) / max(TP+FN+FP+TN,1)
        info = dict(alpha=a, threshold=t, acc=acc, cm=cm, err_rate=err_rate)
        if (best is None) or (err_rate<best["err_rate"]):
            best = info
    return best["alpha"], best["threshold"], best

# ============== 保存/加载/推断 ==============
def save_bundle(models, threshold, path="ntru_coin_xgb_bundle.pkl"):
    joblib.dump({"models":models, "threshold":threshold}, path)
    print(f"[+] Model bundle saved to {path}")

def load_bundle(path="ntru_coin_xgb_bundle.pkl"):
    b = joblib.load(path)
    print(f"[+] Model bundle loaded from {path}")
    return b["models"], b["threshold"]

def ensemble_predict_proba(models, X):
    probs=[]
    for clf in models:
        if hasattr(clf,"predict_proba"):
            p = clf.predict_proba(X)[:,1]
        else:
            if hasattr(clf,"decision_function"):
                df = clf.decision_function(X)
                p = (df-df.min())/(df.max()-df.min()+1e-9)
            else:
                p = clf.predict(X).astype(float)
        probs.append(p)
    return np.mean(probs, axis=0)

def predict_coin(models, threshold, pk1_list, pk2_list):
    feat = np.array(extract_features_plus(pk1_list, pk2_list), dtype=float).reshape(1,-1)
    p = ensemble_predict_proba(models, feat)[0]
    return bool(p>=threshold), float(p)

# ============== 主流程 ==============
if __name__ == "__main__":
    print("=== NTRU coin 判别（强化版）===")
    print(f"lib: XGB={XGB_OK}, LGB={LGB_OK}")
    print(f"n={n}, q={q}, TEST_XS={TEST_XS}, R_smallF={R_smallF}, B_ratio={B_ratio}")
    print(f"dataset: pos={N_POS}, neg={N_NEG}, test_size={TEST_SIZE}, kfold={N_FOLDS}")
    t0 = time.time()

    # 1) 数据
    X, y = build_dataset(N_POS, N_NEG, use_plus=True, verbose=True)

    # 2) 划分
    X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=TEST_SIZE, stratify=y, random_state=SEED)

    # 3) K折训练 + OOF 概率
    models, oof_probs = kfold_train(X_tr, y_tr, n_folds=N_FOLDS)

    # 4) 自动挑 ALPHA + 阈值（优先满足 FP 预算）
    best_alpha, threshold, info = auto_pick_alpha_threshold(
        y_true=y_tr, oof_probs=oof_probs,
        alpha_grid=ALPHA_GRID,
        target_total_err_rate=TARGET_TOTAL_ERR,
        fp_budget_ratio=FP_BUDGET
    )
    print(f"[AUTO] pick ALPHA_FP={best_alpha}, threshold={threshold:.3f}, err_rate={info['err_rate']:.4f}")
    print(f"[AUTO] OOF CM [[TP FN],[FP TN]]:\n{info['cm']}")

    # 5) 独立测试集评估
    proba_te = ensemble_predict_proba(models, X_te)
    y_pred_te = (proba_te>=threshold).astype(int)
    acc_te = accuracy_score(y_te, y_pred_te)
    cm_te  = confusion_matrix(y_te, y_pred_te, labels=[1,0])
    auc_te = roc_auc_score(y_te, proba_te)
    print(f"[TEST] acc={acc_te:.4f}, auc={auc_te:.4f}\n[TEST] CM [[TP FN],[FP TN]]:\n{cm_te}")

    # 6) 保存包
    save_bundle(models, threshold, "ntru_coin_xgb_bundle.pkl")

    # 7) 快速 sanity check
    pk1_pos, pk2_pos = GenNTRU_once()
    pk1_neg, pk2_neg = RandPK_once()
    pp, sp = predict_coin(models, threshold, pk1_pos, pk2_pos)
    pn, sn = predict_coin(models, threshold, pk1_neg, pk2_neg)
    print(f"[Sanity] coin=0 -> {pp} (p={sp:.4f})")
    print(f"[Sanity] coin=1 -> {pn} (p={sn:.4f})")
    print(f"Done. Time: {time.time()-t0:.1f}s")

不过现在 qq 大了完全可以不用模型也可以区分，但是写都写了总不能不用吧，直接拿模型跑就好了，不过模型不是完全拟合的(成功率约99.98%)，所以跑了 4 次才拿到完全 100% 正确的 coincoin，然后后面就是打随机数预测了

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
from sage.all import *
import numpy as np
import joblib

# ---- 参数（与训练时一致）----
q = 1342261
n = 1031
PR = PolynomialRing(Zmod(q), "x")
x = PR.gens()[0]
Q = PR.quotient(x**n + 1)

R_smallF = 160     # 与训练保持一致
B_ratio   = 60     # 与训练保持一致

# ---- 基础工具 ----
def lift_centered_int(a, q):
    a = int(a) % q
    return a if a <= q//2 else a - q

def eval_at_point(pk_list, t):
    V, p = 0, 1
    for c in pk_list:
        V += int(c)*p
        p = (p * t) % q
    return lift_centered_int(V, q)

# ---- 强特征：小残差交集候选 F ----
def smallF_candidates_intersection(V1, V2, R=R_smallF):
    if V1 % q == 0 or V2 % q == 0:
        return 1, 0, 0
    inv1 = int(inverse_mod(V1 % q, q))
    inv2 = int(inverse_mod(V2 % q, q))
    cls1 = {}
    for d1 in range(-R, R+1):
        F1 = (d1 * inv1) % q
        b1 = abs(d1)
        if F1 not in cls1 or b1 < cls1[F1]:
            cls1[F1] = b1
    match_cnt, min_abs_F, min_max_delta = 0, None, None
    for d2 in range(-R, R+1):
        F2 = (d2 * inv2) % q
        if F2 in cls1:
            match_cnt += 1
            F_cent = lift_centered_int(F2, q)
            cost = max(cls1[F2], abs(d2))
            if (min_abs_F is None) or (abs(F_cent) < abs(min_abs_F)):
                min_abs_F = F_cent
            if (min_max_delta is None) or (cost < min_max_delta):
                min_max_delta = cost
    if min_abs_F is None:
        return 0, q, R+1
    return match_cnt, abs(min_abs_F), min_max_delta

# ---- 其他辅助弱特征（只在 x=-1）----
def smallF_score(V1, V2, R=R_smallF):
    best = (10**9, None)
    for F in range(-R, R+1):
        if F == 0: continue
        Y1 = lift_centered_int(F*V1, q)
        if abs(Y1) >= best[0]: continue
        Y2 = lift_centered_int(F*V2, q)
        s = max(abs(Y1), abs(Y2))
        if s < best[0]:
            best = (s, abs(F))
            if s == 0: break
    return best

def ratio_consistency(V1, V2, B=B_ratio):
    best = 10**9
    for a in range(-B, B+1):
        for b in range(-B, B+1):
            if a == 0 and b == 0: continue
            r = lift_centered_int(a*V1 - b*V2, q)
            ar = abs(r)
            if ar < best:
                best = ar
                if ar == 0: return 0
    return best

def coeff_stats(pk_list):
    cs = [lift_centered_int(c, q) for c in pk_list]
    m = sum(cs)/n
    msq = sum(c*c for c in cs)/n
    bins = [q//64, q//32, q//16, q//8]
    fracs = [sum(1 for c in cs if abs(c) <= b)/n for b in bins]
    linf = max(abs(c) for c in cs)
    return [m, msq] + fracs + [linf]

def decision_feature_absF(pk1_list, pk2_list, R=R_smallF):
    V1 = eval_at_point(pk1_list, -1)
    V2 = eval_at_point(pk2_list, -1)
    hits = []
    for F in range(-R, R+1):
        if F == 0: continue
        Y1 = lift_centered_int(F*V1, q)
        if abs(Y1) > R: continue
        Y2 = lift_centered_int(F*V2, q)
        if abs(Y2) > R: continue
        if (V1*Y2 - V2*Y1) % q == 0:
            hits.append(abs(F))
    if hits:
        uniq = sorted(set(hits))
        return [len(uniq), min(uniq)]
    return [0, 0]

# ---- 与训练一致的特征拼装（只用 x=-1）----
def extract_features_plus(pk1_list, pk2_list):
    feats = []
    V1 = eval_at_point(pk1_list, -1)
    V2 = eval_at_point(pk2_list, -1)
    # 强特征：交集候选 F
    match_cnt, min_absF_inter, min_max_delta = smallF_candidates_intersection(V1, V2, R_smallF)
    feats += [match_cnt, min_absF_inter, min_max_delta]
    # 辅助弱特征
    s, bestF = smallF_score(V1, V2, R_smallF)
    feats += [s, (bestF if bestF else 0)]
    feats += [ratio_consistency(V1, V2, B_ratio)]
    # 原始缩放
    feats += [V1/(q/2), V2/(q/2)]
    # 系数统计
    feats += coeff_stats(pk1_list)
    feats += coeff_stats(pk2_list)
    # 你的 decision 两特征
    feats += decision_feature_absF(pk1_list, pk2_list, R_smallF)
    return np.array(feats, dtype=float).reshape(1, -1)

# ===== 兼容不同“特征版本”的提取器 =====

def coeff_stats_bins2(pk_list):
    # 2 桶版本（与早期训练脚本一致）：返回 5 维/把
    cs = [lift_centered_int(c, q) for c in pk_list]
    m = sum(cs)/n
    msq = sum(c*c for c in cs)/n
    frac1 = sum(1 for c in cs if abs(c) <= q//8)/n
    frac2 = sum(1 for c in cs if abs(c) <= q//16)/n
    linf = max(abs(c) for c in cs)
    return [m, msq, frac1, frac2, linf]

def extract_features_v24(pk1_list, pk2_list):
    # 24维（你“强化版”训练脚本用的）：4 桶 coeff_stats + 仅 x=-1
    feats = []
    V1 = eval_at_point(pk1_list, -1)
    V2 = eval_at_point(pk2_list, -1)
    mc, minF, minDelta = smallF_candidates_intersection(V1, V2, R_smallF)   # 3
    s, bestF = smallF_score(V1, V2, R_smallF)                               # +2 -> 5
    feats += [mc, minF, minDelta, s, (bestF if bestF else 0)]
    feats += [ratio_consistency(V1, V2, B_ratio)]                            # +1 -> 6
    feats += [V1/(q/2), V2/(q/2)]                                           # +2 -> 8
    feats += coeff_stats(pk1_list) + coeff_stats(pk2_list)                   # +14 -> 22 (因你当前 coeff_stats 是4桶：7/把)
    feats += decision_feature_absF(pk1_list, pk2_list, R_smallF)             # +2 -> 24
    return np.array(feats, float).reshape(1, -1)

def extract_features_v22(pk1_list, pk2_list):
    # 22维（你现在的 .pkl 很可能是这个版本训练的）：
    #   2 桶 coeff_stats（5/把*2=10），仅 x=-1 的强/弱特征（共 3+2+1+2=8），
    #   再加上 x=+1 的原始两维（2）和 decision 两维（2） => 总 22
    feats = []
    V1m1 = eval_at_point(pk1_list, -1)
    V2m1 = eval_at_point(pk2_list, -1)
    mc, minF, minDelta = smallF_candidates_intersection(V1m1, V2m1, R_smallF)   # 3
    s, bestF = smallF_score(V1m1, V2m1, R_smallF)                               # +2 -> 5
    feats += [mc, minF, minDelta, s, (bestF if bestF else 0)]
    feats += [ratio_consistency(V1m1, V2m1, B_ratio)]                            # +1 -> 6
    feats += [V1m1/(q/2), V2m1/(q/2)]                                           # +2 -> 8
    feats += coeff_stats_bins2(pk1_list) + coeff_stats_bins2(pk2_list)           # +10 -> 18
    feats += decision_feature_absF(pk1_list, pk2_list, R_smallF)                 # +2 -> 20
    V1p1 = eval_at_point(pk1_list, 1)                                           # +2 -> 22
    V2p1 = eval_at_point(pk2_list, 1)
    feats += [V1p1/(q/2), V2p1/(q/2)]
    return np.array(feats, float).reshape(1, -1)

def extract_features_v20(pk1_list, pk2_list):
    # 20维（v22 去掉 x=+1 的两维）
    feats = []
    V1m1 = eval_at_point(pk1_list, -1)
    V2m1 = eval_at_point(pk2_list, -1)
    mc, minF, minDelta = smallF_candidates_intersection(V1m1, V2m1, R_smallF)
    s, bestF = smallF_score(V1m1, V2m1, R_smallF)
    feats += [mc, minF, minDelta, s, (bestF if bestF else 0)]
    feats += [ratio_consistency(V1m1, V2m1, B_ratio)]
    feats += [V1m1/(q/2), V2m1/(q/2)]
    feats += coeff_stats_bins2(pk1_list) + coeff_stats_bins2(pk2_list)
    feats += decision_feature_absF(pk1_list, pk2_list, R_smallF)
    return np.array(feats, float).reshape(1, -1)

def expected_dim_from_models(models):
    # 对 xgboost/sklearn 模型一般有 n_features_in_
    for clf in models:
        dim = getattr(clf, "n_features_in_", None)
        if dim is not None:
            return int(dim)
    return None  # 某些场景可能拿不到，下面会用试跑兜底

# 用“自适配提取器”重写 predict_coin（或直接覆盖你原来的）

# ---- 集成概率 & 预测 ----
def ensemble_predict_proba(models, X):
    probs=[]
    for clf in models:
        if hasattr(clf,"predict_proba"):
            p = clf.predict_proba(X)[:,1]
        else:
            if hasattr(clf,"decision_function"):
                df = clf.decision_function(X)
                p = (df-df.min())/(df.max()-df.min()+1e-9)
            else:
                p = clf.predict(X).astype(float)
        probs.append(p)
    return np.mean(probs, axis=0)

def predict_coin(models, threshold, pk1_list, pk2_list):
    exp = expected_dim_from_models(models)
    # 首选：按模型给的期望维度走
    if exp == 24:
        X = extract_features_v24(pk1_list, pk2_list)
        p = ensemble_predict_proba(models, X)[0]
        return bool(p >= threshold), float(p)
    if exp == 22:
        X = extract_features_v22(pk1_list, pk2_list)
        p = ensemble_predict_proba(models, X)[0]
        return bool(p >= threshold), float(p)
    if exp == 20:
        X = extract_features_v20(pk1_list, pk2_list)
        p = ensemble_predict_proba(models, X)[0]
        return bool(p >= threshold), float(p)

    # 兜底：模型没暴露 exp 特征数，就按 v24→v22→v20 依次试谁能跑
    for builder in (extract_features_v24, extract_features_v22, extract_features_v20):
        X = builder(pk1_list, pk2_list)
        try:
            p = ensemble_predict_proba(models, X)[0]
            return bool(p >= threshold), float(p)
        except ValueError:
            continue
    raise ValueError("无法匹配特征维度：请确认训练与预测用的是同一版特征工程。")


# ---- 加载模型包 ----
def load_bundle(path="ntru_coin_xgb_bundle.pkl"):
    b = joblib.load(path)
    print(f"[+] 模型包已加载: {path}")
    return b["models"], b["threshold"]

# ================== 示例用法 ==================
if __name__ == "__main__":
    from tqdm import trange
    def sample(rand):
        return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))
    from sage.misc import prandom


    models, threshold = load_bundle("ntru_coin_xgb_bundle.pkl")

    def GenNTRU_once():
        while True:
            f  = [sample(prandom) for _ in range(n)]
            g1 = [sample(prandom) for _ in range(n)]
            g2 = [sample(prandom) for _ in range(n)]
            fx  = Q(f); g1x = Q(g1); g2x = Q(g2)
            try:
                h1 = (g1x / fx).lift()
                h2 = (g2x / fx).lift()
                return [int(c) % q for c in h1.list()], [int(c) % q for c in h2.list()]
            except Exception:
                continue

    def RandPK_once():
        pk1 = Q.random_element().lift()
        pk2 = Q.random_element().lift()
        return [int(c) % q for c in pk1.list()], [int(c) % q for c in pk2.list()]

    T = []
    S = []
    # pk1_pos, pk2_pos = GenNTRU_once()
    # pred_pos, p_pos = predict_coin(models, threshold, pk1_pos, pk2_pos)
    # pk1_neg, pk2_neg = RandPK_once()
    # pred_neg, p_neg = predict_coin(models, threshold, pk1_neg, pk2_neg)
    # print(f"[Sanity] coin=0 -> {pred_pos}, p={p_pos:.4f}")
    # print(f"[Sanity] coin=1 -> {pred_neg}, p={p_neg:.4f}")
    if 0:
        for _ in trange(10000):
            coin = randint(0, 1)
            T += [coin]
            if coin:
                pk1_pos, pk2_pos = GenNTRU_once()
                pred_pos, pp = predict_coin(models, threshold, pk1_pos, pk2_pos)
            else:
                pk1_neg, pk2_neg = RandPK_once()
                pred_neg, pp = predict_coin(models, threshold, pk1_neg, pk2_neg)
                
            # print(f"[Sanity] coin=0 -> {pred_pos}, p={p_pos:.4f}")
            # print(f"[Sanity] coin=1 -> {pred_neg}, p={p_neg:.4f}")
            if pp > .65:
                S += [1]
            else: S +=[0]

        cor = 0
        for i, j in zip(T, S):
            if i == j:
                cor += 1

        print(cor)
        print(cor / 10000)

    if 1:
        from pwn import process, remote

        # r = process(['python', 'chal.py'])
        r = remote('39.106.47.249', 36893)

        coins = []
        # r.interactive()
        for _ in trange(20258):
            r.sendlineafter(b'c :', b'1')
            pk12 = r.recvline().split(b': ')[-1].decode().strip()
            pk = pk12.split('] [')
            pk1 = eval(pk[0] + ']')
            pk2 = eval('[' + pk[1])
            pred_pos, pp = predict_coin(models, threshold, pk1, pk2)
            if pp > .65:
                coins += [0]
            else: coins +=[1]
        r.sendlineafter(b'c :', b'2')
        enc = eval(r.recvline().split(b': ')[-1].decode().strip())
        print(enc)
        open('output.py', 'w').write(f'coins = {coins}' + '\n' + f'enc = {enc}')

    if 1:
        from gf2bv import LinearSystem
        from gf2bv.crypto.mt import MT19937
        from Crypto.Cipher import AES
        from Crypto.Hash import SHA256
        from output import coins, enc

        def mt19937(bs, out):
            lin = LinearSystem([32] * 624)
            mt = lin.gens()

            rng = MT19937(mt)
            zeros = []
            for o in out:
                zeros.append(rng.getrandbits(bs) ^ int(o))
            zeros.append(mt[0] ^ int(0x80000000))
            sols = lin.solve_all(zeros)
            for sol in sols:
                rng = MT19937(sol)
                pyrand = rng.to_python_random()
                yield pyrand

        coins = coins[:20000] # It seems unnecessary
        print('go')
        for rng in mt19937(1, coins):
            print('end')
            for _ in range(20258):
                rng.getrandbits(1)
            key = str(rng.getrandbits(256)).encode()
            SHA = SHA256.new()
            SHA.update(key)
            KEY = SHA.digest()
            cipher = AES.new(KEY, AES.MODE_ECB)
            print(cipher.decrypt(enc))

*theorezhnp

题目

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
from Crypto.Cipher import AES
from ecdsa import NIST521p
from ecdsa.ecdsa import Public_key
from ecdsa.ellipticcurve import Point 
from random import randrange
from sys import stdin
from hashlib import *
from secret import seed_token, flag
import time, signal

signal.alarm(600)

def read(l):
    return stdin.read(l + 1).strip()

def pr(msg, key=None):
    if not key:
        print(msg)
    else:
        key = sha256(str(key).encode()).digest()
        print(AES.new(key, AES.MODE_ECB).encrypt(msg.encode()).hex())

def inp():
    try:
        return Point(E, int(read(131), 16), int(read(131), 16))
    except:
        pass
    return None

def DH(priv, pub):
    shared = priv * pub
    return shared.x()

token = input("Please input your team token: ")

if not token:
    exit()

def generate_token(seed, token):  
    return sha256((seed + '&' + sha1(token[::-1].encode()).hexdigest()[:10]).encode()).hexdigest()

to_encrypted_token = generate_token(seed_token, token)

E = NIST521p.curve
G = NIST521p.generator  
m = 235
n = G.order() 
Alice_sk = randrange(n)
Alice_pk = Public_key(G, Alice_sk * G).point
pr(f'Hi, Bob! Here is my public key: {Alice_pk.x() :x}')

Bob_sk = randrange(n)
Bob_pk = Public_key(G, Bob_sk * G).point
pr(f'Hi, Alice! Here is my public key: {Bob_pk.x() :x}')

shared_AB = DH(Alice_sk, Bob_pk)
shared_BA = DH(Bob_sk, Alice_pk)
assert shared_AB == shared_BA

pr('Now, it is your turn:')
for _ in range(19):
    Mallory_pk = inp()
    if not Mallory_pk:
        pr('Invalid pk!')
        exit()
    shared_AC = DH(Alice_sk, Mallory_pk)
    pr(f'Leak: {shared_AC >> m :x}')

pr(to_encrypted_token, shared_AB) 

pr("Give me your token:")
Guess_Token = input() 
if Guess_Token == to_encrypted_token:
    pr("Win for flag: " + flag)
else:
    pr("You Lose")

不会