The Math Held; The Interface Leaked: A Field Guide to Digital Signatures

1. Two Signatures, One Nonce, and the Master Key Fell Out#

In December 2010, at the 27th Chaos Communication Congress, a group called fail0verflow put a single slide on the screen that ended the security of the PlayStation 3 ^[1]. Sony had signed every piece of PS3 firmware with ECDSA, a scheme whose security rests on a discrete logarithm no one has ever solved for a 256-bit curve.

Sony's engineers did not need to fail. They reused the same secret random number -- the per-signature nonce -- for every signature, and any two signatures that share a nonce give up the private key by grade-school algebra. The curve was pristine. The master key fell out of two subtractions.

Twelve years later, the failure jumped one layer up the stack. Java shipped an ECDSA verifier that accepted the signature (r, s) = (0, 0) for any message and any public key -- "Psychic Signatures," CVE-2022-21449, a CVSS 7.5 flaw that forged TLS handshakes, signed JWTs, SAML assertions, and WebAuthn responses alike ^[4], ^[5]. One break leaked a private key through the nonce; the other waved a forgery through at the verifier. Neither touched the underlying hardness assumption. Nobody solved a discrete log. Nobody factored a modulus.

That is the pattern this article is about, worth stating as a question you can carry through every section: when a signer or verifier meets a value it did not create, what secret does it leak, or what forgery does it wave through? The answer is almost never "the math was weak." A signature scheme is only as safe as three things it hands the caller and refuses to decide for you: the per-signature nonce, the signature's canonical form, and the verifier's acceptance rule. ECDSA outsources all three at once.

That is why one scheme -- its elliptic-curve discrete logarithm fully intact -- spawned four categorically different disasters: the reused nonce of the PS3, the drained Android Bitcoin wallets, the malleable transactions that unsettled Bitcoin, and the psychic verifier in Java. You half-know these headlines already. This is the one sentence underneath all of them.

The math held; the interface leaked.

The rest of signature history since ECDSA is one effort to pull those three surfaces back inside the scheme, so the caller can no longer get them wrong. To see why a shared random number hands over a private key -- and why "just use Ed25519" is a real answer but not the whole one -- you first have to be precise about what a signature promises, and the three jobs ECDSA quietly delegates to you.

2. What a Signature Actually Is (and the Three Things ECDSA Hands You)#

Everyone knows the one-liner: sign with the private key, verify with the public key. That one-liner hides three decisions the scheme refuses to make for you. Start with the part that is simple.

A digital signature scheme is three algorithms. KeyGen -> (pk, sk) produces a public verification key and a private signing key. Sign(sk, m) -> sigma turns a message and the private key into a signature. Verify(pk, m, sigma) -> {accept, reject} lets anyone holding the public key check the pair. The word anyone is the whole point.

A message authentication code also proves a message is authentic, but it verifies with the same secret used to produce it, so only insiders can check it. A signature is publicly verifiable and therefore non-repudiable: the entire world can confirm it, and only the holder of sk could have produced it.

The bar every scheme is measured against#

"Secure" needs a precise meaning, and cryptographers settled on one in 1988. Goldwasser, Micali, and Rivest defined existential unforgeability under adaptive chosen-message attack, or EUF-CMA: an adversary who may ask you to sign any messages it likes, adaptively, still cannot produce a valid signature on a single new message it never queried ^[6]. That is a demanding bar, and every scheme in this article is designed to clear it.

But notice the exact word: a new message. EUF-CMA says nothing about whether there might be more than one valid signature on a message you did sign. Tighten the game by one word and you get strong unforgeability, SUF-CMA: the adversary cannot produce any new valid signature, even on an already-signed message. The gap between "new message" and "new signature" looks pedantic. It is the entire malleability story that unravels a Bitcoin transaction in a later section, so it is worth planting the seed now.

EUF-CMA does not promise there is only one valid signature per message. A scheme can be perfectly unforgeable in the textbook sense and still let anyone manufacture a second, different signature on a message you already signed. Whether that matters depends on whether your protocol ever treats the signature itself as an identifier.

The thesis, stated as the scheme's interface#

Here is the organizing idea of the field guide. A signature scheme hands the caller three things and quietly makes each one the caller's responsibility. ECDSA is the worked example that outsources all three.

Surface 1, the nonce. To sign, ECDSA needs a fresh secret random number for every signature. Supply a bad one and you leak the private key. Surface 2, the canonical form. A valid ECDSA signature (r, s) has an evil twin (r, n-s) that also verifies, so the caller must decide whether those are "the same" signature. Surface 3, the verifier. ECDSA's acceptance rule involves modular inversions and range checks, and the specification left enough slack that two conformant-looking verifiers can disagree about which signatures are valid. Every deployed break in this article lives in one of these three surfaces.

flowchart TD
KG[KeyGen] --> SK[Private key sk]
KG --> PK[Public key pk]
M[Message] --> SG[Sign]
SK --> SG
N["Surface 1: the per-signature nonce you must supply"] --> SG
SG --> SIG["Signature r and s"]
SIG --> CF["Surface 2: is r and s the same as r and n minus s?"]
CF --> VF[Verify]
PK --> VF
M --> VF
VR["Surface 3: the byte-exact acceptance rule"] --> VF
VF --> OUT{"Accept or reject"}

The academic description of ECDSA that stands in for the paywalled ANSI standard spells out this division of labor: the scheme defines the arithmetic and leaves nonce generation, encoding choices, and verifier strictness to the implementer ^[7], ^[8]. The cleaner schemes we reach later pull these surfaces back inside the definition. BIP-340 Schnorr, for instance, specifies its verifier down to the byte precisely so the caller cannot get surface 3 wrong ^[3].

The table below is the entire article compressed into one grid: read across each row to watch a surface move from "the caller's problem" to "the scheme's problem."

