Computational cryptography › Public-key encryption and key exchange › Classical number theory › Elliptic-curve discrete log
SIGNATUREPrimitiveGGMCRH

ECDSA

In plain words

The most widely used digital signature: proof that a message came from the owner of a key.

The idea: Your private key is a number x and your public key is x·G. To sign, you pick a fresh random number k, compute the point k·G, and combine k, x and the message hash into a number s. Checking needs only the public key: the verifier recombines the hash, s and the public key and must land on the same point. Because k and x are tied together in one simple equation, anyone who learns k, or sees it reused for two messages, can solve for x: the famous nonce weakness.

Why it matters: Signs website certificates, passkeys, and every Bitcoin and Ethereum transaction.

The details

On the map: certificates, passkeys / FIDO2

The elliptic-curve version of DSA and the most widely deployed signature[1]: TLS certificates (P-256), passkeys and FIDO2 security keys, Bitcoin and Ethereum transactions (secp256k1).

Its security proofs need idealized models (the generic group model, GGM)[2] and a collision-resistant hash (CRH). It is notoriously fragile with randomness: a reused or slightly biased nonce reveals the private key (PlayStation 3 in 2010[3], Android Bitcoin wallets in 2013[4]). Deterministic nonces (RFC 6979)[5] remove that risk.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

GGM
Its security proof only covers attackers who use the group as a black box (the generic group model), an idealization.
CRH
Hash-then-sign: the message is hashed before signing, so a collision in the hash function lets an attacker move a signature onto a different message.

References

  1. NIST. Digital Signature Standard (DSS). NIST FIPS 186-5, 2023. doi:10.6028/NIST.FIPS.186-5
  2. Daniel R. L. Brown. Generic Groups, Collision Resistance, and ECDSA. Designs, Codes and Cryptography, 2005. doi:10.1007/s10623-003-6154-z
  3. fail0verflow. Console Hacking 2010: PS3 Epic Fail. 27th Chaos Communication Congress, 2010. media.ccc.de/v/27c3-4087-en-console_hacking_2010
  4. bitcoin.org. Android Security Vulnerability. 2013. bitcoin.org/en/alert/2013-08-11-android
  5. T. Pornin. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). RFC 6979, 2013. rfc-editor.org/rfc/rfc6979