强网杯 2025 - Zsm's blog

前言#

感觉今年比去年难了好多 xd，有种力不从心的感觉了。。。

题目#

check-little#

task.py

1
from Crypto.Util.number import *
2
from Crypto.Util.Padding import pad
3
from Crypto.Cipher import AES
4
import os
5

6
flag, key = open('secret').read().split('\n')
7

8
e = 3
9

10
while 1:
11
    p = getPrime(1024)
12
    q = getPrime(1024)
13
    phi = (p - 1) * (q - 1)
14
    if phi % e != 0:
15
        break
16
N = p * q
17
c = pow(key, e, N)
18

19
iv = os.urandom(16)
20
ciphertext = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).encrypt(pad(flag.encode(),16)).hex()
21

22
f = open('output.txt', 'w')
23
f.write(f'N = {N}\n')
24
f.write(f'c = {c}\n')
25
f.write(f'iv = {iv}\n')
26
f.write(f'ciphertext = {ciphertext}\n')

正常人拿到这玩意肯定想小 e 攻击的，发现出不来就加上爆破呗，然后发现还是不行。nmd 是哪个人的 key 是 p 啊？还是 GCD 求出来的

exp.py

1
from Crypto.Util.number import *
2
from Crypto.Cipher import AES
3
import gmpy2
4

5
N =
6
c =
7
iv =
8
ciphertext =
9
e = 3
10

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

16
aes = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC)
17
flag = aes.decrypt(bytes.fromhex(ciphertext))
18
print(flag)

ezran#

task.py

1
from Crypto.Util.number import *
2
from random import *
3

4
f = open('flag.txt', 'r')
5
flag = f.read().encode()
6

7
gift=b''
8
for i in range(3108):
9
    r1 = getrandbits(8)
10
    r2 = getrandbits(16)
11
    x=(pow(r1, 2*i, 257) & 0xff) ^ r2
12
    c=long_to_bytes(x, 2)
13
    gift+=c
14

15
m = list(flag)
16
for i in range(2025):
17
    shuffle(m)
18

19
c = "".join(list(map(chr,m)))
20

21
f = open('output.txt', 'w')
22
f.write(f"gift = {bytes_to_long(gift)}\n")
23
f.write(f"c = {c}\n")

看见题目先搜到了鸡块的一个题，2024-同济大学第二届网络安全新生赛 CatCTF-wp-crypto，这里第一开始尝试拿博客中的板子去进行矩阵恢复，但是发现恢复出来的中间的 state 是错误的，貌似需要调整并且爆破。

这里翻以前的文章找到了gf2bv这个库，发现solve_all可以求出全部解，那我们只需要索引重新 shuffle2025 次就行了。这里喂给 ai 稍微爆破一点点

exp.py

1
import struct
2
from tqdm import tqdm
3
from random import Random
4
from Crypto.Util.number import long_to_bytes, bytes_to_long
5
from sage.all import *
6
from gf2bv import LinearSystem
7
from gf2bv.crypto.mt import MT19937
8

9
def recover_mt_state(observed_outputs):
10
    system = LinearSystem([32] * 624)
11
    mt_state_vars = system.gens()
12
    mt_instance = MT19937(mt_state_vars)
13
    constraint_list = []
14
    for output_byte in observed_outputs:
15
        mt_instance.getrandbits(8)
16
        rand_16bit = mt_instance.getrandbits(16)
17
        constraint_list.append((rand_16bit >> 8) ^ int(output_byte))
18
    constraint_list.append(mt_state_vars[0] ^ 0x80000000)
19
    solutions = system.solve_all(constraint_list)
20
    return solutions
21

22
def decrypt_ciphertext(mt_seed, encrypted_text):
23
    mt_rng = MT19937(mt_seed)
24
    python_rng = mt_rng.to_python_random()
25

26
    current_state = python_rng.getstate()[1][:-1]
27
    restored_state = current_state + (len(current_state),)
28
    python_rng.setstate((3, restored_state, None))