Two of those three surfaces were invented before ECDSA existed: the nonce in 1985, the "form" problem in 1978. To understand why a modern scheme still hands them to you, we have to go back to the moment signatures were only an idea.

3. Where Signatures Came From (1976 to 1996)#

In 1976, two Stanford researchers could describe exactly what a signature must do and had no way to build one. Whitfield Diffie and Martin Hellman's "New Directions in Cryptography" named the requirement -- a private operation that anyone can verify with public information, giving the world a way to hold a signer to their message -- but it offered no algorithm to realize it ^[9]. The problem was posed before it was solved, and the two ways it eventually got solved are the two tracks this whole article runs along.

Track A: the trapdoor line#

Two years later, RSA gave the first concrete construction. Signing is the private-key operation, verifying is the public-key operation, and the trapdoor -- factoring is hard, so inverting the public operation without the private exponent is infeasible -- makes the asymmetry real ^[10].

It worked, and it immediately exhibited surface 2. Textbook RSA, which signs the bare message as $\sigma = m^d \bmod N$, is existentially forgeable: pick any $\sigma$, compute $m = \sigma^e \bmod N$, and you have a valid pair for a message you did not choose but that is still "signed."

It is also multiplicatively malleable, because $\sigma_1 \cdot \sigma_2 \bmod N$ is a valid signature on $m_1 \cdot m_2 \bmod N$. The raw trapdoor has no notion of which messages are legitimately structured, so the caller must impose that structure. Getting that structure right, with a proof, took fifteen years and is the subject of a later section.

Track B: the discrete-log line#

In 1985, Taher ElGamal built the first signature whose hardness rests on the discrete logarithm problem rather than factoring ^[11]. It also introduced the load-bearing footgun that defines the rest of this article: a fresh secret nonce drawn for every single signature. Learn that nonce, or reuse it, and the private key follows. This is where surface 1 enters the lineage, and DSA and ECDSA inherit it unchanged.

The engine and the yardstick#

Two ideas from the late 1980s frame everything after. In 1986, Fiat and Shamir showed how to turn an interactive identification protocol -- prove you know a secret without revealing it -- into a non-interactive signature, by replacing the verifier's random challenge with a hash of the commitment and the message ^[12]. That transform is the engine underneath Schnorr, DSA, and EdDSA, and it comes with a catch we return to in the limits section: its security is argued in the random-oracle model, treating the hash as an ideal random function.

Then, in 1988, GMR gave the field its yardstick, EUF-CMA, the definition every later scheme is measured against ^[6].

The clean template, and the patent that froze it#

In 1989, Claus-Peter Schnorr published the scheme that, in hindsight, got everything right. The signer commits to a random point $R = kG$, computes a challenge $e = H(R \mathbin{\|} m)$ by hashing the commitment and message, and answers with $s = k + ex$, where $x$ is the private key. Verification is a single linear check. That linearity is not a detail; it is the reason the scheme is provable, batchable, aggregatable, and non-malleable, and it is the direct ancestor of EdDSA and BIP-340 ^[13].

There was one problem, and it bent the entire history. Schnorr patented the scheme (US 4,995,082, invented 1989, granted 1991, expired 2008) ^[14]. NIST, which needed a royalty-free national standard, could not use it. So the best-behaved discrete-log signature ever designed sat frozen for two decades while the government standardized around something else. The clean scheme was invented first and deployed last.

timeline
title From an idea to a standard, 1976 to 2020
1976 : Diffie and Hellman name the requirement, no algorithm
1978 : RSA, the first construction, Track A
1985 : ElGamal introduces the per-signature nonce, Track B
1986 : Fiat-Shamir turns identification into signatures
1989 : Schnorr, clean and linear, but patented until 2008
1994 : DSA standardized as FIPS 186
1999 : ECDSA moves DSA onto elliptic curves
2011 : Ed25519 bakes determinism in
2013 : RFC 6979 retrofits deterministic nonces
2020 : BIP-340 Schnorr, byte-exact

With the clean scheme locked behind a patent, the U.S. government needed a signature standard of its own. The choices it made under patent pressure are the reason the worse-behaved scheme shipped to the entire internet first.

4. Padding, DSA, and the Fateful Nonce#

Two tracks, two ways to get it wrong first. RSA had to learn not to sign the bare message. The discrete-log camp had to standardize around a secret it could not afford to leak.

Track A cleans up its form#

The fix for textbook RSA's forgeability is a rule you will hear again: never sign the bare message. Hash it first, then pad the hash into a full-width, unpredictable representative that fills the modulus. Done right, this kills existential forgery -- an attacker can no longer start from a random $\sigma$ and back out a validly structured message -- and it destroys the multiplicative structure that let signatures be multiplied together.

The workhorse encoding is PKCS#1 v1.5, a deterministic padding standardized in the early 1990s and still ubiquitous ^[15]. Full-Domain Hash was the conceptual bridge: hash the message across the entire width of the modulus. And in 1996, Bellare and Rogaway's Probabilistic Signature Scheme (PSS) added a random salt and, with it, the tightest security proof any deployed signature would ever get ^[16], ^[10].

We give PSS its own section later; for now, note only that Track A's first footgun was the form of what it signed, and Track A fixed it by structuring that form.

Track B standardizes, under patent pressure#

The discrete-log camp went a different way, and politics shaped the outcome. In 1991 NIST proposed the Digital Signature Algorithm, and in 1994 it became FIPS 186 ^[17]. DSA is an ElGamal and Schnorr relative, deliberately structured to sidestep both the RSA patent and Schnorr's patent, credited to David Kravitz and assigned to the NSA ^[18]. In dodging the clean patented scheme, DSA inherited ElGamal's design decision without modification: a fresh secret nonce for every signature.

Track B goes to curves#

