2025.9-切题

发表于

又是月末了，该找个题目水 blog 了。

这个月基本是没有打过 CTF 的，但是看着之前每月都更了blog，就想着去随便找个题目水一下。本来是打算复现完 smileyctf-2025 的flcg 然后去写 blog 的，但是这个比赛似乎过去有点久了。但是就在前几天，开了一个叫 skateboarding dog CTF，然后 @LOV3 喊着我们去看看，但是当时是放假了所以就没看。赛后看了下最后的那个题目，发现还是有点难度的正好可以水一下 blog。(●'◡'●)

hidden number pawblem

描述

1
2
3
I encrypted my flag with a bunch of primes, but I've lost not only the primes but also the ciphertext itself. Can you help me recover it?

Author: Neobeo

题目

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
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES

FLAG = b"skbdg{?????????????????????????????????????????}"
assert len(FLAG) == 48

primes = [getPrime(128) for _ in range(3)]
modulus = getPrime(128)

key = long_to_bytes(primes[0] ^ primes[1] ^ primes[2] ^ modulus)
aes = AES.new(key, AES.MODE_ECB)
encrypted_flag = aes.encrypt(FLAG)

tmps = []
es = []
for i in range(16):
    tmp = sum(e*p for e,p in zip(encrypted_flag[i::16], primes))
    print(tmp % modulus)

'''
150446291068140049563320772229191257428
30274497893933825999264440472646873791
43867575705590228789129962680194301102
215435877342780673372868219690346172147
99919967040475127359053542571984408741
1418241424975041702003923185520387792
185934806776900279451263515202940787830
9915399472284561223892051362047539015
128538985168972255782337580802434396984
66625731371269352564215497563133736582
208818196421195854278004492989600277886
99906814947789931207521912729518463975
71965491875756016264158124104626078247
17142191919773459556570465854141914661
79550053952325692474643350015142936377
133451730769263639095159572044716238586
'''

exp

题目基于如下式子

[p0p1p2][e0e16e32e1e17e33⋮⋮⋮e15e31e47]  ≡  [y0y1⋯y15](modm),\begin{bmatrix}p_0 &p_1& p_2\end{bmatrix}\begin{bmatrix} e_{0} & e_{16} & e_{32}\\ e_{1} & e_{17} & e_{33}\\ \vdots & \vdots & \vdots\\ e_{15} & e_{31} & e_{47} \end{bmatrix} \;\equiv\; \begin{bmatrix} y_0& y_1& \cdots& y_{15} \end{bmatrix} \pmod m,

仅仅给定了 yiy_i，要求你恢复等式的所有参数。

我们记

E=[e0e16e32e1e17e33⋮⋮⋮e15e31e47],      t=[y0y1⋯y15]E=\begin{bmatrix} e_{0} & e_{16} & e_{32}\\ e_{1} & e_{17} & e_{33}\\ \vdots & \vdots & \vdots\\ e_{15} & e_{31} & e_{47} \end{bmatrix},\;\;\;t=\begin{bmatrix} y_0& y_1& \cdots& y_{15} \end{bmatrix}

注意到任意 α∈Z16\alpha\in \mathbb Z^{16} 若满足

αTE=0,\alpha^T E = 0,

那么有

αT(Ep−t)≡0(modm)⇒m∣αTt.\alpha^T(Ep - t) \equiv 0 \pmod m \quad\Rightarrow\quad m \mid \alpha^T t.

因此只要找到 EE 的左核向量，就能构造出 mm 的倍数，取若干个这样的结果求 gcd⁡\gcd，就能够恢复出模数 mm。

而要计算 EE，就要去找 tt 的左核向量。然而实际上，直接计算 tt 得到的左核向量并不是我们想要的 ee，而是一些小的基向量。但是 ee 是在 [0,255][0,255] 范围内，所以可以考虑爆破基向量的线性组合来枚举得到 EE。

