Recovering a DSA or ECDSA Key from a Reused Nonce

Recovering a DSA or ECDSA Key from a Reused Nonce

Introduction

DSA and ECDSA sign a message using one secret random number per signature, called the nonce, usually written k. The math only stays safe while that nonce is unpredictable and never reused. Repeat a single nonce across two signatures, and the private key is no longer secret. It can be computed directly from the two signatures and the two message hashes.

This is not a subtle statistical attack. It is a few lines of modular arithmetic, and it works every time the nonce repeats. Sony learned this when the PlayStation 3’s ECDSA code signing key leaked in 2010, because it used a fixed k. Bitcoin users learned it in 2013, when a weak Android random number generator reused nonces and let thieves recover wallet keys. This guide runs the real recovery against real DSA parameters and the real secp256k1 curve.

Table of Contents

• How the Signature Uses the Nonce
• Why a Repeat Is Fatal
• The Two-Line Recovery
• Interactive Visualizer
• A Worked Example
• Python Implementation
• For Fun: The Recovery in a Few Lines
• Limitations
• Security Status
• FAQ
• References

How the Signature Uses the Nonce

DSA and ECDSA build each signature from two numbers, r and s, computed modulo a large prime order q (or n for ECDSA). The private key is x, the message hash is h, and the nonce is k:

r = ( g^k mod p ) mod q            # DSA
r = ( k * G ).x  mod n             # ECDSA
s = k^-1 * ( h + x * r )  mod q    # both, same shape

The value r depends only on the nonce k, not on the message. That is the whole weakness in one line. Two signatures made with the same k have exactly the same r, which is visible to anyone, because signatures are public. A matching r across two different messages is a flashing sign that the nonce repeated.

Why a Repeat Is Fatal

Suppose two messages with hashes h1 and h2 are signed with the same nonce k. Both signatures share r, and their s values are:

s1 = k^-1 * ( h1 + x * r )  mod q
s2 = k^-1 * ( h2 + x * r )  mod q

Subtract them. The x * r term is identical in both, so it cancels:

s1 - s2 = k^-1 * ( h1 - h2 )  mod q

Everything in that equation is public except k. The attacker knows s1, s2, h1, and h2. One modular inversion gives the nonce:

k = ( h1 - h2 ) * ( s1 - s2 )^-1  mod q

The Two-Line Recovery

Once k is known, the private key follows from either signature. Rearrange s = k^-1 (h + x r) to solve for x:

x = ( s1 * k - h1 ) * r^-1  mod q

That is the entire attack. Two modular inversions, a handful of multiplications, and the private key that was supposed to need billions of years to brute-force appears instantly. ECDSA is identical, with n in place of q. The elliptic curve only changes how r is formed, not the algebra that recovers the key.

Interactive Visualizer

The visualizer above runs the real attack on real secp256k1, the curve Bitcoin and Ethereum use. It signs two messages you choose with the same deliberately reused nonce, shows that the two signatures share r, then recovers the nonce and the private key and checks them against the real secret. Every number is a genuine 256-bit curve value, computed with real point multiplication, with nothing faked.

Edit either message and run it again. As long as the nonce is reused, the recovered private key matches the real one exactly. That is the point: the key holder did nothing wrong except let one random number repeat.

A Worked Example

The DSA side uses a real 1024-bit prime p with a 160-bit prime order q, and a private key x. Two different payment messages are signed with the same nonce. The shared r gives the attack away, and the recovery returns the exact private key:

DSA: two messages signed with the same nonce
  "Transfer $100 to Alice" and "Transfer $100 to Bob"
  r shared: 0x5160ff55f2...212905
  s1: 0x296ae750d7...a11b09   s2: 0xc5c9234d34...6b7ca7
  recovered x: 0xb5b510130c...5ce0a4   == private key: True

The ECDSA side uses secp256k1 and a 256-bit private key d. Two signed statements reuse one nonce, and the full private key comes back:

ECDSA secp256k1: two messages signed with the same nonce
  "send 10 BTC to 1Alice" and "send 10 BTC to 1Bob"
  r shared: 0xbbf4f314f2...9c6f7c
  recovered d: 0x50a9ea6b83f2c1fced4acddfbe3445a751ef66b3d2c0434d5d732fc6404efbd2
  == private key: True

Both keys come back exactly, with no search and no luck involved. A signer who reuses a nonce even once has published their private key, in effect, inside two ordinary-looking signatures.

Python Implementation

The code is self-contained and runnable. It uses a fixed real DSA parameter set and the real secp256k1 curve, signs two messages with a reused nonce, verifies them, and recovers the private key. The recover_* functions use only public values: the two signatures and the two message hashes.