Through the late 1990s, Certicom and the ANSI X9F1 committee moved DSA onto elliptic curves. The elliptic-curve discrete logarithm is harder per bit than the finite-field version, so ECDSA gets equivalent security from much smaller keys -- 256-bit curves for 128-bit security, against 3072-bit fields for RSA and finite-field DSA. The template was otherwise unchanged, and so was the fateful decision: the same fresh secret nonce, once per signature ^[7].

By the end of the 1990s, an enormous share of the world's authentication rested on Track B: DSA and ECDSA, both carrying a per-signature secret that had to be unique, unpredictable, and never leaked -- and that the caller, not the scheme, was responsible for generating perfectly, every single time. Surface 1 was loaded and handed over to millions of implementers.

The discrete-log camp had built its entire deployed base on a secret the caller had to generate perfectly, every single time. It took exactly one game console, one wallet app, and one SSH client to prove how badly that goes.

5. The Nonce Catastrophe: ECDSA in Full#

Here is the mechanism underneath the PS3 break, the drained Bitcoin wallets, and the 2024 PuTTY disclosure. And here is the precision almost every retelling gets wrong.

ECDSA, mechanically#

Key generation is a private scalar $d$ and its public point $Q = [d]G$, where $G$ generates a group of prime order $n$. To sign a message $m$, ECDSA draws a nonce $k$, forms $R = [k]G$, sets $r = x(R) \bmod n$, and computes

$s = k^{-1}\bigl(H(m) + r\,d\bigr) \bmod n.$

Verification recovers $u_1 = H(m)\,s^{-1}$ and $u_2 = r\,s^{-1}$ and accepts exactly when $x\bigl([u_1]G + [u_2]Q\bigr) \bmod n = r$ ^[7]. Throughout, $H(m)$ is the hash truncated to the leftmost $\text{bitlen}(n)$ bits, not the full digest -- which matters whenever the hash is wider than the order $n$, as with the P-521 curve behind the PuTTY story below. Stare at the signing equation and the danger is obvious.

The nonce $k$ is the load-bearing secret, and $s$ mixes $k$, the message hash, and the private key $d$ into one linear relation. Anything you learn about $k$ becomes a linear equation in $d$.

The repeat case: certain from two signatures#

Sign two different messages with the same nonce and the two signatures share the same $r$ (because $r$ depends only on $k$). Subtract the two signing equations and $k$ cancels, leaving a single linear equation you can solve directly for the private key:

$d = \frac{s_2\,H(m_1) - s_1\,H(m_2)}{r\,(s_1 - s_2)} \bmod n.$

This is not statistical. It is exact, from two signatures. It is the PlayStation 3: Sony used a constant $k$, so every firmware signature shared an $r$, and two of them were enough ^[1]. And it is the 2013 Android Bitcoin thefts: a flaw in the Java SecureRandom implementation caused the nonce to repeat across signatures generated on affected devices, and real coins drained from wallets whose signing keys were exposed by the collision ^[19], ^[20].

The recovery really is grade-school algebra. The demonstration below signs two messages under a reused nonce on toy-sized parameters, then plays the attacker: given only the public signature values, it recovers the nonce and then the private key.

// Illustrative toy sizes, NOT secure. Here r stands in for x([k]G) mod n;
// a real attacker reads r straight off the two signatures.
const n = 1000003n;                       // small prime "group order"
const mod = (a, m) => ((a % m) + m) % m;
function inv(a, m) {                       // modular inverse, extended Euclid
let [or, r] = [mod(a, m), m], [os, s] = [1n, 0n];
while (r !== 0n) { const q = or / r; [or, r] = [r, or - q * r]; [os, s] = [s, os - q * s]; }
return mod(os, m);
}
// Signer's secrets (the attacker never sees these):
const d = 123456n;                        // private key
const k = 654321n;                        // per-signature nonce -- REUSED: the whole bug
const r = 42n;                            // r = x([k]G) mod n; same k gives the same r
const h1 = 111111n, h2 = 222222n;         // two message hashes
// ECDSA signing: s = k^{-1} (h + r*d) mod n
const s1 = mod(inv(k, n) * mod(h1 + r * d, n), n);
const s2 = mod(inv(k, n) * mod(h2 + r * d, n), n);
// Attacker sees only (r, s1, s2, h1, h2). Recover k, then d:
const kRec = mod(mod(h1 - h2, n) * inv(mod(s1 - s2, n), n), n);
const dRec = mod(mod(s1 * kRec - h1, n) * inv(r, n), n);
console.log('recovered nonce k = ' + kRec + '  (true ' + k + ')');
console.log('recovered key   d = ' + dRec + '  (true ' + d + ')');
console.log(dRec === d ? 'PRIVATE KEY RECOVERED from two signatures' : 'mismatch');

Two subtractions and two inversions. No discrete logarithm was harmed.

The bias case: statistical, and it needs many#

Now change the failure. Instead of repeating the nonce, suppose the nonce generator is subtly biased -- say the top few bits are always zero. No two signatures share an $r$, so the two-subtraction trick does not apply, and no single signature hands you the key.

What you have instead is a stream of signatures that each leak a little information about a secret, which is precisely the Hidden Number Problem: recover a hidden value from many samples that each reveal a few high-order bits. Reformulate the biased signatures as an HNP instance, run lattice reduction, and the private key falls out -- but only after you collect many signatures.

The canonical modern proof is PuTTY. In April 2024, CVE-2024-31497 disclosed that PuTTY's ECDSA nonce generator for the NIST P-521 curve was biased so that the first 9 bits of each nonce are zero, enabling full secret key recovery in roughly 60 signatures ^[2]. Sixty. Not two.

The rigor behind that number is a quarter-century of work: Boneh and Venkatesan introduced the Hidden Number Problem in 1996 ^[22]; Howgrave-Graham and Smart turned it into the first practical lattice recovery of DSA keys from partial nonces in 2001 ^[23]; Nguyen and Shparlinski made ECDSA key recovery from a few leaked nonce bits rigorous in 2003 ^[24]; and by 2020, LadderLeak recovered keys with under one bit of nonce leakage per signature ^[25].

