四月训练赛crypto-wp

前言#

赛况惨烈，就一个有解，我服了

题目#

easy_sign#

task.py

1
from Crypto.Util.number import *
2
from flag import flag, msg
3
from gmpy2 import *
4

5
# msg中是加密flag的e
6
msg = msg + b"0" * 20
7

8

9
def gen_key(p, q):
10
    public_key = p * p * q
11
    e = public_key
12
    n = p * q
13
    phi_n = (p - 1) * (q - 1)
14
    private_key = inverse(e, phi_n)
15
    return public_key, private_key, e
16

17

18
p1 = getPrime(512)
19
q1 = getPrime(512)
20

21
N1, d1, e1 = gen_key(p1, q1)
22

23
c1 = pow(bytes_to_long(msg), e1, N1)
24

25
print("N1=", N1)
26
print("d1=", d1)
27
print("c1=", c1)
28

29

30
p2 = getPrime(128)
31
q2 = getPrime(128)
32

33
c2 = pow(bytes_to_long(flag), e, p2 * q2)
34
C = p2**2 + q2**2
35

36

37
print("c2=", c2)
38
print("C=", C)

首先看源码，很明显的两部分第一部分是 $n=p^2*q,e=n$ ,你需要知道这是Schmidt-Samoa密码系统

第二部分就更好玩了， $C = p^2 + q^2$ ,如果你有sagemath，会想到分解

但是求c却不对，这是因为这是多解问题，你可以用https://www.alpertron.com.ar/QUAD.HTM 进行计算，可以求到对的解，

也可以用sage的二元二次丢番图方程求解，进行分解

exp.py

1
N1 =
2
d1 =
3
c1 =
4

5

6
from Crypto.Util.number import *
7
from Crypto.Util.number import long_to_bytes
8
from gmpy2 import *
9

10
pq = gcd(pow(2, d1 * N1, N1) - 2, N1)
11

12
m = pow(c1, d1, pq)
13
print(long_to_bytes(m))
14

15
#e = 44519
16

17
c =
18
C =
19

20
import gmpy2
21
from Crypto.Util.number import *
22
from Crypto.Util.number import long_to_bytes
23
from gmpy2 import *
24
from sympy.abc import t, x, y
25
from sympy.solvers.diophantine.diophantine import diop_quadratic
26

27
e = 44519
28
"""
29
f = ZZ[I](C)
30
divisors_f = divisors(f)
31
for d in divisors_f:
32
    a,b = d.real(), d.imag()
33
    if a**2 + b**2 == C:
34
        p = abs(int(a))
35
        q = abs(int(b))
36
        if is_prime(p) and is_prime(q):
37
            print(p)
38
            print(q)
39
            break
40
"""
41

42
p =
43
q =
44

45
assert C == pow(p, 2) + pow(q, 2)
46
n = p * q
47
phi = (p - 1) * (q - 1)
48
d = gmpy2.invert(e, phi)
49
m = pow(c, d, n)
50

51
for i in range(0, 100000000000000):
52
    mm = m + i * n
53
    flagg = long_to_bytes(mm)
54
    if b"flag{" in flagg:
55
        print(flagg)

babybaby#

task.py

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

4
m = bytes_to_long(flag)
5
p = getStrongPrime(1024)
6
q = getStrongPrime(1024)
7
phi = (p - 1) * (q - 1)
8
e1 = inverse(getPrime(768), phi)
9
e2 = inverse(getPrime(768), phi)
10
e3 = inverse(getPrime(768), phi)
11
n = p * q
12
c = pow(m, 0x10001, n)
13
print(f"e1={e1}")
14
print(f"e2={e2}")
15
print(f"e3={e3}")
16
print(f"c={c}")
17
print(f"n={n}")

其实就是3个e的维纳拓展攻击，参数都没改的

exp.py

1
from Crypto.Util.number import*
2
e1=
3
e2=
4
e3=
5
c=
6
n=
7

8
L = matrix(ZZ, [
9
    [1, -n, 0, n**2, 0, 0, 0, -n**3],
10
    [0, e1, -e1, -n * e1, -e1, 0, n * e1, n**2 * e1],
11
    [0, 0, e2, -n * e2, 0, n * e2, 0, n**2 * e2],
12
    [0, 0, 0, e1 * e2, 0, -e1 * e2, -e1 * e2, -n * e1 * e2],
13
    [0, 0, 0, 0, e3, -n * e3, -n * e3, n**2 * e3],
14
    [0, 0, 0, 0, 0, e1 * e3, 0, -n * e1 * e3],
15
    [0, 0, 0, 0, 0, 0, e2 * e3, -n * e2 * e3],
16
    [0, 0, 0, 0, 0, 0, 0, e1 * e2 * e3]
17
])
18
# alpha = 768 / 2048
19
alpha = 2 / 5
20
D = diagonal_matrix(ZZ, [floor(pow(n, 3 / 2)), n, floor(pow(n, alpha + 3/2)), floor(pow(n, 1/2)), floor(pow(n, alpha + 3/2)), floor(pow(n, alpha + 1)), floor(pow(n, alpha + 1)), 1])
21
M = L * D
22
B = M.LLL()
23
b = vector(ZZ, B[0])
24
A = b * M^(-1)
25
phi = floor(A[1] / A[0] * e1)
26