# reused_nonce.py
#
# Reused-nonce key recovery for DSA and ECDSA. Both schemes need a secret, unique, unpredictable nonce k
# per signature. The value r depends only on k, so two signatures with the same k share r (publicly
# visible). Subtracting the two s-equations cancels the private key and yields k, and then one more step
# yields the private key itself. This is the flaw that leaked the PS3 code-signing key (fixed k) and
# drained Bitcoin wallets in 2013 (a broken RNG repeating k). The DSA parameters below are a real
# 1024-bit/160-bit set; the curve is real secp256k1.
import hashlib


def inv(a, m):
    return pow(a, -1, m)


# ---- DSA (real 1024-bit p / 160-bit q) ----
P = 0xc442337fd54eec951cb75bebeed8e7dc2829c55d19fce6e05963a769a0ce0d4d5a7d87e68e138428643e8329dc23b5ff3bf61dd82e405bb7634de0f0c5985c4865834bf7c66bbe1ee539a5c4bd60345659cde0dbedb4d15e0bc10648a1c75526e17b8670373eb295b4b90d408a1f2599aca9087be256f0684debcd121a404759
Q = 0xe4743a4bed9419c112f108bffab3bf4e09cf3d51
G = 0x21cfd06a251f6c572189e6f50d7e872d3dca1ce3a5e3bb10ebd946a76bd4a52fe1614099403d772f592def561759c7e484bd230f21e3237c02e0c545ce82c8c4c18067ca705722455e6632cf0396b33703d86c7c375e3bf9d8319f791280580ef46fa8d17fb376550410b6cc6b829c8fc7838241d9012bb3ae9464eb701dc951
X = 0xb5b510130c51bb8682050ab550b73c57545ce0a4            # the private key (the target)
DSA_K = 0xabfd9d01278cc0f324e9342e771dd06244a801fd        # the reused nonce


def dsa_hash(m):
    return int.from_bytes(hashlib.sha1(m).digest(), "big") % Q


def dsa_sign(m, k):
    r = pow(G, k, P) % Q
    s = inv(k, Q) * (dsa_hash(m) + X * r) % Q
    return r, s


def recover_dsa(m1, m2, sig1, sig2):
    r, s1 = sig1
    _, s2 = sig2
    h1, h2 = dsa_hash(m1), dsa_hash(m2)
    k = (h1 - h2) * inv((s1 - s2) % Q, Q) % Q          # same k => same r => k cancels out
    x = (s1 * k - h1) * inv(r, Q) % Q
    return k, x


# ---- ECDSA on secp256k1 (Bitcoin / Ethereum / PS3 curve) ----
EP = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
EN = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
GP = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
      0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
D = 0x50a9ea6b83f2c1fced4acddfbe3445a751ef66b3d2c0434d5d732fc6404efbd2   # the private key
EC_K = 0x00b2d2222181e7e4dd50cf58197c257ccdcba623b7bd42d3c5dbbadbd4ef3f9d   # the reused nonce


def ec_add(A, B):
    if A is None or B is None:
        return A or B
    x1, y1 = A
    x2, y2 = B
    if x1 == x2 and (y1 + y2) % EP == 0:
        return None
    lam = (3 * x1 * x1) * inv(2 * y1, EP) % EP if A == B else (y2 - y1) * inv((x2 - x1) % EP, EP) % EP
    x3 = (lam * lam - x1 - x2) % EP
    return (x3, (lam * (x1 - x3) - y1) % EP)


def ec_mul(k, Pt):
    R = None
    while k:
        if k & 1:
            R = ec_add(R, Pt)
        Pt = ec_add(Pt, Pt)
        k >>= 1
    return R


def ec_hash(m):
    return int.from_bytes(hashlib.sha256(m).digest(), "big") % EN


def ecdsa_sign(m, k):
    r = ec_mul(k, GP)[0] % EN
    s = inv(k, EN) * (ec_hash(m) + D * r) % EN
    return r, s


def recover_ecdsa(m1, m2, sig1, sig2):
    r, s1 = sig1
    _, s2 = sig2
    h1, h2 = ec_hash(m1), ec_hash(m2)
    k = (h1 - h2) * inv((s1 - s2) % EN, EN) % EN
    d = (s1 * k - h1) * inv(r, EN) % EN
    return k, d


