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
|
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import inverse, isPrime
from math import isqrt
# EC 椭圆曲线阶
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
# 签名信息
r1 = 18507930132802310344248699822628576170242868593944128167302942018134209256936
s1 = 23965013559564325260453725916491832279556345092147805659950905735422363429946
m1 = b'32748923ur8934u893ygf893h34t3453453'
r2 = 61645219796227967861807301237829197706412124807702206247291322591426944615554
s2 = 84283844402102709520391794221564573160907887711307574424747605446691209453247
m2 = b'ehfw9h8r039u82678ifjewf9024r2323423'
h1 = int.from_bytes(sha256(m1).digest(), 'big')
h2 = int.from_bytes(sha256(m2).digest(), 'big')
s1_inv = inverse(s1, n)
# 构造二次模方程
A = (s2 * 7 * pow(s1_inv, 2, n)) % n
B = (s2 * 3 * s1_inv) % n
C = (s2 * 11) % n
h1sq = pow(h1, 2, n)
r1sq = pow(r1, 2, n)
term1 = (A * h1sq) % n
term2 = (2 * A * r1 * h1) % n
term3 = (A * r1sq) % n
term4 = (B * h1) % n
term5 = (B * r1) % n
const_right = (term1 + term4 + C) % n
linear_right = (term2 + term5) % n
quad_right = term3
# 左右相减后得到二次方程：
# d^2 * quad_right + d * (linear_right - r2) + (const_right - h2) ≡ 0 mod n
a = quad_right
b = (linear_right - r2) % n
c = (const_right - h2) % n
# 求模 n 意义下的二次同余 a*d^2 + b*d + c ≡ 0 (mod n)
def modular_sqrt(a, p):
"""Tonelli-Shanks algorithm: solve x^2 ≡ a mod p"""
if pow(a, (p - 1) // 2, p) != 1:
return None # no square root exists
if p % 4 == 3:
return pow(a, (p + 1) // 4, p)
# Find Q and S with p-1 = Q * 2^S
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
# Find z which is a quadratic non-residue
for z in range(2, p):
if pow(z, (p - 1) // 2, p) == p - 1:
break
m = s
c = pow(z, q, p)
t = pow(a, q, p)
r = pow(a, (q + 1) // 2, p)
while t != 1:
i = 1
t2 = (t * t) % p
while t2 != 1:
t2 = (t2 * t2) % p
i += 1
if i == m:
return None
b = pow(c, 1 << (m - i - 1), p)
m = i
c = (b * b) % p
t = (t * c) % p
r = (r * b) % p
return r
def solve_quadratic_mod(a, b, c, p):
"""Solves a*d^2 + b*d + c ≡ 0 mod p"""
a_inv = inverse(a, p)
b_ = (b * a_inv) % p
c_ = (c * a_inv) % p
# Solve d^2 + b_*d + c_* ≡ 0
discriminant = (b_ * b_ - 4 * c_) % p
sqrt_d = modular_sqrt(discriminant, p)
if sqrt_d is None:
return []
root1 = (-b_ + sqrt_d) * inverse(2, p) % p
root2 = (-b_ - sqrt_d) * inverse(2, p) % p
return [root1, root2]
# 解出 d 的可能值
roots = solve_quadratic_mod(a, b, c, n)
# 解密尝试
for d in roots:
key = sha256(str(d).encode()).digest()
ct = bytes.fromhex("a713d56a102ac904da8baa66deaedcdbb754cd8bc94bf4b45e708d611b53ef92af03e9c20c8c8383f9c6c709f99c709d")
try:
cipher = AES.new(key, AES.MODE_ECB)
flag = unpad(cipher.decrypt(ct), 16)
print(f"[+] Found d = {d}")
print(f"[+] FLAG = {flag}")
break
except:
continue
|
