crypto-ecdsa-reused-nonce-private-key-recovery

Answer

Why identical r implies nonce reuse. In ECDSA on secp256k1 (order n), the signature component r = x(k·G) mod n is a deterministic function of the nonce k alone. Two signatures from the same key can only share r if the same k was used in both — a re-randomized k would land on a different curve point with (overwhelmingly) a different x-coordinate. That single nonce now appears in two equations, and subtracting them eliminates the private key d, leaving k as the only unknown:

s = k⁻¹(z + r·d) mod n
s1 = k⁻¹(z1 + r·d)          s2 = k⁻¹(z2 + r·d)
s1 − s2 = k⁻¹(z1 − z2)  ⇒  k = (z1 − z2) · (s1 − s2)⁻¹ mod n
d = (s1·k − z1) · r⁻¹ mod n

Edge case s1 == s2. If s1 == s2, then z1 == z2 in any valid signature pair (same message), so (z1−z2) = (s1−s2) = 0 and k is 0/0 — indeterminate. The signatures carry no recoverable information, so the code raises ValueError("signatures unusable") instead of attempting a division by zero. This also guards the inconsistent-but-impossible case of s1 == s2 with z1 != z2.

Recovery math is pure big-integer modular arithmetic (extended Euclid for inversion, no crypto libraries); the EC point multiplication used for verification is an independent, self-contained double-and-add implementation.

P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

def modinv(a, m):                       # extended Euclidean inverse
    a %= m; t, newt, r, newr = 0, 1, m, a
    while newr:
        q = r // newr
        t, newt, r, newr = newt, t - q*newt, newr, r - q*newr
    if r != 1: return None
    return t % m

def recover_nonce(r, s1, s2, z1, z2, n=N):
    if s1 % n == s2 % n:
        raise ValueError("signatures unusable: s1 == s2 (identical messages)")
    return ((z1 - z2) * modinv(s1 - s2, n)) % n

def recover_private_key(r, s1, z1, k, n=N):
    return ((s1 * k - z1) * modinv(r, n)) % n

# verification only: recompute r from k*G (pure-python secp256k1)
def ec_add(p1, p2):
    if p1 is None: return p2
    if p2 is None: return p1
    x1, y1 = p1; x2, y2 = p2
    if x1 == x2 and (y1 + y2) % P == 0: return None
    lam = ((3*x1*x1) * modinv(2*y1, P) if p1 == p2
           else (y2 - y1) * modinv(x2 - x1, P)) % P
    x3 = (lam*lam - x1 - x2) % P
    return (x3, (lam*(x1 - x3) - y1) % P)

def ec_mul(k, point=G):
    out, add = None, point
    while k:
        if k & 1: out = ec_add(out, add)
        add = ec_add(add, add); k >>= 1
    return out

def verify_r(r, k, n=N):                # r' = x(k*G) mod n == r ?
    q = ec_mul(k)
    return q is not None and q[0] % n == r % n

# pipeline: k = recover_nonce(...); d = recover_private_key(...)
#           d_hex = format(d, "064x"); assert verify_r(r, k)