中国剩余定理

问题形式

方程组如下（以三个模数为例）：

1
2
3
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
x ≡ a3 (mod n3)

其中 n1, n2, n3 两两互质，N = n1 * n2 * n3，则在 [0, N-1] 内存在唯一解

物不知数

一个整数，除以 3 余 2，除以 5 余 3，除以 7 余 2，求该数

模数：3, 5, 7，两两互质，N = 3 * 5 * 7 = 105

1. 构造基数框架

对每个模数 ni，我们需找一个数 Mi 满足：

1
2
Mi ≡ 1 (mod ni)
Mi ≡ 0 (mod 其他所有模数)

构造方法：令 Ni = N / ni，求出 Ni 模 ni 的逆元 yi，使得 (Ni * yi) ≡ 1 (mod ni)，则 Mi = Ni * yi

2. 逐项计算

① n1 = 3，N1 = 105 / 3 = 35

求 35 mod 3 的逆元：35 ≡ 2 (mod 3)

在模 3 的世界里，35 和 2 是等价的

因此，”求 35 模 3 的逆元” 就变成了 “求 2 模 3 的逆元”

2 * 2 = 4 ≡ 1 (mod 3)，逆元 y1 = 2

基数：M1 = 35 * 2 = 70

② n2 = 5，N2 = 105 / 5 = 21

21 ≡ 1 (mod 5)，逆元 y2 = 1

基数：M2 = 21 * 1 = 21

③ n3 = 7，N3 = 105 / 7 = 15

15 ≡ 1 (mod 7)，逆元 y3 = 1

基础：M3 = 15 * 1 = 15

3. 合成解

1
2
3
4
x = a1*M1 + a2*M2 + a3*M3
  = 2*70 + 3*21 + 2*15
  = 140 + 63 + 30
  = 233

模 105 得到最小正整数解：

1
x = 233 mod 105 = 23

实战案例

smallModulus（CRT）

1
2
3
module = getPrime(64)
self.send(("flag mod {} (in hex) : {}".format(
    hex(module)[2:], hex(m % module)[2:])).encode())

当用户选择 1 时，服务器会：

  • 随机生成一个 64 位（bit）的素数 p_i

  • 计算 r_i = m (mod p_i)

  • 将 p_i 和 r_i 以十六进制的形式返回给用户

  • 允许无限次循环查询

假设我们查询了 k 次，获得了 k 个不同的 64 位素数 p1, p2, ..., pk 以及对应的余数 r1, r2, ..., rk

我们可以写出如下的模同余方程组：

1
2
3
4
m ≡ r1 (mod p1)
m ≡ r2 (mod p2)
...
m ≡ rk (mod pk)

由于 pi 全都是不同的素数，因此它们之间必然两两互素（gcd(pi, pj) = 1）

根据中国剩余定理，上述方程组在模 M 的意义下有唯一解，其中

这意味着，只要 M > m，我们通过 CRT 恢复出来的唯一解 x (mod M) 就一定等于原本的明文 m

已知 m < 2^512。每个素数 p_i 是 64 位的，即 p_i ≈ 2^64

我们希望 M = ∏_{i=1}^{k} p_i > 2^512

根据对数的基本性质

1
log2(A * B) = log2(A) + log2(B)

应用到 M 上则有

这是因为题目说每个 pi 都是 64 位素数，也就是 2^64

1
2
3
4
5
log2(M) = log2(p1) + log2(p2) + …… + log2(pk)

        = 64 + 64 + …… 64k

        ≈ 64k
1
64k ≥ 512  => k ≥ 8

因此，我们只需要进行 8 次查询，收集 8 组模数和余数，就能完美恢复出 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
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
from pwn import *
import hashlib
import string
import re
from functools import reduce
from Crypto.Util.number import long_to_bytes, inverse

HOST = "127.0.0.1"
PORT = 10000

