CryptoHack Mathematics 题解

发表于 分类于 阅读次数：

CryptoHack Mathematics 与零散题解

CryptoHack 题目统计如下：

分类 题数 分数
Symmetric Ciphers 12 465
Mathematics 8 455
RSA 20 1025
Diffie-Hellman 7 285
Hash Functions 6 350
Lattices 13 480
其他 8 200

本文先记录 Mathematics 分类中的两道题，再补充三道零散题。

题目索引

No Way Back Home

题目分析

协议中令 v = p * r mod n，所以 v 含有因子 p。Alice 和 Bob 分别乘上自己的随机数，再通过逆元消除，最终公开了：

1
2
3
vka   = v * kA mod n
vkakb = v * kA * kB mod n
vkb   = v * kB mod n

这些值在模 n 下都不可直接求逆，因为包含因子 p。但在模 q 下它们可逆，可以先恢复 v mod q，再利用 v = 0 mod p 通过 CRT 还原 v mod n。

解法

核心计算如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from hashlib import sha256

from Crypto.Cipher import AES
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.Util.Padding import unpad


n = p * q

vkakb_q = vkakb % q
vkb_q = vkb % q
k_a_q = vkakb_q * inverse(vkb_q, q) % q

vka_q = vka % q
v_q = vka_q * inverse(k_a_q, q) % q

# v = 0 (mod p)，并且 v = v_q (mod q)。
t = v_q * inverse(p, q) % q
v = p * t % n

key = sha256(long_to_bytes(v)).digest()
plaintext = AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(ciphertext))
print(unpad(plaintext, 16).decode())

最终得到：

1
crypto{1nv3rt1bl3_k3y_3xch4ng3_pr0t0c0l}

Unencryptable

题目分析

题目给出一份固定的 DATA，并使用 RSA 对它加密。由于明文满足：

因此：

将 m^(e-1)-1 与 N 做最大公约数，就可以得到 N 的非平凡因子。由于 e = 65537，可以不断将指数 e - 1 除以 2，直到找到合适的分解。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import GCD, bytes_to_long, long_to_bytes


e = 65537
m = bytes_to_long(DATA)
exponent = e - 1

while exponent > 1:
    candidate = GCD(pow(m, exponent, N) - 1, N)
    if 1 < candidate < N:
        p = candidate
        break
    exponent //= 2

q = N // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
flag = long_to_bytes(pow(ciphertext, d, N)).decode()
print(flag)

最终 flag 为：

1
crypto{R3m3mb3r!_F1x3d_P0iNts_aR3_s3crE7s_t00}

Successive Powers

题目给出一组整数：

1
588, 665, 216, 113, 642, 4, 836, 114, 851, 492, 819, 237

它们是整数 x 的连续高次幂模三位素数 p 的结果，需要求出 p 和 x。

观察到：

1
836 // 4 = 209

如果 x != 209，则存在 k 使：

也就是 x = 209 + kp。当 k != 0 时，x >= 209 + p > p，与模运算中取代表元的范围矛盾。因此：

1
2
x = 209
p = 919

将 p 和 x 提交给题目即可得到 flag。

Broken RSA

题目分析

题目给出的 RSA 参数中，N 是素数，e = 16，密文为 c = m^16 mod N，并且明文 m < N。

因为指数是 16，所以不能直接使用普通 RSA 逆元。需要连续执行 4 次模平方根，每一轮都有两个可能的根，总共最多 2^4 = 16 条候选路径。

解法

使用 Tonelli-Shanks 求模素数平方根，然后枚举每次取正根或负根：

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 long_to_bytes
from sympy.ntheory.residue_ntheory import sqrt_mod


# 将题目中的 N 和 ct 填入。
N = ...
ct = ...

candidates = [ct]
for _ in range(4):
    next_candidates = []
    for value in candidates:
        roots = sqrt_mod(value, N, all_roots=True)
        next_candidates.extend(int(root) for root in roots)
    candidates = next_candidates

for candidate in candidates:
    try:
        text = long_to_bytes(candidate).decode()
    except UnicodeDecodeError:
        continue
    if text.startswith("crypto{"):
        print(text)

最终得到：

1
crypto{m0dul4r_squ4r3_r00t}

Noise Free

题目分析

服务端使用如下线性加密：

其中 q = 65537，A 是 64 维随机向量，S 是固定的 64 维私钥，m 是明文字符。

先反复请求 m = 0 的加密结果，就能得到足够多组：

收集至少 64 组线性无关的样本后，用模 q 的高斯消元恢复 S。拿到 S 后，对每个 flag 字符计算：

最后将结果映射回字节。

攻击脚本核心

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
import json
import socket
import sys


Q = 65537
DIMENSION = 64


def recv_line(sock):
    data = bytearray()
    while True:
        byte = sock.recv(1)
        if not byte:
            break
        data.extend(byte)
        if byte == b"\n":
            break
    return data.decode().strip()


def request(sock, payload):
    sock.sendall(json.dumps(payload).encode() + b"\n")
    return json.loads(recv_line(sock))


def solve_mod(matrix, values, modulus):
    augmented = [
        [value % modulus for value in row] + [values[i] % modulus]
        for i, row in enumerate(matrix)
    ]
    row = 0
    for column in range(len(matrix[0])):
        pivot = next(
            (i for i in range(row, len(augmented))
             if augmented[i][column] % modulus),
            None,
        )
        if pivot is None:
            continue

        augmented[row], augmented[pivot] = augmented[pivot], augmented[row]
        inverse = pow(augmented[row][column], modulus - 2, modulus)
        augmented[row] = [
            item * inverse % modulus for item in augmented[row]
        ]

        for other in range(len(augmented)):
            if other == row:
                continue
            factor = augmented[other][column]
            if factor:
                augmented[other] = [
                    (left - factor * right) % modulus
                    for left, right in zip(augmented[other], augmented[row])
                ]
        row += 1

    solution = [0] * len(matrix[0])
    for current in augmented:
        pivot = next(
            (i for i, value in enumerate(current[:-1]) if value == 1),
            None,
        )
        if pivot is not None:
            solution[pivot] = current[-1]
    return solution


host = sys.argv[1] if len(sys.argv) > 1 else "socket.cryptohack.org"
port = int(sys.argv[2]) if len(sys.argv) > 2 else 13411

with socket.create_connection((host, port)) as sock:
    print(recv_line(sock))

    samples = [
        request(sock, {"option": "encrypt", "message": 0})
        for _ in range(70)
    ]
    matrix = [json.loads(sample["A"]) for sample in samples]
    values = [int(sample["b"]) for sample in samples]
    secret = solve_mod(matrix, values, Q)

    flag = []
    for index in range(100):
        result = request(sock, {"option": "get_flag", "index": index})
        if "error" in result:
            break
        vector = json.loads(result["A"])
        value = int(result["b"])
        message = (value - sum(
            vector[i] * secret[i] for i in range(DIMENSION)
        )) % Q
        flag.append(chr(message % 257))

    print("".join(flag))

这道题的核心不是噪声分析，而是发现服务端允许选择明文 0，从而把私钥恢复转化成一个线性方程组。