The precision that almost every retelling gets wrong#

A repeated nonce leaks the private key with certainty from just two signatures. A few-bit-biased nonce is different: a statistical lattice attack that needs many signatures, not one. Conflating repeat with bias is the single most corrected misconception in this corner of cryptography.

Two root causes hide under the word "bias"#

There is a second fork that decides which cure you need. A generation failure -- a bad RNG that repeats or biases the nonce -- is cured by not depending on the RNG at all, which is the deterministic signing of the next section. But a usage failure is different: even a perfectly generated nonce leaks if the code that consumes it, the scalar multiplication $[k]G$, runs in time or draws power that depends on the nonce's bit-length. That is a side channel, and no amount of clever nonce generation closes it.

In 2019, both Minerva and TPM-Fail recovered ECDSA keys from exactly this timing leak, then finished the job with the same lattice machinery as the bias case ^[26], ^[27]. The cure there is constant-time scalar multiplication.

flowchart TD
K["The per-signature nonce k"] --> G["Generation failure: how k is produced"]
K --> U["Usage failure: how k is consumed"]
G --> R["Repeat: same k twice, key from two signatures"]
G --> B["Bias: predictable bits, key from many signatures"]
U --> T["Timing or EM leak of k during scalar multiplication"]
R --> C1["Cure: deterministic nonce, RFC 6979"]
B --> C1
T --> C2["Cure: constant-time scalar multiplication"]

So the random-number generator was the enemy in three of these four stories. The obvious fix is a better RNG. The actual fix, the one the whole field converged on, was to use no randomness at all.

6. The Fix for a Randomness Disaster Was Less Randomness#

The counterintuitive move: if a bad random nonce is what kills you, stop rolling the dice. Derive the nonce deterministically from the one thing that is already secret and the one thing that is already unique.

RFC 6979, the retrofit#

Thomas Pornin's RFC 6979 does exactly that. It derives the nonce as a deterministic function of the private key and the message hash, driving an HMAC-based deterministic random bit generator so that signing consumes no runtime entropy. A broken system RNG can no longer cause a repeat or a generation bias, because there is no RNG in the signing path ^[28].

The elegance is that nothing downstream changes: a deterministic signature verifies under the same verifier as a randomized one, so this is a drop-in with zero protocol change. The RFC states the goal plainly -- signers "do not need access to a source of high-quality randomness" -- and warns that even slight biases in nonce generation may be turned into attacks, exactly the HNP lineage from the previous section ^[28].

But determinism is not unconditionally safer#

Determinism trades one threat model for another. A fully deterministic signer is a fixed, replayable target. Feed it the same key and message twice and it does exactly the same computation, which is the ideal setup for a differential fault attack: run the signer twice, glitch one of the two runs with a voltage or clock disturbance, and diff the correct output against the faulted one to recover the key.

Poddebniak and colleagues demonstrated this against deterministic signature schemes in 2018 ^[29]. NIST took the point: FIPS 186-5 approves deterministic ECDSA yet explicitly flags deterministic schemes as being of particular concern for fault attacks ^[30].

The resolution: hedged signing#

Hedged signing mixes a little fresh randomness back in on top of the deterministic derivation. RFC 6979's own section on variants sanctions adding extra input to the nonce derivation, noting that the result is then no longer deterministic (EC)DSA ^[28]. The payoff is that a hedged signer survives both failure modes: if the RNG dies, the deterministic core still produces a safe, distinct nonce; if the RNG works, the fresh entropy makes each signing unrepeatable and defeats the differential fault attack.

This is where modern libraries land by default. Go's crypto/ecdsa hedges: its documentation says signatures "are not deterministic, but entropy is mixed with the private key and the message," and that "if rand is nil, Sign will produce a deterministic signature according to RFC 6979" ^[31]. BoringSSL mixes in additional entropy the same way ^[32], and the security analysis of hedged Fiat-Shamir signatures under faults gives this posture a formal footing ^[33].

One caution: it fixes only the generation surface. The usage leak from the previous section -- the timing side channel during scalar multiplication -- is untouched by how you derive the nonce, and its cure remains constant-time code. Three cures, three distinct threats.

RFC 6979 pulled surface 1 back inside the scheme, but only surface 1, and only as a patch bolted onto a design that still leaks the other two. A cleaner scheme would make deterministic nonces, a fixed encoding, and a byte-exact verifier all native. That scheme already existed. It had been waiting on a patent to expire for two decades.

7. The Breakthrough: Schnorr Done Right#

Everything RFC 6979 retrofitted, one scheme had baked in from birth. It was invented in 1989 and could not be deployed until 2008, because it was patented.

Why Schnorr is clean#

Recall Schnorr's response, $s = k + ex$. That single linear equation is what makes the scheme provable, batchable, and aggregatable. Provable, because the linear structure is what the Pointcheval-Stern forking lemma needs to reduce forgery to the discrete-log problem in the random-oracle model ^[34]. Batchable, because a linear verification equation lets you check many signatures as one combined equation, the subject of a later section. Aggregatable, because linear things add, which is why threshold and multi-signature schemes like FROST and MuSig2 build directly on Schnorr.

The Fiat-Shamir transform is still the engine turning the underlying identification protocol into a signature; Schnorr is simply the cleanest identification protocol to feed it.

EdDSA and Ed25519 pull all three surfaces inside#

In 2011, Bernstein, Duif, Lange, Schwabe, and Yang published EdDSA, and its edwards25519 instantiation, Ed25519, is the scheme that pulls all three surfaces inside the definition by design ^[35].

