bash -lc cat > /mnt/data/solve.sage.py <<'PY' #!/usr/bin/env sage -python

Usage: save the challenge output up to "signature(hex)>" into out.txt,

then run: sage -python solve.sage.py < out.txt

It prints a DER-encoded ECDSA signature for b"gimme flag".

import hashlib import random import re import sys from sage.all import ZZ, GF, EllipticCurve, Matrix, inverse_mod

NIST P-521 / secp521r1 parameters

p = 2**521 - 1 N = ZZ(int("01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409", 16)) a = -3 b = int("0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16) Gx = int("00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16) Gy = int("011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)

LEAK = 6 B = 1 << LEAK TARGET = b"gimme flag"

def parse_transcript(text): qx = qy = None samples = [] for line in text.splitlines(): line = line.strip() if line.startswith("public_x ="): qx = ZZ(int(line.split("=", 1)[1].strip())) elif line.startswith("public_y ="): qy = ZZ(int(line.split("=", 1)[1].strip())) else: m = re.fullmatch(r"([0-9a-fA-F]+)\s+([0-9a-fA-F]+)\s+([0-9a-fA-F]+)\s+(\d+)", line) if m: h = ZZ(int(m.group(1), 16)) r = ZZ(int(m.group(2), 16)) s = ZZ(int(m.group(3), 16)) kl = ZZ(int(m.group(4))) samples.append((h, r, s, kl)) if len(samples) < 80: raise SystemExit(f"too few samples parsed: {len(samples)}") return qx, qy, samples

def recover_key(samples, qx=None, qy=None): """Recover d from k mod 2^LEAK using a centered HNP lattice.""" m = len(samples) invB = inverse_mod(B, N) center = N // (2 * B)

text
t = []
u = []
for h, r, s, kl in samples:
    si = inverse_mod(s, N)
    # k = si*(h + r*d) mod N = kl + B*x
    # x = (si*r*B^-1)*d + (si*h - kl)*B^-1 mod N, and x < N/B.
    ti = (r * si * invB) % N
    ui = ((h * si - kl) * invB - center) % N   # center the error around 0
    t.append(ZZ(ti))
    u.append(ZZ(ui))

def valid(d):
    if not (1 <= d < N):
        return False
    for h, r, s, kl in samples:
        k = (inverse_mod(s, N) * (h + r * d)) % N
        if k % B != kl:
            return False
    if qx is not None and qy is not None:
        E = EllipticCurve(GF(p), [a, b])
        G = E(Gx, Gy)
        Q = d * G
        if ZZ(Q[0]) != qx or ZZ(Q[1]) != qy:
            return False
    return True

# R is the coordinate scaling. B is the textbook value; larger values often
# help make the embedded closest vector easier for BKZ to expose.
for R in [B, 2*B, 4*B, 8*B, 16*B, 32*B, 64*B, 128*B, 256*B]:
    M = Matrix(ZZ, m + 2, m + 2)
    for i in range(m):
        M[i, i] = N * R
    for i in range(m):
        M[m, i] = t[i] * R
    M[m, m] = 1
    for i in range(m):
        M[m + 1, i] = u[i] * R
    M[m + 1, m + 1] = N

    # LLL is sometimes enough; BKZ-20/25 is still small for this dimension.
    bases = []
    L = M.LLL()
    bases.append(L)
    for beta in (20, 25, 30):
        try:
            L = L.BKZ(block_size=beta)
            bases.append(L)
        except TypeError:
            # Older Sage versions may not accept keyword args.
            L = L.BKZ(beta)
            bases.append(L)
        except Exception:
            pass

    for L in bases:
        for row in L.rows():
            if abs(ZZ(row[-1])) == N:
                for sg in (1, -1):
                    d = (sg * ZZ(row[-2])) % N
                    if valid(d):
                        return d
raise SystemExit("failed to recover d; try increasing BKZ block size")

def der_len(n): if n < 128: return bytes([n]) b = n.to_bytes((n.bit_length() + 7) // 8, "big") return bytes([0x80 | len(b)]) + b

def der_int(x): b = int(x).to_bytes((int(x).bit_length() + 7) // 8 or 1, "big") if b[0] & 0x80: b = b"\x00" + b return b"\x02" + der_len(len(b)) + b

def der_sig(r, s): body = der_int(r) + der_int(s) return b"\x30" + der_len(len(body)) + body

def sign_target(d): E = EllipticCurve(GF(p), [a, b]) G = E(Gx, Gy) h = ZZ(int.from_bytes(hashlib.sha512(TARGET).digest(), "big")) while True: k = ZZ(random.randrange(1, int(N))) R = k * G r = ZZ(R[0]) % N if r == 0: continue s = (inverse_mod(k, N) * (h + r * d)) % N if s != 0: return der_sig(r, s).hex()

def main(): qx, qy, samples = parse_transcript(sys.stdin.read()) d = recover_key(samples, qx, qy) print(sign_target(d))

if name == "main": main() PY ls -l /mnt/data/solve.sage.py head -5 /mnt/data/solve.sage.py

Thought for 27m 48s