2025强网杯

发表于 阅读次数： Waline： 本文字数： 3.2k 阅读时长 ≈ 12 分钟

记录2025强网杯——Crypto题解（除0解题外）

最后排名 40，有过高光，但最后还是太遗憾了，从Blurred这题重新上线后一直到比赛结束没能肝出来，赛后尝试了一下赛中没尝试过的思路一下就出了。

check-little

task.py

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
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')
"""
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2
"""

学弟用AI尝试各种方法，发现p = gcd(N,c)，解密即可

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from Crypto.Cipher import AES
import gmpy2

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

p = gmpy2.gcd(c,N)
q = N // p
d = inverse(e,(p-1)*(q-1))
key = pow(c,d,N)

aes = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC)
flag = aes.decrypt(bytes.fromhex(ciphertext))
print(flag)
# flag{m_m4y_6e_divIS1b1e_by_p?!}

ezran

task.py

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

x=(pow(r1, 2*i, 257) & 0xff) ^ r2由于进行了 &ff，所以这个值小于256，那么异或就不影响r2的高8bit，3108 * 8 > 19968，足够恢复state，这里没用造矩阵的形式做，用的是gf2bv，存在多解的可能，所以用的是solve_all()，恢复state之后找一下shuffle2025次的映射即可求出

exp.py

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 gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from Crypto.Util.number import *
from tqdm import *
from random import *
import sys

sys.set_int_max_str_digits(20000)
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()
        RNG = pyrand
        STATE = RNG.getstate()[1][:-1]
        STATE = STATE + (len(STATE),)

        RNG.setstate((3,STATE,None))
        for i 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.startswith("flag{"):
            print(flag)
            return
        
gift = ""
gift = int(gift)
c = ")9Lsu_4s_eb__otEli_nhe_tes5gii5sT@omamkn__ari{efm0__rmu_nt(0Eu3_En_og5rfoh}nkeoToy_bthguuEh7___u"
gift_bytes = long_to_bytes(gift)

gift_list = []
for i in range(0, len(gift_bytes), 2):
    chunk = gift_bytes[i:i+2]
    gift_list.append(bytes_to_long(chunk) >> 8)
    
mt19937(16, gift_list)

sk

task.py

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
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!")

先生成两个 $2\times 3$的矩阵 P,Q，加密的数学逻辑为
$$
PP = P_{0,0}\cdot (u_0 \mod p) + P_{0,1}\cdot (u_0m\mod p) + P_{0,2}\cdot (u_0m^2\mod p) + P_{1,0}\cdot (u_1 \mod p) + P_{1,1}\cdot (u_1m\mod p) + P_{1,2}\cdot (u_1m^2 \mod p)
$$

$$
QQ = Q_{0,0}\cdot (u_0\mod p) + Q_{0,1}\cdot (u_0m\mod p) + Q_{0,2}\cdot (u_0m^2\mod p) + Q_{1,0}\cdot (u_1\mod p) + Q_{1,1}\cdot (u_1m \mod p) + Q_{1,2}\cdot (u_1m^2 \mod p)
$$

记$r_{0,0} = u_0 \mod p$，$r_{0,1} = u_0m \mod p$，$r_{0,2} = u_0m^2 \mod p$

$r_{1,0} = u_1 \mod p$，$r_{1,1} = u_1m \mod p$，$r_{1,2} = u_1m^2 \mod p$

于是有
$$
PP = P_{0,0}r_{0,0} + P_{0,1}r_{0,1} + P_{0,2}r_{0,2} + P_{1,0}r_{1,0} + P_{1,1}r_{1,1} + P_{1,2}r_{1,2}\mod p
$$

$$
QQ = Q_{0,0}r_{0,0} + Q_{0,1}r_{0,1} + Q_{0,2}r_{0,2} + Q_{1,0}r_{1,0} + Q_{1,1}r_{1,1} + Q_{1,2}r_{1,2} \mod p
$$

$r_{i,j}$都是小量，用cuso可以求出所有 $r_{i,j}$，求出来之后就能得到 m，然后用 p再生成私钥和公钥，自己走一遍加密流程，向服务器发送这些值。

解法1：cuso

exp.py

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
from cuso import find_small_roots
from Crypto.Util.number import *
from math import gcd
from random import randint
from pwn import *


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

sh = remote("47.104.146.31",7777)

context.log_level = 'debug'
token = ""
sh.sendlineafter(b"team token:",token.encode())
pk = eval(sh.recvline().strip().decode())
enc_ticket = eval(sh.recvline().strip().decode())