if __name__ == "__main__":
    m1, m2 = b"Transfer $100 to Alice", b"Transfer $100 to Bob"
    s1, s2 = dsa_sign(m1, DSA_K), dsa_sign(m2, DSA_K)
    print("DSA   r shared:", s1[0] == s2[0])
    k, x = recover_dsa(m1, m2, s1, s2)
    print("DSA   recovered private key == real:", x == X)

    em1, em2 = b"send 10 BTC to 1Alice", b"send 10 BTC to 1Bob"
    e1, e2 = ecdsa_sign(em1, EC_K), ecdsa_sign(em2, EC_K)
    print("ECDSA r shared:", e1[0] == e2[0])
    k2, d = recover_ecdsa(em1, em2, e1, e2)
    print("ECDSA recovered private key == real:", d == D)
    print("ECDSA recovered d:", hex(d))

Running it confirms both recoveries:

DSA   r shared: True
DSA   recovered private key == real: True
ECDSA r shared: True
ECDSA recovered private key == real: True
ECDSA recovered d: 0x50a9ea6b83f2c1fced4acddfbe3445a751ef66b3d2c0434d5d732fc6404efbd2

For Fun: The Recovery in a Few Lines

Given two signatures that share r, the recovery itself is four lines, independent of the curve or group. Pass the order, the two hashes, and the two s values:

def recover(order, r, h1, h2, s1, s2):
    inv = lambda a: pow(a, -1, order)
    k = (h1 - h2) * inv((s1 - s2) % order) % order     # the reused nonce
    x = (s1 * k - h1) * inv(r) % order                 # the private key
    return k, x

That function is the whole attack. Everything else in the full listing is just the signing and hashing needed to produce the inputs, which a real attacker reads straight off the wire instead.

Limitations

The attack is exact, but it only applies under specific conditions:

• The nonce must actually repeat, or be predictable. This recovery needs two signatures with the same k. A biased or partially leaked nonce can also break the key through lattice attacks, which are more involved, but a full repeat is the clean case shown here.
• The signatures must be from the same key. The two messages have to be signed by the same private key with the same nonce. A matching r from two different keys is coincidence, not a break.
• You need the message hashes. The attacker must know what was signed, which is normally public, since signatures accompany their messages. Without h1 and h2 the subtraction does not close.
• Correct signing is immune. A properly generated nonce, random or derived deterministically per RFC 6979, never repeats across different messages, so this attack simply never triggers.

Security Status

• Nonce reuse is a total break, not a weakening. When it happens, the private key is recovered with certainty and almost no computation. There is no safety margin to fall back on, which is what makes it so dangerous compared to attacks that only chip away at security.
• Deterministic nonces are the standard fix. RFC 6979 derives the nonce deterministically from the private key and the message hash, using HMAC. The nonce is still secret and unique per message, but it no longer depends on a random number generator that might fail. Modern libraries use it by default.
• It keeps happening in practice. The PS3 break in 2010 and the Android Bitcoin wallet thefts in 2013 are the famous cases, but weak or repeated nonces still surface in audits. The lesson is that the nonce is as sensitive as the private key itself, and generating it correctly is not optional.

FAQ

What exactly is the nonce?

It is a secret random number chosen fresh for each signature, written k. It blinds the private key inside the signature equation. The signature is secure only while k is unpredictable and never reused, which is why it is sometimes called an ephemeral key.

How does the attacker notice a reused nonce?

The value r in a signature depends only on the nonce, not the message. So two signatures that share the same r were almost certainly made with the same nonce. Since signatures are public, scanning for a repeated r across a signer’s history is easy.

Does this break DSA and ECDSA in general?

No. It breaks implementations that reuse or mishandle the nonce. The algorithms are secure when the nonce is generated correctly. This is an implementation failure, not a flaw in the underlying math, which is exactly why deterministic nonces were standardized.

Was this really how the PS3 was hacked?

Yes. Sony used a fixed, constant k for all ECDSA code signatures, so every signature shared the same r. That let researchers recover the master private signing key in 2010 and sign their own code as if it came from Sony.

How do I avoid it in my own code?

Never generate the nonce yourself from a general-purpose random source unless you are certain it is strong. Use a library that implements RFC 6979 deterministic nonces, or a modern signature scheme like Ed25519 that derives the nonce deterministically by design.

References

1. fail0verflow. “Console Hacking 2010: PS3 Epic Fail,” 27C3, 2010 (the reused-nonce recovery of the PS3 ECDSA key).

2. Pornin, Thomas. “Deterministic Usage of DSA and ECDSA Digital Signature Algorithms,” RFC 6979, 2013.

3. Bos, Joppe, et al. “Elliptic Curve Cryptography in Practice,” 2013 (analysis of nonce reuse in deployed Bitcoin keys).

4. The DSA guide on this site: /blog/dsa_guide/

5. The ECDSA guide on this site: /blog/ecdsa_guide/