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, for which no practical classical attack is known on properly chosen large groups.

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 except the identity generates the whole group. Real ECDSA uses much larger approved parameters and specified hash-to-integer processing. This browser toy exposes its keys and uses small integers; it is not a secure signing tool.

Press Sign.

The nonce k must be secret. Reusing it with distinct message-hash values modulo n is dangerous: the two signature equations then 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 fail0verflow demonstrated that reused ECDSA nonces exposed PlayStation 3 signing keys. The example shows why secrecy of the long-term key is not enough: the per-signature nonce must be generated and handled correctly. Deterministic nonce generation, as specified by RFC 6979, is one established way to avoid relying on fresh randomness for each signature; it does not remove other implementation risks.

Sign two messages with one nonce, then attack.

No practical classical attack is known against properly parameterised ECDSA with suitable curves and hashes. Implementations can fail through nonce reuse, weak randomness, faults, or side-channel leakage. Partial nonce leakage can enable key recovery, but success depends on the amount and structure of leakage, measurement noise and the number of signatures available; it is not an unconditional result for any leaked bit.

Deterministic ECDSA derives the nonce from the private key and message hash, removing dependence on fresh signing randomness. With the same inputs it produces the same signature. It does not guarantee collision-free nonces for different messages, and it does not remove side-channel or fault risks. Correct randomised ECDSA is also possible; secure key generation still needs suitable randomness.

Source: RFC 6979 (August 2013), §§1, 3.2 and 4, an Informational RFC. Its deterministic nonce procedure retains implementation-security requirements. This exhibit uses visitor-selected toy nonces and does not implement RFC 6979.

Like all discrete-logarithm cryptography, ECDSA falls to a sufficiently large quantum computer running Shor's algorithm. ML-DSA is one standardized post-quantum signature option and uses module-lattice assumptions — 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.