ECDSA

Elliptic curves entered cryptography in 1985, proposed independently by Neal Koblitz and Victor Miller. The appeal was efficiency: the discrete logarithm problem seemed much harder on a curve than in the integers modulo a prime, so a 256-bit curve key offered roughly the security of a 3072-bit RSA key. Scott Vanstone adapted the existing Digital Signature Algorithm to curves in 1992, and ECDSA was standardised as ANSI X9.62 in 1999. Bitcoin adopted it in 2009, which put the algorithm in front of a far larger and more adversarial audience than the standards bodies had imagined.

Fix a curve, a base point G on it, and the number n of points G generates. A private key is a number d; the matching public key is the point Q = dG. Recovering d from Q means solving the elliptic-curve discrete logarithm problem, which nobody knows how to do at full size.

To sign a message hash h, pick a one-time random number k — the nonce — and compute:

R = kG  ·  r = R_x mod n  ·  s = k⁻¹(h + rd) mod n

The signature is the pair (r, s). A verifier who has only Q, h and the signature recomputes a point from them and checks that its x-coordinate comes back to r. The private key never appears in the check — that asymmetry is the whole point.

This runs a genuine curve, small enough to read: y² = x³ + 3x + 2 over the integers mod 97. It has 102 points plus the point at infinity, so n = 103 — a prime, which means every point generates the whole group. Real ECDSA uses the same arithmetic with numbers around 2²⁵⁶.

Press Sign.

The nonce k must be secret, and it must be different every time. Sign two different messages with the same k and the two equations share an unknown. Subtract them and k falls out; substitute back and the private key follows. No lattice, no supercomputer — secondary-school algebra:

k = (h₁ − h₂) / (s₁ − s₂)   then   d = (s₁k − h₁) / r

In December 2010 the group fail0verflow demonstrated that Sony's PlayStation 3 signed every firmware release with the same fixed k. The console's master signing key was recoverable by anyone who owned two signed updates. Sony could not fix it with a patch: the key was the root of the console's trust, and it was now public. The identical bug drained Bitcoin wallets in 2013 when an Android random-number generator repeated its output.

Sign two messages with one nonce, then attack.

No practical attack is known against ECDSA's mathematics on a well-chosen curve. Every notable break has been an implementation failure, and almost all of them concern the nonce: repeating it, generating it with a weak random source, or leaking a few of its bits through a timing or cache side channel. Even partial leakage is fatal — recovering a handful of nonce bits across a few hundred signatures lets an attacker reconstruct the private key by lattice reduction.

The standard defence is to stop generating k randomly at all. Deterministic ECDSA (RFC 6979) derives the nonce from the private key and the message hash together, so identical messages produce identical signatures and different messages cannot collide. EdDSA (Ed25519) builds the same idea into the scheme by design, which is one reason it is now often preferred.

Like all discrete-logarithm cryptography, ECDSA falls to a sufficiently large quantum computer running Shor's algorithm. Its replacement, ML-DSA, rests on lattice problems instead — the reason that shift works is set out in the Learning With Errors exhibit.

Every HTTPS connection to a site with an EC certificate verifies an ECDSA signature during the handshake. Every Bitcoin and Ethereum transaction is authorised by one. Secure-boot chains in phones, games consoles and cars use ECDSA or its close relatives to check that firmware came from the manufacturer. When your browser shows a padlock, an elliptic-curve signature was almost certainly checked to put it there.