ECDSA

Every time your browser opens an HTTPS connection, every time a Bitcoin transaction is broadcast, every time an SSH key is checked — there is a good chance an ECDSA signature is doing the heavy lifting. The algorithm combines elliptic-curve arithmetic with a carefully chosen random number to produce a pair $(r, s)$ that proves you hold a private key without ever revealing it.

The math is elegant. The security is solid — under one assumption: the random number, called the nonce $k$, must be chosen fresh, uniformly at random, and never repeated. Not almost never. Never.

If the same nonce is used for two different messages, an attacker who sees both signatures can recover your private key using nothing more exotic than basic arithmetic. No quantum computer. No years of brute force. Just two subtractions and a modular division. The attack is that simple, and the consequences are that total.

This catastrophe has struck real systems. In 2010 the Sony PlayStation 3 signed all its firmware with the same nonce, and security researchers recovered the console's master signing key in minutes. In 2013 a flawed random-number generator on Android Bitcoin wallets caused the same failure, draining funds. Today, the lesson is baked into every serious cryptographic library: ECDSA nonce reuse is not a theoretical weakness — it is a death sentence for a key.

The demo below uses a tiny elliptic curve over a small prime field so all the arithmetic fits on screen. The curve is $y^2 \equiv x^3 + ax + b \pmod{p}$ with a generator point $G$ of prime order $n$. A private key $d$ is a secret integer; the public key is the curve point $Q = dG$.

To sign a message $m$ you pick a secret nonce $k$, compute $R = kG$, let $r = R.x \bmod n$, and output $s = k^{-1}(h + dr) \bmod n$ where $h$ is the hash of $m$. If $k$ is reused across two messages, the nonce cancels out and you can solve for $d$ directly.

<p class="hint">{{hint}}</p>
<div class="scenario" id="scenario">
  <div class="params" id="params"></div>
</div>
<div class="btns">
  <button id="btn-reveal" type="button">{{btn_reveal}}</button>
  <button id="btn-new" type="button" class="ghost">{{btn_new}}</button>
</div>
<div class="result" id="result"></div>
<div class="steps" id="steps"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.params { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 8px; padding: .7rem 1rem; font-size: .88rem; line-height: 1.8; }
.params b { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .8rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-weight: 700; font-size: 1rem; margin-bottom: .5rem; min-height: 1.4em; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }
.steps { font-size: .83rem; color: #333; line-height: 2; font-family: ui-monospace, monospace; background: #f8f9fa; border-radius: 8px; padding: .6rem .9rem; display: none; }
.steps.show { display: block; }
.label { color: #888; margin-right: .3em; }

// Code not found

Notice: verifying a signature is fast public-key arithmetic. Breaking a key requires that fatal repeated $k$ — but once it appears, the recovery is instant. No brute force, no guessing. The private key falls out of two linear equations.

This is why modern libraries like libsodium and Ed25519 use deterministic nonces (RFC 6979): they derive $k$ from a hash of the private key and the message, so the same message always produces the same nonce but different messages always produce different ones. Randomness failure becomes impossible by design.

ECDSA security has two layers, and the gap between them is the whole story.

The hard layer — elliptic-curve discrete logarithm (ECDLP). Given a public key $Q = dG$ on a well-chosen curve, finding $d$ is believed to be computationally infeasible for classical computers. The best known classical algorithms run in $O(\sqrt{n})$ time via Pollard's rho — for a 256-bit curve with $n \approx 2^{256}$, that is roughly $2^{128}$ group operations, far beyond any foreseeable hardware. This problem is not proven hard (it could fall if a breakthrough in discrete logarithms emerged), but decades of cryptanalysis have produced no efficient attack. Status: widely believed hard, not formally proven.

The fragile layer — the nonce $k$. Security collapses the instant $k$ is reused. If two signatures $(r, s_1)$ and $(r, s_2)$ share the same $r$ (same $k$), then:

$$k = \frac{h_1 - h_2}{s_1 - s_2} \pmod{n}$$

$$d = \frac{s_1 k - h_1}{r} \pmod{n}$$

These are two lines of arithmetic. The ECDLP hardness is bypassed entirely because the unknown $k$ appears in two equations simultaneously — it is not a discrete log problem at all, just a system of linear congruences. This is why the attack requires no special computation: it runs in microseconds.

Partial nonce leakage is nearly as bad. If an attacker learns even a handful of bits of $k$ across many signatures — via timing side-channels, power analysis, or cache attacks — lattice methods (specifically the hidden number problem, solved with LLL reduction) can recover the full private key from hundreds of signatures. The lattice shortest vector problem is the underlying tool; it is believed hard in general but tractable enough in practice when bias is measurable.

Quantum threat. Shor's algorithm runs on a quantum computer in polynomial time and solves ECDLP directly, breaking ECDSA regardless of nonce discipline. This is why post-quantum standards (NIST PQC, 2024) are replacing elliptic-curve signatures with lattice- or hash-based schemes.

ECDSA and its nonce-reuse catastrophe are not textbook curiosities — they have shaped real security decisions:

• TLS / HTTPS: virtually every HTTPS handshake uses an elliptic-curve key exchange or signature. Libraries like OpenSSL now use RFC 6979 deterministic nonces to prevent randomness failures.
• Bitcoin and Ethereum: every transaction is an ECDSA signature over the secp256k1 curve. The 2013 Android wallet theft demonstrated that a weak random-number generator alone is enough to drain funds — no malware required.
• PlayStation 3 (2010): Sony signed all PS3 firmware with a fixed nonce. George Hotz (geohot) and fail0verflow recovered the root signing key, enabling arbitrary code execution and homebrew on every PS3 ever manufactured.
• SSH host keys: SSH servers authenticate themselves with ECDSA or Ed25519 keys. A virtual machine cloned with a copied key file — and a predictable RNG seed — can produce repeated nonces.
• Code signing and software supply chains: operating-system update mechanisms and app stores rely on signed binaries. A compromised signing key, recovered through nonce reuse, lets an attacker push malicious updates to millions of devices.

The lesson the community drew is now standard practice: never let applications near raw ECDSA nonce generation. Use digital signatures built on Ed25519 (which is inherently deterministic) or use RFC 6979 when ECDSA is mandatory. The underlying elliptic-curve hardness is real; the nonce discipline is a human engineering problem that deterministic schemes solve completely.

ECDSA is a remarkable construction: a 256-bit private key that can sign messages in microseconds, with security that rests on a problem no classical computer has cracked in decades. But it has a razor-thin margin for error. The entire edifice sits on a single secret random number chosen fresh for every signature.

Reuse that number — even once — and the private key falls out of two subtractions. The PlayStation 3, Android Bitcoin wallets, and countless other systems have learned this lesson the hard way.

The elegant fix is to remove randomness from the equation entirely: derive the nonce deterministically from the private key and the message hash (RFC 6979), as Ed25519 does by construction. The hard part — the elliptic-curve discrete logarithm — stays hard. The fragile part — nonce generation — becomes impossible to mishandle.

Security is not just about choosing hard problems. It is about never letting a single engineering slip erase the hardness you chose.