Elliptic Curve Digital Signature Algorithm (ECDSA) Explained

ECDSA is the elliptic-curve variant of the Digital Signature Algorithm, defined over finite abelian groups derived from carefully chosen elliptic curves. It provides digital signatures with much smaller keys and signatures than RSA at equivalent security levels: a 256-bit elliptic curve gives roughly 128 bits of security, comparable to RSA-3072, but with keys thirty times smaller and far faster signing and verification.

A signer holds a private scalar d and a public point Q = dG on the curve, where G is a standardized base point of prime order n. To sign a message, the signer hashes it to an integer e, selects a random nonce k in [1, n-1], computes the point R = kG, sets r to R’s x-coordinate reduced mod n, and computes s = k^-1 (e + dr) mod n. The signature is the pair (r, s), and it is typically encoded in ASN.1 DER or compact 64-byte form.

Verification reverses the process. The verifier computes u1 = es^-1 and u2 = rs^-1, evaluates u1G + u2Q, and checks whether the result’s x-coordinate equals r mod n. A valid signature implies that the signer knew d, because otherwise the linear combination would only coincide at R by chance. Security rests on the elliptic curve discrete logarithm problem: given Q, recovering d is computationally infeasible on properly chosen curves.

A critical implementation requirement is nonce uniqueness and secrecy. If k repeats across two signatures with the same key, an attacker can subtract the equations and solve for d directly. Predictable or partially leaked k values are just as fatal. The 2010 Sony PlayStation 3 secure-boot failure happened because the same k was used for every signature, letting anyone extract the private key. Hardware RNG failures and VM snapshot restores have caused similar breaks repeatedly in the Bitcoin ecosystem.

Deterministic nonces defined in RFC 6979 eliminate reliance on fresh randomness by deriving k from the private key and message hash via HMAC-based iteration. This keeps signatures reproducible and removes a whole failure class, at the cost of making some fault-injection attacks slightly easier, which is why some implementations add extra entropy anyway. Alternatives such as EdDSA (Ed25519) take determinism further and are often preferred today, but ECDSA remains dominant in TLS certificates, Bitcoin, and Ethereum.