29
    for _ in range(3108):
30
        python_rng.getrandbits(8)
31
        python_rng.getrandbits(16)
32
    indices = list(range(len(encrypted_text)))
33

34
    for iteration in range(2025):
35
        python_rng.shuffle(indices)
36

37
    decrypted = []
38
    for position in range(len(encrypted_text)):
39
        original_pos = indices.index(position)
40
        decrypted.append(encrypted_text[original_pos])
41

42
    return ''.join(decrypted)
43

44

45
ENCRYPTED_MESSAGE =
46
GIFT_VALUE =
47

48
def main_execution():
49
    gift_bytes = long_to_bytes(int(GIFT_VALUE)) if GIFT_VALUE else b""
50
    processed_gifts = []
51
    byte_pairs = [gift_bytes[i:i+2] for i in range(0, len(gift_bytes), 2)]
52

53
    for pair in byte_pairs:
54
        numeric_value = bytes_to_long(pair)
55
        processed_gifts.append(numeric_value >> 8)
56

57
    recovered_states = recover_mt_state(processed_gifts)
58

59
    for state_candidate in recovered_states:
60
        decrypted_result = decrypt_ciphertext(state_candidate, ENCRYPTED_MESSAGE)
61
        print(f"解密结果: {decrypted_result}")
62

63
if __name__ == "__main__":
64
    main_execution()

sk(*)#

task.py

1
from random import randint
2
from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
3
from math import gcd
4
import signal
5
from secret import flag
6

7

8
def gen_coprime_num(pbits):
9
  lbits = 2 * pbits + 8
10
  lb = 2**lbits
11
  ub = 2 ** (lbits + 1)
12
  while True:
13
    r = randint(lb, ub)
14
    s = randint(lb, ub)
15
    if gcd(r, s) == 1:
16
      return r, s
17

18

19
def mult_mod(A, B, p):
20
  result = [0] * (len(A) + len(B) - 1)
21
  for i in range(len(A)):
22
    for j in range(len(B)):
23
      result[i + j] = (result[i + j] + A[i] * B[j]) % p
24

25
  return result
26

27

28
def gen_key(p):
29
  f = [randint(1, 2**128) for i in ":)"]
30
  h = [randint(1, 2**128) for i in ":("]
31

32
  R1, S1 = gen_coprime_num(p.bit_length())
33
  R2, S2 = gen_coprime_num(p.bit_length())
34

35
  B = [[randint(1, p - 1) for i in ":("] for j in ":)"]
36

37
  P = []
38
  for b in B:
39
    P.append(mult_mod(f, b, p))
40

41
  Q = []
42
  for b in B:
43
    Q.append(mult_mod(h, b, p))
44

45
  for i in range(len(P)):
46
    for j in range(len(P[i])):
47
      P[i][j] = P[i][j] * R1 % S1
48
      Q[i][j] = Q[i][j] * R2 % S2
49

50
  sk = [(R1, S1), (R2, S2), f, h, p]
51
  pk = [P, Q, p]
52

53
  return sk, pk
54

55

56
def encrypt(pk, pt):
57
  P, Q, p = pk
58
  pt = bytes_to_long(pt)
59

60
  PP = 0
61
  QQ = 0
62

63
  for i in range(len(P)):
64
    u = randint(1, p)
65
    for j in range(len(P[0])):
66
      PP = PP + P[i][j] * (u * pt**j % p)
67
      QQ = QQ + Q[i][j] * (u * pt**j % p)
68

69
  return PP, QQ
70

71

72
def decrypt(sk, ct):
73
  RS1, RS2, f, h, p = sk
74
  R1, S1 = RS1
75
  R2, S2 = RS2
76

77
  P, Q = ct
78
  invR1 = inverse(R1, S1)
79
  invR2 = inverse(R2, S2)
80
  P = (P * invR1 % S1) % p
81
  Q = (Q * invR2 % S2) % p
82

83
  f0q = f[0] * Q % p