Surface 1, the nonce, is native and deterministic. Ed25519 computes the nonce as $r = H(\text{prefix} \mathbin{\|} M) \bmod L$, hashing a secret key-derived prefix together with the message. There is no runtime RNG in the signing path, so the entire PS3 and Android failure class is structurally impossible rather than merely discouraged. The designers said so directly, and named the incident:

Signatures are generated deterministically ... directly relevant to the recent collapse of the Sony PlayStation 3 security system.

Surface 2, the encoding, is fixed. An Ed25519 signature is a fixed 64-byte string, a point encoding followed by a scalar, and RFC 8032 mandates a strict range check that the scalar satisfy $0 \le S < L$ on decode. Enforcing that check makes a strict Ed25519 implementation strongly unforgeable, closing the malleability surface at the encoding level ^[36].

Surface 3, the arithmetic, is safe by construction. edwards25519 uses a complete twisted-Edwards addition law with no exceptional cases, so the constant-time implementation is the natural one, and there are no special points where a naive verifier misbehaves ^[35]. Determinism here is structural, not a patch bolted on afterward, which is the real reason "why determinism helps" is a property of the design rather than a library option.

flowchart TD
M[Message] --> SCH
SK[Private key] --> SCH
subgraph SCH["Inside EdDSA and BIP-340"]
N["Surface 1: deterministic key-prefixed nonce"]
F["Surface 2: fixed canonical encoding"]
V["Surface 3: byte-exact verifier"]
end
SCH --> SIG["One valid signature, no caller choices"]
SIG --> OK{"Accept or reject, deterministically"}

BIP-340: Schnorr over secp256k1, with the verifier pulled inside#

Bitcoin needed Schnorr on its own curve, secp256k1, and in 2020 BIP-340 delivered it: 64-byte signatures, 32-byte x-only public keys, and, most importantly for surface 3, a verifier specified down to the byte. The specification states that the verification algorithm is "completely specified ... at the byte level," the guarantee whose full payoff we reach when we return to verifier strictness later ^[3].

BIP-340 also adopts the hedged idea natively: it derives a synthetic nonce and notes that the added randomness is only supplemental to security, so a faulty RNG cannot break it. Bitcoin's Taproot upgrade deployed it in November 2021 ^[37].

Now the punchline. The scheme that makes deterministic nonces, a fixed encoding, and a byte-exact verifier native is Schnorr, invented in 1989. It could not be deployed until its patent expired in 2008, which is exactly why the worse-behaved ECDSA shipped to the entire internet two decades before its clean successor. Ed25519 arrived in 2011, BIP-340 in 2020. The best-behaved design was first on paper and last in production.

One honest caveat keeps this from being a silver bullet. Plain Ed25519 has no hedging knob: it is purely deterministic, so on hardware where an attacker can inject faults it is the harder-hit fault target, and hardened embedded implementations re-inject randomness exactly as the hedged-signing analysis recommends ^[29], ^[33]. This is coexistence, not a coronation. Ed25519 and BIP-340 close all three surfaces on the discrete-log track. But the other 1976 track, RSA, had its own reckoning with the form of a signature, and its answer came with something the discrete-log schemes still lack: a tight proof.

8. RSA-PSS: Probabilistic Signing with a Tight Proof#

On the discrete-log track, determinism was the virtue. On the RSA track, the opposite move -- adding randomness -- bought the best security proof any deployed signature has.

PSS, mechanically#

Never sign the bare message. The EMSA-PSS encoding hashes the message, mixes in a fresh random salt, and builds a full-width encoded message before the RSA private-key operation. Concretely, it forms $H = \mathrm{Hash}(\text{padding} \mathbin{\|} \mathrm{Hash}(M) \mathbin{\|} \text{salt})$, masks the salt-bearing data block against a mask generated from $H$, and assembles the encoded message as maskedDB followed by $H$ followed by the trailer byte 0xbc. The signature is that encoded message raised to the private exponent modulo $n$ ^[15], ^[16]. Verification recomputes the whole structure and checks it exactly, rejecting anything that does not fit the padding shape.

flowchart LR
M[Message] --> MH["mHash = Hash of M"]
SALT["Random salt"] --> H2["H = Hash of padding, mHash, salt"]
MH --> H2
H2 --> DB["maskedDB = data block xor mask from H"]
DB --> EM["EM = maskedDB then H then 0xbc"]
H2 --> EM
EM --> SIG["Signature = EM to the d mod n"]

Why probabilistic buys a tight proof#

Bellare and Rogaway proved PSS existentially unforgeable with a tight reduction to the RSA problem in the random-oracle model: a forger against PSS can be turned into an algorithm that inverts RSA with essentially the same success probability and running time ^[16].

That word tight is the whole prize. A tight reduction loses almost nothing between the scheme's security and the underlying hard problem, so a concrete key size gives you concrete confidence; a loose reduction loses a large factor, so you either accept a weaker guarantee or inflate parameters to compensate. By contrast, PKCS#1 v1.5's signature padding has only a heuristic argument, not a tight proof. Among deployed signatures, PSS's guarantee is the gold standard, and it sets up the proof-quality spectrum we return to in the limits section.

The deployment reality, stated exactly#

"Is RSA-PSS widely deployed?" has a split answer, and blurring the split is a common error. TLS 1.3 makes RSA-PSS mandatory to implement for the online handshake signature: the CertificateVerify message uses the rsa_pss_rsae_* schemes, and a compliant implementation must support them ^[38]. That is a specification requirement.

Separately, as a matter of deployment, most Web-PKI certificates -- the long-lived signatures a certificate authority puts on the certs in the chain -- are still PKCS#1 v1.5. So the handshake signature your browser makes live and the certificate-chain signatures it validates are different signatures with different padding, and the honest answer separates them.

The cost profile that decides where PSS fits#