27
d = inverse_mod(0x10001, phi)
28
m = pow(c, d, n)
29
flag = long_to_bytes(int(m))
30
print(flag)

easy_Matrix#

task.py

1
import hashlib
2
import random
3

4
from Crypto.Cipher import AES
5
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
6
from Crypto.Util.Padding import pad
7
from flag import *
8

9
p = getPrime(1024)
10

11

12
def f(x, c):
13
    r = 0
14
    for v in c:
15
        r = (r * x + v) % p
16
    return r
17

18

19
k = hashlib.sha256(flag).digest()
20
c = [bytes_to_long(k)]
21
for _ in range(29):
22
    c.append(bytes_to_long(hashlib.sha256(long_to_bytes(c[-1])).digest()))
23

24
pairs = [(x := random.randint(0, p), f(x, c)) for _ in range(20)]
25

26
iv = b"\x00" * 16
27
enc = AES.new(k, AES.MODE_CBC, iv).encrypt(pad(flag, 16))
28

29
with open("out.txt", "w") as file:
30
    file.write(f"{p=}\n{pairs=}\n{(iv.hex(), enc.hex())=}\n")

欠定方程组，导致无法直接求解，那么肯定是格了xd

稍微处理一下， $c_0 x_j^{n-1} + c_1 x_j^{n-2} + \dots + c_{n-1} x_j^0 - k_j p = y_j$

搞成矩阵

M = \left( \begin{array}{c|c|c} I_{n \times n} & W \cdot X & 0 \\ \hline 0 & W \cdot p I_{m \times m} & 0 \\ \hline 0 & -W \cdot Y & K \end{array} \right)

那么LLL之后 $v = [c_0, c_1, \dots, c_{n-1}, \underbrace{0, 0, \dots, 0}_{m \text{ zeros}}, K]$

exp.py

1
import hashlib
2
from Crypto.Cipher import AES
3
from Crypto.Util.number import long_to_bytes
4
from Crypto.Util.Padding import unpad
5

6
p=
7
pairs=[]
8
enc_flag=('00000000000000000000000000000000', '9c7264cf50c67bcbb0ee97de74c8430cf4a1047c6372ce9db22b8e53c2422db3b674ca44a25fec5b8b9adc526dd9a6c1')
9

10
m = len(pairs)
11
n = 30
12

13
W = 2^512
14
K = 2^255
15

16
M = matrix(ZZ, n + m + 1, n + m + 1)
17

18
for k in range(n):
19
    M[k, k] = 1
20
    for j in range(m):
21
        M[k, n + j] = W * power_mod(pairs[j][0], n - 1 - k, p)
22

23
for j in range(m):
24
    M[n + j, n + j] = W * p
25

26
for j in range(m):
27
    M[n + m, n + j] = -W * pairs[j][1]
28
M[n + m, n + m] = K
29

30
reduced = M.LLL()
31

32
c0 = None
33
for row in reduced:
34
    if row[n+m] == K or row[n+m] == -K:
35
        sign = 1 if row[n+m] == K else -1
36
        c0 = int(row[0] * sign)
37
        break
38

39
if c0 is not None:
40
    MASTER_KEY = long_to_bytes(c0).rjust(32, b'\x00')
41

42
    iv = bytes.fromhex(enc_flag[0])
43
    enc = bytes.fromhex(enc_flag[1])
44
    cipher = AES.new(MASTER_KEY, AES.MODE_CBC, iv)
45
    flag = unpad(cipher.decrypt(enc), 16)
46
    print("Flag:", flag.decode())
47
else:
48
    print("未能在格内找到符合条件的最短向量。")

Ez_Cu#

task.py：

1
from secret import flag
2
from Crypto.Util.number import getPrime, bytes_to_long
3

4
m = bytes_to_long(flag)
5
p = getPrime(1024)
6
q = getPrime(1024)
7
n = p * q
8
e = 65537
9
c = pow(m, e, n)
10
ph = p >> 600
11
gift = (p % (2 ** 592)) % bytes_to_long(b'The CopperSmith\'s Gift')
12
print(f"{n = }")
13
print(f"{e = }")
14
print(f"{c = }")
15
print(f"{ph = }")
16
print(f"{gift = }")

