ECDSA Nonce Reuse and the Private Key It Leaks

An ECDSA signature is a pair of integers $(r, s)$ computed from a message hash $z$, a private key $d$, and a per-signature secret $k$ chosen uniformly from the range of the curve order $n$. The value $r$ is the $x$-coordinate of the point $kG$ reduced modulo $n$, and $s = k^{-1}(z + r d) \bmod n$. The verifier recovers a point from $r$ and $s$ and checks that it has the expected $x$-coordinate.

The formula contains two unknowns, $k$ and $d$, in a single equation. Given one signature, that equation has $n$ solutions for $d$, one per possible $k$, and all are equally plausible. Given two signatures over the same key with the same $k$, there are two equations and two unknowns, and the system is linear.

Two equations, one subtraction

Write the two signing equations with the same nonce:

$$s_1 = k^{-1}(z_1 + r d) \bmod n, \qquad s_2 = k^{-1}(z_2 + r d) \bmod n$$

The $r$ value is identical in both, because it depends only on $kG$. Multiply each by $k$ and subtract:

$$s_1 k - s_2 k = z_1 - z_2 \pmod n \quad\Longrightarrow\quad k = \frac{z_1 - z_2}{s_1 - s_2} \bmod n$$

With $k$ recovered, either equation gives $d = (s_1 k - z_1) r^{-1} \bmod n$. Both divisions are modular inverses and always exist unless $s_1 \equiv s_2$, which would mean $z_1 \equiv z_2$ and the messages had the same hash. No search, no cryptanalysis of the curve, and no interaction with the signer: two signatures in a public log are sufficient.

def recover_key(n, r, s1, s2, z1, z2):
    # Same nonce used for two signatures; all arithmetic mod the curve order
    k = (z1 - z2) * pow(s1 - s2, -1, n) % n
    d = (s1 * k - z1) * pow(r, -1, n) % n
    return k, d

The operation costs three modular inverses on numbers the size of the curve order, which is negligible compared with any network exchange. A single duplicated nonce anywhere in a key’s lifetime is a complete compromise of that key, not a partial one, because the attacker can then sign anything.

The failure is not hypothetical in the sense of requiring a broken curve or a weak hash. It arises from any source of randomness that repeats: a virtual machine restored from a snapshot with a stale entropy pool, a forked process that inherits a random state, a hardware generator that returns a fixed value after reset, or a counter that overflows. The signatures involved remain individually valid, so nothing fails visibly; the compromise is silent and retroactive, since every past signature by that key is now forged-able.

Biased nonces are almost as bad

Suppose the nonce is not repeated but is drawn from a smaller set, or has a few known high bits, or comes from a generator with a small bias. Each signature then gives an equation whose hidden value $k_i$ lies in a restricted range. This is the hidden number problem, and it is solved with lattice reduction rather than algebra.

The standard formulation collects signatures into a lattice whose short vectors correspond to the deviations $k_i - \hat{k}_i$ from the expected value. Lattice reduction finds those short vectors when the deviations are small relative to the modulus and there are enough signatures. The number of signatures needed scales inversely with the number of leaked bits per signature, so a nonce that leaks a few bits is dangerous when an attacker can collect many signatures, and a fully repeated nonce is the degenerate case where one pair suffices. The techniques are those of Nguyen and Shparlinski’s analysis of DSA, and the practical thresholds have tightened as reduction algorithms have improved.

The practical lesson is that a nonce has to be uniform across the full range, not merely unpredictable. A nonce drawn from a 64-bit generator and zero-extended to the scalar width is a nonce whose value is confined to a range of about $2^{64}$, which is small enough that a lattice built from a modest number of signatures recovers the key outright; the top bits are not secret at all, they are zero. The same applies to a generator that always sets certain bits, or that emits values from a counter with a fixed stride. Each of these reduces the entropy of $k$ per signature, and the hidden-number machinery converts that reduction into a key recovery given enough samples.

Deterministic nonces and their own trap