P,Q,p = pk
PP,QQ = enc_ticket

r00,r01,r02,r10,r11,r12 = var('r00,r01,r02,r10,r11,r12')
f1 = P[0][0]*r00 + P[0][1]*r01 + P[0][2]*r02 + P[1][0]*r10 + P[1][1]*r11 + P[1][2]*r12 - PP
f2 = Q[0][0]*r00 + Q[0][1]*r01 + Q[0][2]*r02 + Q[1][0]*r10 + Q[1][1]*r11 + Q[1][2]*r12 - QQ

relations = [f1,f2]
bounds = {r00: (0, 2**256),r01: (0,p),r02 : (0,p),r10: (0,2**256),r11: (0,p),r12: (0,p)}
roots = find_small_roots(
    relations,
    bounds,
)
    
for root in roots:
    u0 = root[r00]
    u1 = root[r10]
    m1 = root[r01] * inverse(u0,p) % p
    m2 = root[r11] * inverse(u1,p) % p
    if m1 == m2:
        print(m1)
        sk1, pk1 = gen_key(p)
        RS1, RS2, f, h, pp = sk1
        R1,S1 = RS1
        R2,S2 = RS2
        ct1 = encrypt(pk1,long_to_bytes(m1))
        sh.sendlineafter(b"op>",b'2')
        sh.sendlineafter(b"ct:",f"{ct1[0]} {ct1[1]}".encode())
        sh.sendlineafter(b"your f:",f"{f[0]} {f[1]}".encode())
        sh.sendlineafter(b"your h:",f"{h[0]} {h[1]}".encode())
        sh.sendlineafter(b"your R1 S1:",f"{R1} {S1}".encode())
        sh.sendlineafter(b"your R2 S2:",f"{R2} {S2}".encode())
        print(sh.recvline().strip().decode())

解法2：造格

根据上面的等式造这样的格
$$
\begin{bmatrix}
r_{0,0} & r_{0,1} & r_{0,2} & r_{1,0} & r_{1,1} & r_{1,2} & -1 & -1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & P_{0,0} & Q_{0,0}\\
0 & 1 & 0 & 0 & 0 & 0 & P_{0,1} & Q_{0,1}\\
0 & 0 & 1 & 0 & 0 & 0 & P_{0,2} & Q_{0,2}\\
0 & 0 & 0 & 1 & 0 & 0 & P_{1,0} & Q_{1,0}\\
0 & 0 & 0& 0 & 1 & 0 & P_{1,1} & Q_{1,1}\\
0 & 0 & 0 & 0& 0 & 1 & P_{1,2} & Q_{1,2}\\
0 & 0 & 0& 0& 0& 0& PP & 0\\
0&0 & 0& 0 &0&0 &0 & QQ
\end{bmatrix} =
\begin{bmatrix}
r_{0,0} & r_{0,1} & r_{0,2} & r_{1,0} & r_{1,1} & r_{1,2} & 0 & 0
\end{bmatrix}
$$

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
from Crypto.Util.number import *
from math import gcd
from random import randint
from pwn import *

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

sh = remote("47.104.146.31",7777)

context.log_level = 'debug'
token = ""
sh.sendlineafter(b"team token:",token.encode())
pk = eval(sh.recvline().strip().decode())
enc_ticket = eval(sh.recvline().strip().decode())

P,Q,p = pk
PP,QQ = enc_ticket

L = Matrix(ZZ,[
    [1,0,0,0,0,0,P[0][0],Q[0][0]],
    [0,1,0,0,0,0,P[0][1],Q[0][1]],
    [0,0,1,0,0,0,P[0][2],Q[0][2]],
    [0,0,0,1,0,0,P[1][0],Q[1][0]],
    [0,0,0,0,1,0,P[1][1],Q[1][1]],
    [0,0,0,0,0,1,P[1][2],Q[1][2]],
    [0,0,0,0,0,0,PP,0],
    [0,0,0,0,0,0,0,QQ]
])
L[:,-2:] *= 2^1000
for line in L.LLL():
    u0 = line[0] % p
    u1 = line[3] % p
    u0_m = line[1] % p
    u1_m = line[4] % p
    m1 = u0_m * inverse(u0,p) % p
    m2 = u1_m * inverse(u1,p) % p
    if m1 == m2:
        new_sk, new_pk = gen_key(p)
        RS1, RS2, f, h, pp = new_sk
        R1,S1 = RS1
        R2,S2 = RS2
        new_ct = encrypt(new_pk,long_to_bytes(m1))
        sh.sendlineafter(b"op>",b'2')
        sh.sendlineafter(b"ct:",f"{new_ct[0]} {new_ct[1]}".encode())
        sh.sendlineafter(b"your f:",f"{f[0]} {f[1]}".encode())
        sh.sendlineafter(b"your h:",f"{h[0]} {h[1]}".encode())
        sh.sendlineafter(b"your R1 S1:",f"{R1} {S1}".encode())
        sh.sendlineafter(b"your R2 S2:",f"{R2} {S2}".encode())
        print(sh.recvline().strip().decode())

