ECDSA

ECDSA signs TLS certificates, hardware tokens and cryptocurrency transactions. Nobody has come close to solving the elliptic-curve discrete logarithm behind it, yet ECDSA keys are lost regularly, and almost always the same way: through the random number used once per signature.

Rests on
The ECDLP, and a uniformly random secret nonce for every signature
Standards
FIPS 186-5; SEC 1; ANSI X9.62; deterministic nonces in RFC 6979
Sizes
P-256: 64-byte signature (r, s); 33-byte compressed public key
Best known attack
Pollard's rho on the curve, about 2128 for P-256. In practice, reused, biased or leaked nonces
Quantum
Broken by Shor's algorithm

Signing and verifying

The public parameters are a curve with a base point G of prime order n. A private key is an integer d, and the public key is Q = dG. To sign a message, hash it to an integer z, then:

  1. Choose a secret nonce k uniformly between 1 and n − 1.
  2. Compute the point kG and let r be its x-coordinate mod n.
  3. Compute s = k−1(z + rd) mod n. The signature is (r, s).

To verify, compute w = s−1, then the point (zw)G + (rw)Q, and accept if its x-coordinate mod n equals r. It works because (zw)G + (rw)Q = w(z + rd)G = kG.

The example on this page runs on the real P-256 curve, at full size, in the code that builds this page. A key pair was drawn, and the message "Pay Alice 10 coins" was signed with a random nonce:

Q.x = 16c5e7e8705a2ae2474767308b755c54cff1af229cf3ff351d60d391a5b124fc
Q.y = a59d5cb1f6b4902dd6350ac628dc38e3c6ed87cf2d4cebc525bbe943d703d064

r   = 14ce431740968d40033648f63e34d260f5d329aa70f2e516e278cab3ee9411f2
s   = da76a7337f0dc8a2b0503456cfa3d59620b92cc7e33f2afe876f7616afa8a9e8

A P-256 public key and a signature on "Pay Alice 10 coins", in hexadecimal

It verifies against Q, and does not verify for "Pay Bob 20 coins".

One nonce, two signatures

Look at the signing equation as an attacker would. It is one linear equation, s = k−1(z + rd), in two unknowns, k and d. A single signature reveals nothing, because every d has a matching k. But if the same k is ever used for two messages, the two signatures share r and give two equations in the same two unknowns:

k = (z1 − z2) / (s1 − s2),   d = (s1k − z1) / r  (mod n) Two signatures with the same nonce give up the private key

The build signed "Pay Alice 10 coins" and "Pay Bob 20 coins" with the same nonce. Both signatures are valid, and both have the same r, which is how the reuse is spotted from outside:

r   = cb07b062b8d7af8d0ed281924c8a94e67c229175ac1fbd2090f3a523c502ea9d
s1  = f872e3eb0b3f2c3e6ba18e4b9129b95828f180a9df9216a0c7481e62da033b1a
s2  = b6cf16d1daee0952d46931a819397b6e41243a6544eb13cc8cec141a3a050d0f
z1  = f359021fadd6e209e61397188b22911c97a99c13311bee82edfbd9a5bde91991
z2  = 6a03b853ee8000b6c76a898ed9a88f87bc48000a2b83454a37e6d083ac6d52f6

k   = ea7a3bf4a4f26de35499523182aab29ad7f357bf4e2f13f05922c31f81e00562
d   = 1bfed262bd821be1057f723be45270d37e62710eb8dac0fe7bc0c090abebdba1

The two signatures, the two SHA-256 hashes, and what the formulas above recover

The recovered d satisfies dG = Q, so it is the private key. The build then signs "Pay Mallory everything" with it, and that signature verifies under the victim's public key. There is no search here and no dependence on the curve's size: two modular inversions and a few multiplications break the key.

This has happened in production. In 2010 the fail0verflow group showed that Sony signed PlayStation 3 software with a fixed nonce, and recovered the signing key. In 2013 a flaw in Android's SecureRandom caused Bitcoin wallets to repeat nonces, and coins were taken from the affected addresses. Scanning public blockchains for repeated r values still turns up keys.

Deterministic nonces

The standard fix is to stop needing a random number generator at signing time. RFC 6979 derives k deterministically from the private key and the message hash with HMAC. The same message always gets the same nonce, and different messages get unrelated ones. Repeating k across different messages then needs an HMAC collision. EdDSA builds the same idea into its definition, and FIPS 186-5 allows deterministic ECDSA.

Deterministic signing has a weakness of its own. Because the same computation happens every time, a fault injected during one signing can be compared with a correct signature on the same message, and similar fault attacks work much as they do on RSA with CRT. Hedged signing, which mixes fresh randomness into the deterministic derivation, keeps the protection against bad generators while defeating these comparisons. It is the default in ML-DSA.

Biased and leaked nonces

The nonce does not have to repeat to be fatal. Each signature gives a linear relation between k and d. If an attacker knows a few bits of each k, from a timing side channel, a biased generator or a truncated random number, many signatures together form an instance of the hidden number problem, which lattice reduction solves. Published attacks recover P-256 and secp256k1 keys from nonce leaks of a few bits per signature, given enough signatures. Constant-time scalar multiplication and nonces drawn uniformly mod n, not reduced from a slightly shorter string, are what prevents this.

Malleability

If (r, s) is a valid signature, so is (r, n − s): negating s negates w, and the verification point becomes −kG, which has the same x-coordinate. For the signature above, n − s is

s'  = 258958cb80f2375e4fafcba9305c2a699c2dcde5c3d873866c4a54ac4cba7b69

The second valid signature on the same message, under the same key

and it verifies. This does not let anyone sign a new message, but it breaks any system that identifies a signed object by the hash of its signature. Bitcoin transaction identifiers had exactly that problem, and Bitcoin now requires the smaller of s and n − s. EdDSA and Schnorr signatures as in BIP-340 are defined so that this does not arise.

Where it stands

Against the curve itself ECDSA is as strong as the ECDLP, about 2128 for P-256 and secp256k1; see the ECDLP note. Against a quantum computer running Shor's algorithm it falls completely, and NIST IR 8547 proposes disallowing it after 2035. Until then, reviewing an ECDSA implementation is mostly reviewing its nonces: where they come from, whether they are uniform mod n, and whether they leak through timing.

Primary sources

  1. NIST FIPS 186-5, Digital Signature Standard (DSS) (2023)
  2. T. Pornin, RFC 6979, Deterministic usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) (2013)
  3. Standards for Efficient Cryptography Group, SEC 1: Elliptic Curve Cryptography, version 2.0 (2009)
  4. fail0verflow, "Console hacking 2010: PS3 epic fail", 27th Chaos Communication Congress (2010)
  5. N. Howgrave-Graham and N. P. Smart, "Lattice attacks on digital signature schemes", Designs, Codes and Cryptography 23 (2001)