RFC 6979 replaces the random nonce with a deterministic function of the private key and the message hash: HMAC-based derivation that produces a candidate $k$ and retries with a counter if the candidate is out of range. For a given key and message, the nonce is fixed, so there is no state to repeat and no entropy to run dry. Two different messages give different nonces, because the message hash is an input, so the reuse attack does not apply.

The determinism has a consequence that is easy to overlook. If the same message is signed twice, the same nonce results, and the signatures are byte-identical. That is harmless for security, because the attacker already has that signature. It is not harmless for any system that treats a signature as a unique identifier or that expects a fresh signature per transaction; those systems must add their own identifier rather than relying on the signature bytes.

Deterministic derivation also makes the nonce as strong as the key derivation. If the private key is leaked, all past nonces are recoverable, but so is the private key, so nothing additional is lost. If the hash used inside the derivation is weak, the nonce inherits that weakness. The construction is designed to make the nonce behave like a random oracle output for each distinct (key, message) pair, and it is specified in a way that implementations can test against published vectors.

The alternative that avoids both problems is signing with a scheme where the nonce is not a separate secret at all. Ed25519 derives its scalar from a hash of the private key and includes a per-signature random value in the nonce when the hedged variant is used, and the failure mode of a repeated nonce is different, as the Ed25519 construction describes. The hedging preserves determinism as a fallback while removing the dependence on a single random draw.

What the verifier must check, and what it cannot

A verifier takes $(r, s)$, computes $w = s^{-1} \bmod n$, $u_1 = z w \bmod n$, $u_2 = r w \bmod n$, computes the point $u_1 G + u_2 Q$ for the public key $Q$, and accepts if its $x$-coordinate reduced modulo $n$ equals $r$. The verifier learns nothing about $k$ from this, and no property of the signature reveals whether the nonce was reused. Detection has to happen outside the primitive: by comparing $r$ values across a corpus of signatures, which is what a public ledger makes possible, or by controlling the signing process so that reuse cannot occur.

Range checks are part of verification and are frequently the difference between a sound implementation and a broken one. Both $r$ and $s$ must lie in $[1, n-1]$. A verifier that accepts $s = 0$ or a value outside the group order can be attacked, and the check costs two comparisons. Some implementations accept $r = 0$ because it does not occur for honest signatures, but the acceptance of an out-of-range value can produce a valid verification for a message the signer never signed.

Signature malleability is another consequence of the algebra. For a valid $(r, s)$, the pair $(r, n - s)$ also verifies, because the verification equation is symmetric in the sign of $s$ once the point is negated. Both encodings are accepted by most verifiers, so a system that identifies a transaction by its signature bytes can be made to see two distinct identifiers for the same signed content. Bitcoin’s early handling of this is the well-known case; the fix was to require the lower of the two $s$ values, which is a policy choice layered on top of the scheme rather than something ECDSA itself enforces. Protocols that need a unique signature per message must either apply a canonicalization rule or use a scheme, such as RSA-PSS with strict encoding checks, where the encoding is unique.

Choosing the hash and the curve

ECDSA is defined over any prime-order group with an efficiently computable order, and the standard specifies curves of several sizes. The hash output is truncated or expanded to the bit length of $n$ before use in the equations, and the rule is truncation of the leftmost bits. A 512-bit hash on a 256-bit curve uses its leftmost 256 bits, so the collision resistance of the hash beyond 128 bits contributes nothing to the signature’s security; the binding property that matters is the preimage and second-preimage resistance at the curve’s security level.

Nonce handling is where the implementation, not the standard, determines the outcome. A signature scheme whose security proof assumes a uniformly random nonce will be broken by an implementation that supplies a good-but-biased one, and the break will not show up in any test that checks correctness. The only reliable defence is to control the nonce generation with a specified construction and to treat any deviation as a defect: deterministic derivation built from HMAC, a hardware generator with a documented failure mode, or a scheme that removes the nonce from the interface entirely.