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
| from Crypto.Util.number import inverse
# 给定的数据
data = [
(424507, 258891, 246908, 696833),
(725635, 532266, 196020, 913873),
(525257, 615406, 320693, 1041077),
(83144, 77839, 378617, 739631),
(118240, 112107, 439081, 659539),
(689363, 382486, 909472, 1013741),
(689679, 637871, 783227, 901529),
(255640, 331169, 471838, 594311),
(583522, 135573, 846849, 1010203),
(420869, 290426, 411805, 618377),
(945219, 32778, 905582, 1021651),
(620301, 441932, 117862, 869233),
(663631, 852415, 494895, 867619),
(699620, 557493, 53174, 730571),
(59702, 84201, 265515, 854299),
(20572, 600277, 106738, 765319),
(681296, 883108, 245309, 900577),
(100959, 581845, 520231, 716789),
(149718, 384454, 362305, 876761),
(373486, 791525, 183314, 847477),
(550280, 313487, 490116, 601397),
(318232, 430375, 409959, 934907),
(79907, 133279, 451022, 561917),
(171513, 94683, 332805, 615497),
(426495, 420294, 285501, 619079),
]
# 转换为 (a_i, d_i, p_i)
equations = []
for a, b, c, p in data:
d = (c - b) % p
equations.append((a, d, p))
# 求解单个方程
def solve_one_equation(a, d, p):
inv_a = inverse(a, p)
return (inv_a * d) % p
# 使用 CRT 合并方程
def chinese_remainder_theorem(equations):
x = 0
N = 1
for _, _, p in equations:
N *= p
for a, d, p in equations:
n = N // p
inv_n = inverse(n, p)
x += d * n * inv_n
x %= N
return x, N
# 计算结果
reduced_equations = [(1, solve_one_equation(a, d, p), p) for a, d, p in equations]
m, mod = chinese_remainder_theorem(reduced_equations)
print(f"Recovered m: {m}")
flag = long_to_bytes(m)
print(f"Recovered flag: {flag.decode()}")
|
