1
import math
2
import sys
3
import zipfile
4
from pathlib import Path
5

6
archive = Path(sys.argv[1]) if len(sys.argv) > 1 else Path("encrypt.zip")
7
with zipfile.ZipFile(archive) as zf:
8
    values = {}
9
    for line in zf.read("secret").decode().splitlines():
10
        key, value = line.split("=", 1)
11
        values[key] = int(value)
12

13
N, m1, m2 = values["N"], values["m1"], values["m2"]
14
e = 0x10001
15

16
a = math.isqrt(N)
17
if a * a < N:
18
    a += 1
19
while True:
20
    b2 = a * a - N
21
    b = math.isqrt(b2)
22
    if b * b == b2:
23
        p, q = a - b, a + b
24
        if p * q == N:
25
            break
26
    a += 1
27

28
phi = (p - 1) * (q - 1)
29
d = pow(e, -1, phi)
30
S = pow(m1, d, N)
31
T = pow(m2, d, N)
32

33
assert (S**3 - T) % (3 * S) == 0
34
product = (S**3 - T) // (3 * S)
35
discriminant = S * S - 4 * product
36
root = math.isqrt(discriminant)
37
assert root * root == discriminant
38
F1, F2 = (S + root) // 2, (S - root) // 2
39

40
def long_to_bytes(n):
41
    return n.to_bytes((n.bit_length() + 7) // 8, "big")
42

43
parts = [long_to_bytes(F1), long_to_bytes(F2)]
44
for ordered in (parts, parts[::-1]):
45
    candidate = b"".join(ordered)
46
    if candidate.startswith(b"GWHT{") and candidate.endswith(b"}"):
47
        print(candidate.decode())
48
        break