RSA's economics are lopsided and they determine where it belongs. Verification uses a tiny public exponent, usually 65537, so it is very fast. Signing uses the full-width private exponent, so it is slow, and the signatures are large: 256 bytes at RSA-2048, 384 bytes at RSA-3072, an order of magnitude bigger than a 64-byte elliptic-curve signature. That makes RSA-PSS excellent where you verify far more often than you sign, such as certificates and firmware images, and painful where you sign constantly. We put real numbers on this in the state-of-the-art section.

PSS pinned RSA's form with a proof. But the discrete-log schemes still had an unresolved question about form, one that let anyone alter a signature without the key and briefly threatened to break Bitcoin.

9. Malleability, Canonicalization, and Strong Unforgeability#

Recall the promise EUF-CMA does not make: that there is only one valid signature per message. For ECDSA there are always at least two, and the caller was left to notice.

Surface 2: ECDSA malleability, mechanically#

Take any valid ECDSA signature (r, s). Now negate the scalar: (r, n - s) also verifies, and it is a different signature on the same message, producible by anyone with no private key at all. The reason is visible in the verification equation. Replacing $s$ with $n - s$ is replacing it with $-s \bmod n$, which flips the signs of both $u_1$ and $u_2$, negating the recovered point to $-R$. On these curves a point and its negation share an $x$-coordinate, so $x(-R) \bmod n = x(R) \bmod n = r$, and the check still passes.

BIP-340 states the fact plainly: "If (r,s) is a valid ECDSA signature then (r,n-s) is also valid" ^[3]. So standard ECDSA meets EUF-CMA but not SUF-CMA -- exactly why that one-word distinction was worth planting seven sections ago.

The protocol fallout: Bitcoin transaction malleability#

Malleability is harmless until a protocol treats the signature as an identifier. Bitcoin did. A transaction id is a hash computed over the whole transaction including its signatures, so flipping s to n - s changes the txid without changing what the transaction does. Anything that referenced an unconfirmed transaction by its id -- a chain of dependent spends, a naive payment tracker -- could be broken by a third party rewriting the signature in flight ^[39].

The fix: low-s canonicalization restores SUF-CMA#

If two signatures differ only by $s$ versus $n - s$, pick one. The low-s rule requires $s \le n/2$, so exactly one of the twins is standard and the other is rejected on sight. Bitcoin moved this from proposal to policy across BIP-62 and BIP-146, and it restores strong unforgeability in the system that needed it most ^[40], ^[41]. Ed25519's analogue is the strict S < L range check that RFC 8032 mandates on decode, which is what makes a strict Ed25519 implementation SUF-CMA ^[36].

Surface 3: the verifier, which closed last and most embarrassingly#

The third surface failed in two distinct shapes. The first is a permissive verifier. In 2022, Java's ECDSA verification accepted the all-zero signature (r, s) = (0, 0) for any message and any key, because it skipped the range check that forbids zero. "Psychic Signatures," CVE-2022-21449, scored CVSS 7.5 and forged anything built on Java's signatures: TLS, signed JWTs, SAML assertions, OIDC id tokens, and WebAuthn responses ^[4], ^[5].

The second shape is more subtle: honest disagreement. "Taming the Many EdDSAs" showed that verifiers all conforming to RFC 8032 nonetheless split on adversarial inputs -- cofactored versus cofactorless verification equations, non-canonical point encodings, small-order points -- so the same signature could be valid to one library and invalid to another ^[42]. For a consensus system that is a disaster, and ZIP-215 answers it by pinning a byte-exact validation profile on which single and batch verification always agree ^[43].

BIP-340 treats this surface as an engineering requirement rather than an afterthought, which is why its verifier is specified to the byte:

The verification algorithm must be completely specified at the byte level. This guarantees that nobody can construct a signature that is valid to some verifiers but not all.

The evidence, in one table#

Every named break in this article splits cleanly across the three surfaces. Read the "Surface" column and the thesis stops being a slogan and becomes a body count.

Notice what is missing from the root-cause column: not once did anyone solve an elliptic-curve discrete logarithm or factor a modulus. That is Aha 1, complete. Fix the nonce, fix the form, fix the verifier, and you have a signature you can trust one at a time. But the modern world verifies millions at once, and the obvious way to batch them is quietly forgeable.

10. Batch Verification, and the One Condition That Makes It Safe#

Schnorr's linearity offers a tempting shortcut: instead of checking a thousand signatures one by one, check their sum once. Done naively, that shortcut lets an attacker slip forgeries past you.

The technique#

Because Schnorr, EdDSA, and BIP-340 verification is a single linear equation, a batch of $u$ signatures can be checked as one random linear combination of those equations. That collapses $u$ separate double-scalar multiplications into a single large multi-scalar multiplication, whose cost is sublinear in the number of distinct bases, which is where the throughput win comes from. The original Ed25519 paper reports a batch of 64 signatures verifying at under 134,000 cycles per signature, against 273,364 cycles for a single verification, roughly a twofold speedup ^[35].

The non-negotiable safety condition#

The coefficients must be randomized. Here is why the naive all-ones sum fails. A signature verifies exactly when its verification residual is zero. If you add the residuals with equal weight, an attacker can submit two invalid signatures whose residuals are equal and opposite, so they cancel in the sum: the batch equation holds even though neither signature is valid.

Weight each residual by an independent random coefficient and the errors no longer cancel except with negligible probability. BIP-340 derives its batch coefficients from a CSPRNG seeded over all of the inputs, so an attacker cannot predict the weights and engineer a set of residuals that sums to zero without each signature being individually valid ^[3].

