How a signature is made.

The previous articles introduced the parts: a hash function that condenses the document, and a hard mathematical problem, factoring or the discrete logarithm, that separates the private key from the public one. This article puts them together. It walks, equation by equation, through the three signature schemes that dominate practice (RSA PSS, ECDSA and EdDSA) and pauses where they tend to fail, which is almost never in the mathematics.

The common skeleton

1. Hash. H(m) is computed over the exact bytes to be signed. From this point on, the document exists only through its hash.
2. Transform with the private key. Each scheme turns the hash into a signature through an operation that only the holder of the private key can perform.
3. Distribute. The document travels with the signature and, usually, with the certificate that binds the public key to an identity.
4. Verify. The recipient recomputes the hash and checks, with the public key, that the signature matches that hash. A single differing bit in the document or in the signature makes the check fail.

In RSA, as shown in the article devoted to that algorithm, the transformation is direct: the hash, with PSS padding, is raised to the private exponent. Discrete logarithm signatures work differently, and they are worth examining in detail.

ECDSA, equation by equation

ECDSA has a long lineage. Taher ElGamal proposed the first signature based on the discrete logarithm in 1985. Claus Schnorr published a simpler and more elegant variant in 1989, but patented it. NIST, looking for an unencumbered scheme, adopted a variant of ElGamal in 1991, DSA, standardized in FIPS 186 in 1994. Scott Vanstone proposed carrying it over to elliptic curves in 1992, and ECDSA was standardized by the end of that decade. Today it is specified in FIPS 186 5 and SEC 1.

The parameters are a curve, a generator point G of prime order n, the private key d and the public key Q = d · G. Let z be the hash of the message, taken as a number and truncated to the size of n.

Why does it work? Because, if everything is legitimate, u₁ · G + u₂ · Q = w(z + r · d) · G, and w(z + r · d) = k by the way s was built. The verifier reconstructs the point R without knowing either k or d. With the 19 point toy curve from the previous article you can follow it by hand: with d = 7, k = 10 and z = 3, you get r = 7 and s = 9; the verifier computes u₁ = 13, u₂ = 5 and obtains 13 · G + 5 · Q = 48 · G = 10 · G, whose x coordinate is 7. It matches.

The next lab does the same with real numbers: it generates a key pair on P 256 in your browser, using the platform’s built in cryptography, and signs and verifies whatever text you type.

The nonce: a tiny piece carrying all the risk

In ECDSA, the number k is as secret as the private key. If it leaks, the equation for s has a single unknown, d, and it can be solved. But the most famous mistake is not leaking it; it is reusing it. If two different messages are signed with the same k, the two signatures share r, and a subtraction is all it takes:

This is no academic curiosity. In 2010 it was shown that a widely sold video game console signed its software with a constant k, and its master key was exposed. In 2013, a flaw in the random number generator of a mobile platform caused cryptocurrency wallets to reuse nonces, and funds were stolen. The article in this series devoted to real world failures returns to both cases.

Reuse is not even necessary. If the nonces carry a small bias, for example if their leading bits tend to be zero because the implementation leaks their length through computation time, a few hundred or a few thousand signatures are enough to reconstruct the key using lattice techniques. That is why RFC 6979 exists: it defines how to derive k deterministically from the private key and the message, using HMAC. The signatures are still standard ECDSA, verifiable by anyone, but they no longer depend on a good random number generator at signing time.

EdDSA: Schnorr, deterministic and complete

Schnorr’s patent expired in 2008, and in 2011 Daniel Bernstein and four coauthors published Ed25519, a Schnorr type signature on the Edwards curve equivalent to Curve25519. It was designed to eliminate ECDSA’s pitfalls at the root.

• Deterministic nonce by design. r is derived from the secret and the message. Signing the same thing twice yields the same signature; signing different messages yields independent nonces. There is no random number generator that can fail at the critical moment.
• No modular inversions. The Schnorr equation is linear, and simpler to implement in constant time.
• Complete formulas. Addition on the Edwards curve has no special cases, so the code does not branch on the data.
• Clean security reduction. Schnorr signatures have cleaner security proofs in the random oracle model than ECDSA does.

One detail matters for large documents. Pure EdDSA hashes the full message twice, once for the nonce and once for the challenge, which means reading through it twice. For cases where that is a problem there is a prehashed variant, Ed25519ph, at the price of making security also depend on the collision resistance of that prehash function, something the pure version does not need.

The three, side by side

In legally binding document signing, all three coexist. RSA dominates through legacy and because secure signature creation devices have supported it for decades; ECDSA is growing with identity documents and new certificates; EdDSA, accepted by NIST since 2023, is the natural choice for systems designed from scratch. For the verifier, what matters is that the scheme and its parameters are identified unambiguously in the signature, so that the check can be reproduced twenty years from now.

← All notes