Introduction

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)(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 kk, 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.

Try It: Recover 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 y2≡x3+ax+b(modp)y^2 \equiv x^3 + ax + b \pmod{p} with a generator point GG of prime order nn. A private key dd is a secret integer; the public key is the curve point Q=dGQ = dG.

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

<p class="hint">Tiny ECDSA over <b>y² ≡ x³ + 2x + 2 (mod 17)</b>, generator G=(5,1), order n=19.
    Two messages signed with the <em>same</em> nonce k — watch one formula recover the private key.</p>
<div class="scenario" id="scenario">
  <div class="params" id="params"></div>
</div>
<div class="btns">
  <button id="btn-reveal" type="button">Reveal k and recover private key d</button>
  <button id="btn-new" type="button" class="ghost">New random scenario</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Tiny elliptic curve: y² ≡ x³ + 2x + 2 (mod 17) ──────────────────────
// Points (precomputed multiples of G=(5,1), order n=19):
// This is a standard toy curve used in textbooks (order-19 subgroup).
const p = 17, a = 2, n = 19;
const G = { x: 5, y: 1 };

function mod(x, m) { return ((x % m) + m) % m; }
function modInv(a, m) {
  // Extended Euclidean algorithm
  let [old_r, r] = [a, m], [old_s, s] = [1, 0];
  while (r !== 0) { const q = Math.floor(old_r / r); [old_r, r] = [r, old_r - q * r]; [old_s, s] = [s, old_s - q * s]; }
  return mod(old_s, m);
}
function pointAdd(P, Q) {
  if (!P) return Q; if (!Q) return P;
  if (P.x === Q.x && P.y === Q.y) {
    // Point doubling
    const lam = mod(mod(3 * P.x * P.x + a, p) * modInv(mod(2 * P.y, p), p), p);
    const x3 = mod(lam * lam - 2 * P.x, p);
    return { x: x3, y: mod(lam * (P.x - x3) - P.y, p) };
  }
  if (P.x === Q.x) return null; // point at infinity
  const lam = mod(mod(Q.y - P.y, p) * modInv(mod(Q.x - P.x, p), p), p);
  const x3 = mod(lam * lam - P.x - Q.x, p);
  return { x: x3, y: mod(lam * (P.x - x3) - P.y, p) };
}
function scalarMul(k, P) {
  let R = null, Q = P, exp = ((k % n) + n) % n;
  while (exp > 0) { if (exp & 1) R = pointAdd(R, Q); Q = pointAdd(Q, Q); exp >>= 1; }
  return R;
}

// ── Precompute all valid scalar multiples of G (1..n-1) ──────────────────
const POINTS = [];
for (let i = 1; i < n; i++) POINTS.push({ k: i, pt: scalarMul(i, G) });

// ── ECDSA sign (returns {r,s} or null if r==0) ────────────────────────────
function sign(h, d, k) {
  const R = scalarMul(k, G);
  const r = mod(R.x, n); if (r === 0) return null;
  const s = mod(modInv(k, n) * mod(h + d * r, n), n); if (s === 0) return null;
  return { r, s };
}

// ── Generate a random scenario ────────────────────────────────────────────
function randInt(lo, hi) { return lo + Math.floor(Math.random() * (hi - lo + 1)); }
let scenario = null;

function newScenario() {
  document.getElementById('result').textContent = '';
  document.getElementById('result').className = 'result';
  document.getElementById('steps').className = 'steps';
  document.getElementById('steps').innerHTML = '';
  document.getElementById('btn-reveal').disabled = false;

  let d, k, h1, h2, sig1, sig2;
  do {
    d  = randInt(2, n - 2);   // private key
    k  = randInt(2, n - 2);   // REUSED nonce
    h1 = randInt(1, n - 1);   // hash of message 1
    h2 = randInt(1, n - 1);   // hash of message 2 (different)
    if (h1 === h2) continue;
    sig1 = sign(h1, d, k);
    sig2 = sign(h2, d, k);
  } while (!sig1 || !sig2 || sig1.r !== sig2.r);

  const Q = scalarMul(d, G);
  scenario = { d, k, h1, h2, sig1, sig2, Q };

  const params = document.getElementById('params');
  params.innerHTML =
    fmt('<b>Curve:</b> y² ≡ x³ + 2x + 2 (mod 17), G=(5,1), order n=19<br><b>Public key Q:</b> (%x%, %y%)<br><b>Signature 1</b> on h₁=%h1%: &nbsp;r=%r%, s₁=%s%<br><b>Signature 2</b> on h₂=%h2%: &nbsp;r=%r2%, s₂=%s2%<br><span style="color:#c92f3c;font-size:.82rem">⚠ Both signatures share the same r — same nonce k was used!</span>', { x: Q.x, y: Q.y, h1: h1, r: sig1.r, s: sig1.s, h2: h2, r2: sig2.r, s2: sig2.s });
}

// ── Key recovery from nonce reuse ─────────────────────────────────────────────
function recover() {
  if (!scenario) return;
  const { d, k: trueK, h1, h2, sig1, sig2, Q } = scenario;

  // k = (h1 - h2) / (s1 - s2)  mod n
  const num_k = mod(h1 - h2, n);
  const den_k = mod(sig1.s - sig2.s, n);
  const kRec  = mod(num_k * modInv(den_k, n), n);

  // d = (s1*k - h1) / r  mod n
  const num_d = mod(sig1.s * kRec - h1, n);
  const dRec  = mod(num_d * modInv(sig1.r, n), n);

  // Verify
  const Qcheck = scalarMul(dRec, G);
  const correct = dRec === d && Qcheck && Qcheck.x === Q.x && Qcheck.y === Q.y;

  const res = document.getElementById('result');
  res.className = 'result ' + (correct ? 'ok' : 'bad');
  res.textContent = correct
    ? fmt('✓ Private key recovered: d = %dRec%  (secret key was %trueK% — exposed!)', { dRec: dRec, trueK: trueK })
    : '✗ Recovery failed (unexpected — check the math).';

  const steps = document.getElementById('steps');
  steps.className = 'steps show';
  steps.innerHTML =
    fmt('<span class="label">Step 1 – recover k:</span>k = (h₁ − h₂) · (s₁ − s₂)⁻¹ mod n<br>  = (%h1% − %h2%) · (%s% − %s2%)⁻¹ mod %n%<br>  = %num_k% · %modInv% mod %n%<br>  = <b>%kRec%</b><br><br><span class="label">Step 2 – recover d:</span>d = (s₁·k − h₁) · r⁻¹ mod n<br>  = (%s%·%kRec% − %h1%) · %modInv2% mod %n%<br>  = %num_d% · %modInv2% mod %n%<br>  = <b>%dRec%</b><br><br><span class="label">Verify:</span> d·G = (%v%, %v2%) = Q = (%x%, %y%) ✓', { h1: h1, h2: h2, s: sig1.s, s2: sig2.s, n: n, num_k: num_k, modInv: modInv(den_k, n), kRec: kRec, modInv2: modInv(sig1.r, n), num_d: num_d, dRec: dRec, v: Qcheck ? Qcheck.x : '?', v2: Qcheck ? Qcheck.y : '?', x: Q.x, y: Q.y });

  document.getElementById('btn-reveal').disabled = true;
  console.log('True d:', d, '| Recovered d:', dRec, '| True k:', trueK, '| Recovered k:', kRec);
}

document.getElementById('btn-reveal').addEventListener('click', recover);
document.getElementById('btn-new').addEventListener('click', newScenario);
newScenario();
Result
Console

Notice: verifying a signature is fast public-key arithmetic. Breaking a key requires that fatal repeated kk — 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 kk 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.

The Real Complexity

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=dGQ = dG on a well-chosen curve, finding dd is believed to be computationally infeasible for classical computers. The best known classical algorithms run in O(n)O(\sqrt{n}) time via Pollard's rho — for a 256-bit curve with n≈2256n \approx 2^{256}, that is roughly 21282^{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 kk. Security collapses the instant kk is reused. If two signatures (r,s1)(r, s_1) and (r,s2)(r, s_2) share the same rr (same kk), then:

k=h1−h2s1−s2(modn)k = \frac{h_1 - h_2}{s_1 - s_2} \pmod{n}

d=s1k−h1r(modn)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 kk 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 kk 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ecdsa/Content licensed under CC BY-NC 4.0.