ECDSA nonce reuse private key recovery
Recover an ECDSA private key from two signatures that reused the same nonce - the flaw that broke the PlayStation 3 and countless wallets.
Open in ctfpalECDSA requires a fresh random nonce k for every signature. Reuse it once and the private key is recoverable by algebra - not by brute force, not probabilistically, but exactly, from two signatures.
The two-equation solve
Two signatures with the same k share the same r, since r depends only on k. That shared r is how you spot the flaw in a signature dump. From s1 = k^-1 (h1 + r*d) and s2 = k^-1 (h2 + r*d), subtract to eliminate d, solve for k, then substitute back for d.
k = (h1 - h2) * pow(s1 - s2, -1, n) % n
d = (s1 * k - h1) * pow(r, -1, n) % n # the private keyIf the nonces are merely biased rather than repeated - a few known top bits, say - the algebra does not apply, but lattice reduction does. See the biased nonce attack.
Related tools
Biased nonce lattice attack (hidden number problem)
Recover an ECDSA key from many signatures whose nonces leak only a few bits, by reducing the hidden number problem to a lattice with LLL.
Discrete logarithm solver
Solve discrete logs with baby-step giant-step, Pollard’s rho, and Pohlig-Hellman - the last of which breaks any group with smooth order.
XOR crib dragging for many-time pads
Recover both plaintexts when a one-time pad key is reused, by dragging a guessed word along the XOR of two ciphertexts.
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.