Blurred——复现

task.py

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

思路很清晰，区分出尽可能多的coin，然后打MT19937。

如果样本来自GenNTRU，那么有
$$
h_1(x) \equiv g_1(x)f^{-1}(x)
$$

$$
h_2(x) \equiv g_2(x)f^{-1}(x)
$$

当$x = -1$的时候，可以把环映射到整数域，也就是
$$
h_1(-1) \equiv g_1(-1)f^{-1}(-1) \mod q
$$

$$
h_2(-1) \equiv g_2(-1)f^{-1}(-1) \mod q
$$

这时候就可以当作格入门的题来做，即$fh \equiv g \mod p$，我们造这样的格
$$
\begin{bmatrix}
f & k_1 & k_2
\end{bmatrix}
\begin{bmatrix}
1 & h_1 & h_2\\
0 & q & 0\\
0 & 0 & q
\end{bmatrix}
= \begin{bmatrix}
f & g_1 & g_2
\end{bmatrix}
$$
这时候我本地测试发现，$f$会比较小，基本落在$[-20,20]$，另外一个随机的样本就没有这样的结果，所以我将区分的阈值设为20

以$n = 211$测试发现，错误率为$\frac{26}{20258}$，打远程似乎错误率高了不少，导致打MT19937没出

其实赛中的时候就想到用向量的长度做区分，但是一直以为自己的正确率足以，但事实证明正确率不够。赛后测了一下，来自GenNTRU的样本，规约出的向量长度不会很大，阈值选100就能完美区分coin

exp.py

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
from sage.all import *
from pwn import * 
from tqdm import trange
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from Crypto.Util.number 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)

# sh = remote(ip,port)
sh = process(['sage','task.py'])

bits = []
for i in trange(19968):
    sh.sendlineafter(b"c :",b'1')
    res = sh.recvline().strip().decode().split(':')[-1]
    start1 = res.find('[')
    end1 = res.find(']')
    h1 = Q(eval(res[start1:end1+1]))
    start2 = res.find('[',end1)
    end2 = res.find(']',end1+1)
    h2 = Q(eval(res[start2:end2+1]))
    h1_value = h1.lift()(-1)
    h2_value = h2.lift()(-1)
    L = Matrix(ZZ,[
        [1,h1_value,h2_value],
        [0,-q,0],
        [0,0,-q]
    ])
    line = L.LLL()[0]
    if int(line.norm()) < 100:
        coin = 0
    else:
        coin = 1
    bits.append(coin)

sh.sendlineafter(b"c :",b'2')
enc_flag = eval(sh.recvline().strip().decode().split('Flag: ')[-1].strip())
print(f"enc_flag = {enc_flag}")
print(f"bits = {bits}")

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

    rng = MT19937(mt)
    zeros = []
    for o in out:
        zeros.append(rng.getrandbits(1) ^ int(o))
    zeros.append(mt[0] ^ int(0x80000000))
    # zeros.append(mt[0] ^ int(0x00000000))
    for sol in lin.solve_all(zeros):
        rng = MT19937(sol)
        pyrand = rng.to_python_random()
        RNG = pyrand
        STATE = RNG.getstate()[1][:-1]
        STATE = STATE + (len(STATE),)
        RNG.setstate((3,STATE,None))
        for i in trange(19968):
            RNG.getrandbits(1)
        SHA = SHA256.new()
        SHA.update(str(RNG.getrandbits(256)).encode())
        KEY = SHA.digest()
        cipher = AES.new(KEY, AES.MODE_ECB)
        flag = cipher.decrypt(enc_flag)
        print(flag)

RNG = mt19937(bits)

好奇为什么给这么多交互机会，一开始以为20258次出现部分bit错误也能求解——也就是MT19937的20258个bit里面存在少部分随机位置的bit翻转可以求解，赛后实验发现，存在一个bit错误都无法求解，所以当时思路错了，应该想办法得到100%正确的coin，而不是允许部分差错。

-------------已经到底啦！-------------