拿到 EE 以后，就可以按照上面的方式恢复 mm 了。

得到 mm 以后，在 Fm\mathbb F_m 上解矩阵方程

E⋅p≡t(modm),E \cdot p \equiv t \pmod m,

即可恢复出 (p0,p1,p2)(p_0,p_1,p_2)。

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from tqdm import trange
from sage.all import *
from itertools import product, combinations, permutations
import multiprocessing as mp

tmps = [150446291068140049563320772229191257428,
30274497893933825999264440472646873791,
43867575705590228789129962680194301102,
215435877342780673372868219690346172147,
99919967040475127359053542571984408741,
1418241424975041702003923185520387792,
185934806776900279451263515202940787830,
9915399472284561223892051362047539015,
128538985168972255782337580802434396984,
66625731371269352564215497563133736582,
208818196421195854278004492989600277886,
99906814947789931207521912729518463975,
71965491875756016264158124104626078247,
17142191919773459556570465854141914661,
79550053952325692474643350015142936377,
133451730769263639095159572044716238586]

l = len(tmps)
M = column_matrix(tmps)
Ker = M.left_kernel_matrix()
Ker = Ker[:12, :]
E = Ker.right_kernel_matrix().T

Es = []
for s1, s2, s3, s4 in product(range(-10, 11), repeat=4):
    v = E * vector([s1, s2, s3, s4])
    if all(0 <= i <= 255 for i in v):
        Es.append(v)

choices = [*combinations(range(len(Es)), r=3)]
t = len(choices)
v = vector(tmps)
def worker(begin, end):
    for idx in trange(begin,end):
        if idx >= len(choices):
            return
        e1, e2, e3 = [Es[j] for j in choices[idx]]
        modulus = gcd(column_matrix([e1, e2, e3]).left_kernel_matrix() * v)
        if isPrime(modulus) and modulus.bit_length() == 128:
            p1, p2, p3 = map(int, column_matrix(GF(modulus), [e1, e2, e3]).solve_right(v))
            if p1.bit_length() < 128:
                p1 += modulus
            if p2.bit_length() < 128:
                p2 += modulus
            if p3.bit_length() < 128:
                p3 += modulus
            if isPrime(p1) and isPrime(p2) and isPrime(p3):
                print(p1, p2, p3, modulus, e1, e2, e3)

NUM_PROCESS = 10
gap = t // NUM_PROCESS
ps = []
for x in range(NUM_PROCESS):
    p = mp.Process(target=worker, args=(gap * x, gap * (x + 1)))
    p.start()
    ps.append(p)
    
for p in ps:
    p.join()

拿到值以后就可以美美解密了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
modulus = 225589597066928478356612192118049564733
p1 = 218345485451013392433572197012850914507
p2 = 334024095181193149414939520221423878019
p3 = 312665646933474564504579136376120066273
assert isPrime(p1) and isPrime(p2) and isPrime(p3) and isPrime(modulus) and all(i.bit_length() == 128 for i in [p1, p2, p3, modulus]) 
e1 = (245, 190, 32, 125, 141, 136, 39, 100, 20, 20, 85, 112, 103, 166, 104, 174)
e2 = (46, 186, 237, 166, 106, 48, 23, 179, 115, 28, 93, 168, 134, 88, 61, 113)
e3 = (84, 212, 164, 73, 70, 107, 127, 156, 176, 180, 189, 208, 213, 78, 102, 124)
key = long_to_bytes(p1 ^ p2 ^ p3 ^ modulus)
aes = AES.new(key, AES.MODE_ECB)

for E in permutations([e1, e2, e3], r=3):
    print(aes.decrypt(bytes(sum([list(v) for v in E], []))))
    
# b'skbdg{congrats_you_have_mastered_both_OL_and_LP}'

但是看到 flag 是基于 OL 和 LP，那就很显然计算 ee 的方式本意并不是靠爆破，不过这个以后再说了。 (¬‿¬)