// Illustrative model. A signature is VALID iff its verification residual is 0.
const n = 1000003n;
const mod = (a, m) => ((a % m) + m) % m;
// Attacker forges two invalid signatures whose residuals are equal and opposite.
const D = 777n;                 // the cancelling error the attacker chooses
const e1 = mod(D, n);           // residual of forged signature 1 (nonzero: invalid)
const e2 = mod(-D, n);          // residual of forged signature 2 (nonzero: invalid)
console.log('signature 1 valid on its own? ' + (e1 === 0n));   // false
console.log('signature 2 valid on its own? ' + (e2 === 0n));   // false
// Naive all-ones batch: accept iff the plain sum of residuals is 0
const allOnes = mod(e1 + e2, n);
console.log('all-ones batch residual = ' + allOnes + (allOnes === 0n ? '  -> ACCEPTED, forgery slips through' : '  -> rejected'));
// Randomized batch: weight each residual by a per-input random coefficient
const a1 = 31337n, a2 = 424242n;   // seeded by a CSPRNG over ALL inputs
const rand = mod(a1 * e1 + a2 * e2, n);
console.log('randomized batch residual = ' + rand + (rand === 0n ? '  -> accepted' : '  -> REJECTED, forgery caught'));

flowchart TD
IN["u signatures to verify"] --> SEED["Seed a CSPRNG over all u inputs"]
SEED --> COEF["Random coefficients a1 through au"]
COEF --> MSM["One multi-scalar multiplication"]
MSM --> OK{"Batch equation holds?"}
OK -->|yes| ACC["Accept all"]
OK -->|no| FALL["Fall back to individual verification"]
IN --> BAD["Naive all-ones coefficients"]
BAD --> CANCEL["Attacker makes two residuals cancel"]
CANCEL --> FORGE["Invalid batch accepted, a forgery"]

What batching does not give you, and where it is not used#

A failed batch tells you only that some signature in it is bad, not which one, so you must fall back to individual verification to find the culprit -- a real cost when batches are large. Batching is also a Schnorr-family privilege: BIP-340 notes that standardized ECDSA "cannot be verified more efficiently in batch," so the ECDSA deployments that dominate the web get no speedup here ^[3]. And adoption is narrower than the technique's fame suggests.

That is the deployed toolkit: ECDSA, Ed25519, BIP-340 Schnorr, and RSA-PSS, each with its surfaces pulled in to a different degree. Which one should you reach for in 2026? The honest answer is not a single winner.

11. State of the Art and Competing Approaches (2024 to 2026)#

There is no single best signature scheme to crown. The state of the art is four deployed constructions, each dominant in a niche, plus a set of signposts pointing at the frontier. This is coexistence with selective supersession, not a ladder where each rung replaces the last.

The four, per niche#

Deterministic or hedged ECDSA leads by raw deployment. It is what FIPS, TLS, and the secp256k1 chains run, and modern libraries hedge it by default ^[28], ^[31]. Ed25519 is the misuse-resistant greenfield default: deterministic nonce, fixed encoding, constant-time by construction ^[36], ^[35]. BIP-340 Schnorr leads for consensus and threshold work, being byte-exact, SUF-CMA by design, and linear enough to aggregate ^[3]. RSA-PSS leads verify-heavy and interoperability-bound settings with its tight proof and cheap verification ^[15], ^[38].

Of the classical schemes, only finite-field DSA is withdrawn for new signatures by FIPS 186-5; deterministic ECDSA is approved, which is not the same as mandated ^[30].

Benchmarks, read correctly#

The reference measurements everyone quotes for Ed25519 come from the eBATS and eBACS public benchmarking effort ^[35], ^[44].

Signposts at the frontier#

Four constructions sit just outside the four-scheme core and deserve a pointer rather than a section. XEdDSA lets you sign with an X25519 Diffie-Hellman key, a specialized key-reuse trick that is deployed at scale in the Signal protocol and the applications built on it, so it is peripheral by role but anything but academic ^[45].

MuSig2 and FROST are two-round multi-signature and threshold-Schnorr protocols that produce an ordinary 64-byte signature indistinguishable from a single-signer one ^[46], ^[47]. BLS offers pairing-based aggregation and anchors Ethereum consensus; a companion part in this series on hashing to curves covers it.

And the horizon is post-quantum: NIST finalized ML-DSA in FIPS 204 and SLH-DSA in FIPS 205 in August 2024, both with signatures ranging from kilobytes to tens of kilobytes, an order of magnitude or more larger than anything in the table above ^[48], ^[49].

Every row of those tables assumes the hardness holds. That assumption has a precise shape, and a known expiration date.

12. Theoretical Limits#

Here is what a first course skips: none of these schemes has an unconditional proof, their proofs differ enormously in quality, and every one of them dies to the same quantum algorithm.

Conditional security, three assumptions#

Every guarantee in this article is conditional. The elliptic-curve schemes rest on the hardness of the elliptic-curve discrete logarithm; RSA-PSS rests on the RSA problem, which is no harder than factoring; and all of the Fiat-Shamir schemes rest additionally on the random-oracle model, a heuristic that proves security while treating the hash function as an ideal random function that no real hash exactly is. "Provably secure" here always means "secure if these assumptions hold." That is not a weakness peculiar to signatures; it is the honest status of essentially all deployed public-key cryptography.

The tightness spectrum#

The interesting frontier is not whether the proofs exist but how much they lose. A reduction converts an attacker on the scheme into an algorithm against the hard problem, and the tightness of that conversion is how much security leaks in the translation.

RSA-PSS has a tight reduction to RSA ^[16]. Schnorr and EdDSA have only a loose, quadratic-loss reduction through the forking lemma ^[34], and Seurin proved that this loss is essentially the best any algebraic reduction can do, so it is a genuine barrier rather than a proof waiting to be improved ^[50]. Later work made the multi-user Schnorr reduction explicit, with a loss on the order of the number of hash queries ^[51]. And (EC)DSA has the weakest guarantee of all: the only known proofs must model its conversion function as an idealized, bijective random oracle ^[52].

Deployment and proof quality are inversely correlated here. The most-deployed signature in the world, ECDSA, has the least satisfying proof: it is secure because the elliptic-curve discrete logarithm is hard, not because the scheme is clean. And tight proof or loose, every scheme in this article falls to Shor's algorithm. The destination is post-quantum, not a better curve.