84
  f1q = f[1] * Q % p
85
  h0p = h[0] * P % p
86
  h1p = h[1] * P % p
87

88
  a = f1q + p - h1p % p
89
  b = f0q + p - h0p % p
90

91
  pt = -b * inverse(a, p) % p
92
  pt = long_to_bytes(pt)
93

94
  return pt
95

96

97
if __name__ == "__main__":
98
  # signal.alarm(30)
99
  p = getPrime(256)
100
  sk, pk = gen_key(p)
101
  ticket = long_to_bytes(randint(1, p))
102
  enc_ticket = encrypt(pk, ticket)
103
  print(pk)
104
  print(enc_ticket)
105

106
  for i in range(2):
107
    op = int(input("op>").strip())
108
    if op == 1:
109
      msg = input("pt:").strip().encode()
110
      ct = encrypt(pk, msg)
111
      print(f"ct: {ct}")
112
    elif op == 2:
113
      user_input = input("ct:").strip().split(" ")
114
      if len(user_input) == 2:
115
        ct = [int(user_input[0]), int(user_input[1])]
116
      else:
117
        print("invalid ct.")
118
        break
119

120
      user_input = input("your f:").strip().split(" ")
121
      if len(user_input) == 2:
122
        user_f = [int(user_input[0]), int(user_input[1])]
123
      else:
124
        print("invalid f.")
125
        break
126

127
      user_input = input("your h:").strip().split(" ")
128
      if len(user_input) == 2:
129
        user_h = [int(user_input[0]), int(user_input[1])]
130
      else:
131
        print("invalid h.")
132
        break
133

134
      user_input = input("your R1 S1:").strip().split(" ")
135
      if len(user_input) == 2:
136
        user_r1s1 = [int(user_input[0]), int(user_input[1])]
137
      else:
138
        print("invalid R1 S1.")
139
        break
140

141
      user_input = input("your R2 S2:").strip().split(" ")
142
      if len(user_input) == 2:
143
        user_r2s2 = [int(user_input[0]), int(user_input[1])]
144
      else:
145
        print("invalid R2 S2.")
146
        break
147

148
      pt = decrypt((user_r1s1, user_r2s2, user_f, user_h, p), ct)
149
      if pt == ticket:
150
        print(flag)
151
      else:
152
        print(pt.hex())
153
    else:
154
      print("invalid op.")
155
      break
156

157
  print("bye!")

这个题主要的加密就是

1
def encrypt(pk, pt):
2
  P, Q, p = pk
3
  pt = bytes_to_long(pt)
4

5
  PP = 0
6
  QQ = 0
7

8
  for i in range(len(P)):
9
    u = randint(1, p)
10
    for j in range(len(P[0])):
11
      PP = PP + P[i][j] * (u * pt**j % p)
12
      QQ = QQ + Q[i][j] * (u * pt**j % p)
13

14
  return PP, QQ

PP = \sum_{i=0}^{1} \sum_{j=0}^{2} P_{i,j} \cdot (u^i \cdot pt^j \bmod p) \\ QQ = \sum_{i=0}^{1} \sum_{j=0}^{2} Q_{i,j} \cdot (u^i \cdot pt^j \bmod p)

在这两个式子里面，我们知道 $P_{i,j}$ 还有 $Q_{i,j}$ ，后面的那一堆可以认为是小参数，我们可以通过格去恢复，然后再恢复 pt。

exp.py

1
from sage.all import *
2
from pwn import *
3
import ast
4
from Crypto.Util.number import *
5

6
context.log_level = "debug"
7
io = process(["python", "task.py"])
8
io.sendlineafter(b"team token", "".encode())
9
P, Q, p = ast.literal_eval(io.recvline().decode().lstrip(":"))
10
pp, qq = ast.literal_eval(io.recvline().decode())
11
v_p = vector(ZZ, (P[0] + P[1] + [-pp] + [0]))
12
v_q = vector(ZZ, (Q[0] + Q[1] + [0] + [-qq]))
13
M = identity_matrix(ZZ, len(v_p))
14
M = M.augment(matrix(ZZ, [v_p, v_q]).transpose())
15
M[:, -2:] *= 2**384
16
L = M.LLL()
17
res = None
18
for row in L:
19
  if row[-2] == 0 and row[-1] == 0 and row[-3] == 1 and row[-4] == 1:
20
    print("[+] Found!")
21
    res = row
22
    break
23
assert res is not None
24
w00, w01, w02, w10, w11, w12 = res[:6]
25

26
m = (w01 * inverse(w00, p)) % p
27
print(m)
28
io.recvuntil(b"op>")
29
io.sendline(b"2")
30
io.sendline(f"1 {m}".encode())
31
io.sendline(b"1 0")
32
io.sendline(b"0 1")
33
io.sendline(f"1 {p}".encode())
34
io.sendline(f"1 {p}".encode())
35
io.interactive()

看很多师傅的博客都是用 cuso 去打的，关键部分是

1
upt0, upt1, upt2, upt3, upt4, upt5 = var('upt0, upt1, upt2, upt3, upt4, upt5')
2
f1 = P[0][0]*upt0 + P[0][1]*upt1 + P[0][2]*upt2 + P[1][0]*upt3 + P[1][1]*upt4 + P[1][2]*upt5 - PP
3
f2 = Q[0][0]*upt0 + Q[0][1]*upt1 + Q[0][2]*upt2 + Q[1][0]*upt3 + Q[1][1]*upt4 + Q[1][2]*upt5 - QQ
4

5
relations = [f1,f2]
6
bounds = {upt0:(0, 2**256), upt1:(0,p), upt2:(0,p), upt3:(0,2**256), upt4:(0,p), upt5:(0,p)}
7
roots = find_small_roots(
8
    relations,
9
    bounds,
10
)

这样去求解，感觉得学一下 cuso 了，和这个相比自己有点像原始人

Blurred(*)#

task.py

1
from sage.all import *
2
from sage.misc import prandom
3
import random
4
from Crypto.Cipher import AES
5
from Crypto.Hash import SHA256
6
from Crypto.Util.Padding import pad
7

8
q = 1342261
9
n = 1031
10
PR = PolynomialRing(Zmod(q), "x")
11
x = PR.gens()[0]
12
Q = PR.quotient(x**n + 1)
13
flag = b"flag{*****************************}"
14

15
def sample(rand):
16
    return (rand.getrandbits(1) - rand.getrandbits(1)) * (rand.getrandbits(1) * rand.getrandbits(1))
17

18

19
def GenNTRU():
20
    f = [sample(prandom) for _ in range(n)]
21
    g1 = [sample(prandom)for _ in range(n)]
22
    g2 = [sample(prandom) for _ in range(n)]
23
    g1x = Q(g1)
24
    g2x = Q(g2)
25

26
    while True:
27
        fx = Q(f)
28
        try:
29
            h1 = g1x / fx
30
            h2 = g2x / fx
31
            return (h1.lift(), h2.lift(), fx)
32
        except:
33
            prandom.shuffle(f)
34
            continue
35

36
for _ in range(20259):
37
    c = int(input("c :"))
38
    if c == 1:
39
        coin = random.getrandbits(1)
40
        if coin == 0:
41
            pk1, pk2, fx = GenNTRU()
42
        else:
43
            pk1, pk2, fx = Q.random_element().lift(), Q.random_element().lift(), Q([sample(prandom) for _ in range(n)])
44

45
        print("Hints:", pk1.list(), pk2.list())
46

47
    elif c == 2:
48
        SHA = SHA256.new()
49
        SHA.update(str(random.getrandbits(256)).encode())
50
        KEY = SHA.digest()
51
        cipher = AES.new(KEY, AES.MODE_ECB)
52
        flag = pad(flag, AES.block_size)
53
        print("Flag:", cipher.encrypt(flag))
54
    else:
55
        break