之前自己学校的比赛出过一模一样的，但是当时我们没有禁 AI，所以大家做的都还挺理想的，这题新生赛里也许是中等偏上？

small_roots()不深究原理使用的话就当成是一个模域下求解方程小根的函数工具就行。那么我们的目标就是通过给出的已知信息来建立一个方程等式来求出我们需要的小根信息。题目中给出了ph也就是p的高 424-bit，这肯定不足以直接打出p的剩下低 600-bit。

然后我们可以看看gift给出了什么：

1
gift = (p % (2 ** 592)) % bytes_to_long(b'The CopperSmith\'s Gift')

也就是说gift是p的低 592-bit 模bytes_to_long(b'The CopperSmith\'s Gift')的余数，我们测试一下可知，大约是低 175-bit。

1
from Crypto.Util.number import bytes_to_long
2

3
m = bytes_to_long(b'The CopperSmith\'s Gift')
4
print(m.bit_length(), m)
5
# 175 31580704707012293774603627903276951444456382271153780

现在来尝试把p用一个等式表达，中间缺失的 8-bit 我们用pm表示：

p=ph*2^{600}+pm*2^{592}+k*m+gift

整理一下信息，ph已知，pm仅 8-bit，m和gift已知，k大约592 - 175 = 417bit，可以直接爆破pm并用CopperSmith打出k，这样p就出来了。

exp.py：

1
import sys
2
from tqdm import trange
3
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
4

5
n =
6
e = 65537
7
c =
8
ph =
9
gift =
10
mod_ = bytes_to_long(b'The CopperSmith\'s Gift')
11
p_high = ph << 600
12
PR.<x> = PolynomialRing(Zmod(n))
13
for p_mid in trange(2 ** 8):
14
    pp = p_high + (p_mid * 2 ** 592)
15
    f = pp + x * mod_ + gift
16
    roots = f.monic().small_roots(X=2**418, beta=0.4, epsilon=0.05)
17
    if roots:
18
        for r in roots:
19
            p = int(pp + r * mod_ + gift)
20
            q = n // p
21
            assert p * q == n
22
            phi = (p - 1) * (q - 1)
23
            d = inverse(e, phi)
24
            m = pow(c, d, n)
25
            print(long_to_bytes(m).decode())
26
            sys.exit(1)
27
#  76%|█████████████████████████████████████████████████████████████▍                   | 194/256 [00:04<00:01, 47.53it/s]
28
# flag{I_th1nk_Y0u_4re_g00d_At_Copper}

Prediction#

task.py：

1
import random
2
from secret import seed, flag
3
from Crypto.Util.number import bytes_to_long
4

5
flag = bytes_to_long(flag)
6
assert flag.bit_length() == 391
7
rng = random.Random()
8
rng.seed(seed)
9
nums = [rng.getrandbits(8) for _ in range(2496)]
10
key = rng.getrandbits(391)
11
enc = flag ^ key
12
with open("output.txt", "w") as f:
13
    f.write(f"nums = {str(nums)}\n")
14
    f.write(f"enc = {enc}")

ps：说实在的，相比于今年上半年以及去年下半年的一些比赛（包括新生赛）出的 MT19937 相关的题目来说，这道题真的太基础了。

当时考虑到禁 AI 的原因，就只略加了一点点难度（也许这题有个中等叭），把randcrack库给 ban 了，但是用gf2bv还是能很轻松地打出来，这里给个老师傅的链接供大家学习，具体知识我就不细说了。

exp.py：

1
from gf2bv import LinearSystem
2
from gf2bv.crypto.mt import MT19937
3
from tqdm import *
4
import random
5
from Crypto.Util.number import *
6

7
def mt19937(bs, out):
8
    lin = LinearSystem([32] * 624)
9
    mt = lin.gens()
10
    rng = MT19937(mt)
11
    zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
12
    sol = lin.solve_one(zeros)
13
    rng = MT19937(sol)
14
    pyrand = rng.to_python_random()
15
    for i in range(2496):
16
        out.append(pyrand.getrandbits(8))
17
    return pyrand.getrandbits(391)
18

19
nums = [...]
20
enc =
21
key = mt19937(8, nums)
22
print(long_to_bytes(key ^ enc).decode())
23
# flag{P3rh4ps_Cryptographers_4re_a11_G00D_Proph3t}

总结#

其实并没有难为大家，更多的还是看看大家平时的积累，如果平时有刷题的话，应该能做出来前两个？

目录

a ctfer on the load

前言#

题目#

easy_sign#

babybaby#

easy_Matrix#

Ez_Cu#

Prediction#

总结#