1
# !/usr/bin/env sage
2
import re
3
import socket
4
from random import randint, seed
5

6
HOST = "57.131.40.44"
7
PORT = 9976
8
CANARY = 325
9

10
def recv_all(sock):
11
    chunks = []
12
    while True:
13
        data = sock.recv(4096)
14
        if not data:
15
            break
16
        chunks.append(data)
17
    return b"".join(chunks).decode(errors="ignore")
18

19
def query_calibration(p, a, b, gx, gy):
20
    payload = f"2\n{CANARY}\n{p} {a} {b} {gx} {gy}\n5\n".encode()
21
    with socket.create_connection((str(HOST), int(PORT)), timeout=float(10)) as s:
22
        s.sendall(payload)
23
        out = recv_all(s)
24
    m = re.search(r"Q = \(([-0-9]+), ([-0-9]+)\)", out)
25
    if not m:
26
        raise RuntimeError(f"No Q found for params {(p,a,b,gx,gy)}\nOutput:\n{out}")
27
    return int(m.group(1)), int(m.group(2)), out
28

29
def submit_scalar(k):
30
    payload = f"4\n{CANARY}\n{k}\n5\n".encode()
31
    with socket.create_connection((str(HOST), int(PORT)), timeout=float(10)) as s:
32
        s.sendall(payload)
33
        out = recv_all(s)
34
    return out
35

36
def combine_congruence(a, m, b, n):
37
    g = gcd(m, n)
38
    if (a - b) % g != 0:
39
        raise ValueError("Inconsistent congruences")
40
    m1 = m // g
41
    n1 = n // g
42
    t = ((b - a) // g) * inverse_mod(m1, n1)
43
    t = Integer(t % n1)
44
    l = lcm(m, n)
45
    x = Integer((a + m * t) % l)
46
    return x, Integer(l)
47

48
def build_candidates(target_bits=64):
49
    seed(int(1337))
50
    prime_list = list(primes(40000, 70001))
51
    cands = []
52
    for _ in range(2500):
53
        p = int(prime_list[randint(0, len(prime_list) - 1)])
54
        F = GF(p)
55
        a = randint(0, p - 1)
56
        b = randint(0, p - 1)
57
        if (4 * a^3 + 27 * b^2) % p == 0:
58
            continue
59
        E = EllipticCurve(F, [a, b])
60
        G = E.random_point()
61
        if G.is_zero():
62
            continue
63
        n = int(G.order())
64
        if n < 2000:
65
            continue
66
        gx = int(G[0])
67
        gy = int(G[1])
68
        cands.append((p, int(a), int(b), gx, gy, n))
69

70
    selected = []
71
    M = Integer(1)
72
    while M.nbits() <= target_bits + 8:
73
        best = None
74
        best_gain = 1
75
        for (p, a, b, gx, gy, n) in cands:
76
            gain = Integer(n // gcd(n, M))
77
            if gain > best_gain:
78
                best_gain = gain
79
                best = (p, a, b, gx, gy, n)
80
        if best is None:
81
            break
82
        selected.append(best)
83
        M = lcm(M, Integer(best[5]))
84
        cands.remove(best)
85
        if len(selected) >= 16:
86
            break
87
    return selected
88

89
def main():
90
    selected = build_candidates()
91
    print(f"[+] selected {len(selected)} curves")
92

93
    x = Integer(0)
94
    M = Integer(1)
95
    used = 0
96

97
    for (p, a, b, gx, gy, n) in selected:
98
        E = EllipticCurve(GF(p), [a, b])
99
        G = E((gx, gy))
100
        qx, qy, _ = query_calibration(p, a, b, gx, gy)
101
        try:
102
            Q = E((qx, qy))
103
            kmod = Integer(Q.log(G))
104
        except Exception as ex:
105
            print(f"[skip] unusable sample for p={p}: {ex}")
106
            continue
107

108
        if used == 0:
109
            x = kmod
110
            M = Integer(n)
111
        else:
112
            x, M = combine_congruence(x, M, kmod, Integer(n))
113
        used += 1
114
        print(f"[{used}] n={n}, k mod n={kmod}, combined bits={M.nbits()}")
115
        if M > 2^64:
116
            break
117

118
    upper = Integer(2^64 - 1)
119
    if x > upper:
120
        x = Integer(x % M)
121

122
    candidates = []
123
    tmax = int((upper - x) // M)
124
    for t in range(tmax + 1):
125
        k = Integer(x + t * M)
126
        if 0 <= k <= upper:
127
            candidates.append(k)
128

129
    if len(candidates) != 1:
130
        raise RuntimeError(f"Could not isolate scalar uniquely. Remaining: {len(candidates)}")
131

132
    k = int(candidates[0])
133
    print(f"[+] recovered master scalar: {k}")
134
    print(submit_scalar(k))
135

136
if __name__ == "__main__":
137
    main()