很明显的思路是收集一堆 bit 去打 mt19937，但是有个 ntru 是真的不会了。

这里 copy 一下shin师傅的思路

首先会有

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

又因为在环 R 上面，-1 的时候就是 g(-1)，那么就只剩下了一个简单的格了

\left( \begin{array}{ccc} 1 & H_1 & H_2 \\ 0 & -p & 0 \\ 0 & 0 & -p \end{array} \right)

我们求第一行就行，同时 NTRU 出来的值比较小，取 100 为界限即可，并且不允许有一个 bit 错误，所以 01 都要考虑。

1
from sage.all import *
2
from pwn import *
3
from tqdm import trange
4
from gf2bv import LinearSystem
5
from gf2bv.crypto.mt import MT19937
6
from Crypto.Util.number import *
7
from Crypto.Cipher import AES
8
from Crypto.Hash import SHA256
9

10

11
q = 1342261
12
n = 1031
13
PR = PolynomialRing(Zmod(q), "x")
14
x = PR.gens()[0]
15
Q = PR.quotient(x**n + 1)
16

17
sh = process(["python", "task.py"])
18

19
bits = []
20
for i in trange(19968):
21
    sh.sendlineafter(b"c :",b'1')
22
    res = sh.recvline().strip().decode().split(':')[-1]
23
    start1 = res.find('[')
24
    end1 = res.find(']')
25
    h1 = Q(eval(res[start1:end1+1]))
26
    start2 = res.find('[',end1)
27
    end2 = res.find(']',end1+1)
28
    h2 = Q(eval(res[start2:end2+1]))
29
    h1_value = h1.lift()(-1)
30
    h2_value = h2.lift()(-1)
31
    L = Matrix(ZZ,[
32
        [1,h1_value,h2_value],
33
        [0,-q,0],
34
        [0,0,-q]
35
    ])
36
    line = L.LLL()[0]
37
    if int(line.norm()) < 100:
38
        bits.append(0)
39
    else:
40
        bits.append(1)
41

42
sh.sendlineafter(b"c :",b'2')
43
sh.recvuntil(b"Flag: ")
44
enc_flag = eval(sh.recvline().strip())
45
print(f"enc_flag = {enc_flag}")
46
print(f"bits = {bits}")
47

48
def mt19937(out, ch):
49
    hig = [int(0x00000000), int(0x80000000)]
50
    lin = LinearSystem([32] * 624)
51
    mt = lin.gens()
52

53
    rng = MT19937(mt)
54
    zeros = []
55
    for o in out:
56
        zeros.append(rng.getrandbits(1) ^ int(o))
57
    zeros.append(mt[0] ^ hig[ch])
58

59
    for sol in lin.solve_all(zeros):
60
        rng = MT19937(sol)
61
        pyrand = rng.to_python_random()
62
        RNG = pyrand
63
        STATE = RNG.getstate()[1][:-1]
64
        STATE = STATE + (len(STATE),)
65
        RNG.setstate((3,STATE,None))
66

67
        for i in trange(19968):
68
            RNG.getrandbits(1)
69

70
        SHA = SHA256.new()
71
        SHA.update(str(RNG.getrandbits(256)).encode())
72
        KEY = SHA.digest()
73
        cipher = AES.new(KEY, AES.MODE_ECB)
74
        flag = cipher.decrypt(enc_flag)
75
        if b"flag" in flag:
76
            print(f"high = {ch}")
77
            print(f"{flag = }")
78

79
RNG = mt19937(bits, 0)
80
RNG = mt19937(bits, 1)

总结#

感觉自己还是太菜了，迟迟摸不到强者的尾气。。。害，也快退役了，不甘心啊。。。

后面可能做密码越来越少了，毕竟没有考研的打算，可能还是会走 web 或者是开发吧。。。安服好像也不是不行？总之先为了工作吧。。。

a ctfer on the load

前言#

题目#

check-little#

ezran#

sk(*)#

Blurred(*)#

总结#