The one bound that is not conjectural#

There is exactly one limit in this section that is not an open question. Shor's algorithm solves both factoring and the discrete logarithm in quantum polynomial time, so a cryptographically relevant quantum computer breaks every scheme in this article at once ^[53]. No curve size and no modulus length helps, because Shor's cost is polynomial in the key size. The elliptic-curve schemes and RSA-PSS fall together.

If the theory is this settled -- conditional proofs of differing quality and a known quantum cliff -- then everything still up to you lives in the code. Here is that part, compressed into rules you can apply on Monday.

13. The Practical Guide: Decision Rules#

Every rule below is one row of the failure catalog, inverted. If you remember nothing else, remember the decision tree.

flowchart TD
START{"What constrains you?"} --> G["Greenfield, no constraint"]
START --> F["FIPS or compliance"]
START --> R["Must interoperate with RSA"]
START --> B["Bitcoin or byte-exact consensus"]
START --> T["Threshold or multisig"]
G --> GE["Ed25519 with a strict verifier"]
F --> FE["Hedged ECDSA P-256 or FIPS-approved Ed25519, enforce low-s"]
R --> RE["RSA-PSS as PS256, at least RSA-3072"]
B --> BE["BIP-340 Schnorr, or low-s strict-DER ECDSA if legacy"]
T --> TE["FROST or MuSig2, never deterministic nonces"]

Use X, with these parameters, in this case#

Greenfield, no FIPS constraint. Reach for Ed25519, verified with a strict profile that enforces the canonical S < L range and a ZIP-215-style byte-exact rule ^[36], ^[43]. You get deterministic nonces, a fixed encoding, and constant-time arithmetic for free.

FIPS-constrained. Use deterministic or hedged ECDSA on P-256 following RFC 6979 and its hedged variant, or FIPS 186-5-approved Ed25519. Enforce low-s, and insist on a constant-time library so you do not reopen the Minerva timing surface ^[28], ^[30].

RSA interoperability for a new design. Use RSA-PSS (the PS256 scheme), never PKCS#1 v1.5 for new work. Set the salt length equal to the hash length, use a matching MGF hash, and choose at least RSA-3072 for 128-bit security ^[15].

Bitcoin or byte-exact consensus. Use BIP-340 Schnorr, as deployed in Taproot. If you are stuck with legacy ECDSA, enforce low-s and strict DER encoding so transactions are not malleable ^[3], ^[41].

Threshold or multisig. Use FROST or MuSig2 over BIP-340, and never use deterministic nonces in multi-party signing -- a deterministic nonce in an interactive protocol can be replayed across differing co-signer inputs and leak the share ^[47], ^[46], ^[3].

Always. Hedge the nonce whenever the platform can face fault injection. Domain-separate your keys per scheme: BIP-340 warns that reusing one key across RFC-6979 ECDSA and BIP-340 can leak it through cross-scheme nonce coincidences ^[3]. Verify strictly, and when any part of your protocol hashes over signatures, treat SUF-CMA, not merely EUF-CMA, as the bar.

Turn each of those rules around and you get the antipatterns that keep showing up in real code review: the misuse catalog.

14. Common Misuse, and the One Sentence Underneath#

Every break in this article was a violated rule from the last section. Here they are as the antipatterns a reviewer actually finds in real code.

• A caller-supplied nonce from a weak or predictable RNG. This is the Android wallets and, in its biased form, PuTTY ^[19], ^[2].
• A nonce reused across messages or keys. This is the PS3, and it is certain from two signatures ^[1].
• Non-constant-time scalar multiplication. This is Minerva and TPM-Fail: even a perfect nonce leaks through timing ^[26], ^[27].
• Skipping the range, subgroup, or canonical-s checks. This reopens malleability, and for a permissive verifier it reopens forgery ^[3].
• Treating EUF-CMA as if it meant non-malleability. This is Bitcoin transaction-id malleability: the scheme was unforgeable and the protocol still broke ^[3].
• Naive all-ones batch coefficients. A forgeable batch, defeated by errors that cancel in the sum ^[3].
• A lax or permissive verifier. This is Psychic Signatures, which accepted the all-zero signature for any message ^[4].
• PKCS#1 v1.5 for new designs, or blurring the encryption-versus-signature split. Use RSA-PSS, and never confuse the v1.5 decryption oracle with the unbroken v1.5 signature scheme ^[15].
• Signing without domain separation. One key across two schemes can leak through cross-scheme nonce coincidences ^[3].

The one sentence underneath#

Return to that slide at 27C3. Sony's curve was pristine; two signatures gave up the master key ^[1]. Now line up the rest of the body count. Across three decades, almost no deployed break ever solved an elliptic-curve discrete logarithm or factored a modulus. Attackers reused a nonce, biased one ^[2], leaked one through timing ^[26], flipped a signature's s to n - s, or accepted the all-zero signature for any message ^[4]. The hardness assumption sat untouched through all of it.

That is why "signing done right" is not a single choice but a stack: the right scheme for the job, a nonce you do not have to trust the RNG for, a canonical form, and a byte-exact verifier -- and, the deepest lesson the evolution kept teaching, a preference for schemes where the dangerous case simply cannot be reached, which is what Ed25519 and BIP-340 buy you. Remove any one layer and a surface reopens.

The horizon does not change the shape of the problem, only its arithmetic: post-quantum signatures like ML-DSA and SLH-DSA will hand the same three surfaces to the same callers, at ten to a hundred times the signature size ^[48]. The nonce, the form, and the verifier will still be where the security lives.

A signature is only as safe as the nonce, the form, and the verifier the scheme hands you. The math held; the interface leaked.

Using a signature safely, in the end, is the discipline of never handing an attacker a value your scheme forgot to own.