def solve_pow(r):
    """
    自动化求解 Proof of Work (SHA256 爆破)
    """
    try:
        # 接收 "sha256(XXXX+" 之后的部分，直到遇到 ')' 并丢弃该字符
        r.recvuntil(b"sha256(XXXX+")
        # 获取后缀（直到 ')' 之前的内容）
        suffix = r.recvuntil(b")", drop=True).decode()
        # 继续接收 "== " 之后的内容，即目标哈希值
        r.recvuntil(b"== ")
        target = r.recvline().strip().decode()

        log.info(f"收到 PoW 挑战: 后缀 = {suffix}, 目标哈希 = {target}")

        # 定义爆破所使用的字符集：大小写字母 + 数字
        alphabet = string.ascii_letters + string.digits
        # mbruteforce 会尝试所有长度为 4 的字符串组合，对每个前缀计算 sha256(prefix+suffix)，
        # 并与 target 比较，返回第一个匹配的字符串。
        prefix = util.iters.mbruteforce(
            lambda x: hashlib.sha256((x + suffix).encode()).hexdigest() == target,
            alphabet,
            4,          # 长度固定为 4
            'exact'     # 表示精确长度，而不是 "最多 4"
        )

        log.success(f"成功爆破出 XXXX: {prefix}")
        # 将正确的前缀发送给服务器
        r.sendlineafter(b"Give me XXXX: ", prefix.encode())
        return True
    except Exception as e:
        log.error(f"PoW 求解失败: {e}")
        return False


def chinese_remainder_theorem(remainders, moduli):
    """
    标准中国剩余定理 (CRT) 实现
    输入：
        remainders : 列表，每个元素为余数 r_i
        moduli     : 列表，每个元素为模数 p_i (两两互素)
    输出：
        满足 x ≡ r_i (mod p_i) 的最小非负整数解 x

    算法步骤：
        1. 计算所有模数的乘积 M = ∏ p_i
        2. 对于每个 i：
           - 计算 M_i = M // p_i
           - 求 t_i = M_i 在模 p_i 下的逆元，即 M_i * t_i ≡ 1 (mod p_i)
           - 累加 x += r_i * t_i * M_i
        3. 返回 x % M （确保结果在 [0, M) 范围内）
    """
    # reduce 逐步计算所有模数的乘积
    M = reduce(lambda x, y: x * y, moduli)
    total = 0
    for r_i, p_i in zip(remainders, moduli):
        M_i = M // p_i                      # 除去当前模数的部分
        # 使用 Crypto.Util.number 中的 inverse 计算模逆元
        t_i = inverse(M_i, p_i)
        total += r_i * t_i * M_i
    return total % M


def get_oracle_data(r):
    # 发送菜单选项 "1" 以获取一次泄露
    r.sendlineafter(b"> ", b"1")
    response = r.recvline().decode().strip()

    # 正则表达式：
    #   - "flag mod " 后跟一个十六进制数（[0-9a-fA-F]+）
    #   - 然后固定字符串 " (in hex) : "
    #   - 再跟另一个十六进制数
    pattern = r"flag mod ([0-9a-fA-F]+) \(in hex\) : ([0-9a-fA-F]+)"
    match = re.search(pattern, response)

    if match:
        mod_hex = match.group(1)   # 模数的十六进制字符串
        res_hex = match.group(2)   # 余数的十六进制字符串
        return int(mod_hex, 16), int(res_hex, 16)
    else:
        raise ValueError(f"无法解析服务器返回的数据: {response}")


def pwn_start():
    # 建立 TCP 连接
    r = remote(HOST, PORT)

    if not solve_pow(r):
        r.close()
        return

    # ---------- 2. 收集同余方程组数据 ----------
    # 已知 flag m < 2^512，每个泄露的模数是 64 位素数（≈ 2^64）
    # 由 CRT 要求：所有模数的乘积 M > m，这样恢复出的唯一解就是原明文
    # 乘法位数累加：log2(M) ≈ Σ log2(p_i) ≈ 64 * k
    # 需要 64 * k ≥ 512 => k ≥ 8。此处取 8 次即可
    required_queries = 8
    moduli = []          # 存储模数 p_i
    remainders = []      # 存储余数 r_i

    log.info(f"开始收集 Oracle 数据，共需 {required_queries} 组...")
    for i in range(required_queries):
        p_i, r_i = get_oracle_data(r)
        moduli.append(p_i)
        remainders.append(r_i)
        log.info(f"[#{i+1}] 模数(64位): {hex(p_i)} | 余数: {hex(r_i)}")

    log.info("数据收集完毕，正在执行中国剩余定理求解...")
    flag_numeric = chinese_remainder_theorem(remainders, moduli)

    flag = long_to_bytes(flag_numeric)
    print("\n" + "=" * 40)
    log.success(f"成功恢复 Flag 原始明文:")
    # 使用 errors='ignore' 避免可能存在的非 UTF-8 字节导致解码异常
    print(flag.decode(errors='ignore'))
    print("=" * 40 + "\n")

    # 发送菜单选项 "2" 正常退出
    r.sendlineafter(b"> ", b"2")
    r.close()


if __name__ == "__main__":
    pwn_start()