Digital
Signatures

The authentication gap

Asymmetric encryption from Chapter 9 provides confidentiality. Bob decrypts a message and reads it. But nothing in the ciphertext proves Alice wrote it. Eve could have encrypted the same message with Bob's public key, and Bob would have no way to distinguish the two.

MACs from Chapter 3 solved the authentication problem for shared-key settings. If Alice and Bob share a secret key, a MAC proves the message came from someone who knows that key. But MACs have a fundamental limitation: both sides hold the same secret. Both can create and verify tags. There is no way for a third party to confirm who actually authored the message.

From MACs to signatures

Digital signatures use asymmetric keys to solve this. Only the signer can create a signature (private key), but anyone can verify it (public key). If Alice signs a contract, Bob can prove to Charlie that Alice signed it. Alice cannot deny having signed it, because only her private key could have produced that signature.

This property is called non-repudiation. It is something MACs cannot provide, because both parties hold the shared key. With MACs, Bob could have forged the tag himself. With signatures, only Alice's private key could have produced the proof.

The size problem

RSA can only operate on values smaller than $n$ (typically 256 bytes for a 2048-bit key). You cannot sign a 10 MB file directly. Even for elliptic curve schemes, the input must be a fixed-size scalar.

The solution is the hash-then-sign paradigm. Hash the message with SHA-256 to get a 32-byte digest. Sign the digest. To verify: hash the received message, then check the signature against that hash. If the signature matches, the message is authentic.

The equations

Because the hash function is collision-resistant (Chapter 2), finding a different message with the same hash is infeasible. A signature on the hash is as good as a signature on the full message.

Why it works

The signer raises the hash to the private exponent ${\color{#ef4444}d}$. The verifier raises the signature to the public exponent ${\color{#00e5a0}e}$. If the result equals the hash, the signature is valid. This works because of the same RSA identity from Chapter 9:

How ECDSA works

The signer has a private key scalar ${\color{#8b5cf6}d}$ and a public key point ${\color{#f59e0b}Q} = d \cdot G$. To sign a message:

The nonce is critical

If the per-signature nonce ${\color{#00e5a0}k}$is reused or predictable, the private key can be recovered. This is exactly what happened to Sony's PlayStation 3 ECDSA implementation in 2010: they used the same $k$ for every signature, and hackers extracted the private key from two signatures.

The math is straightforward. Given two signatures $(r, s_1)$ and $(r, s_2)$ on different messages (same $r$ because same $k$):

Once ${\color{#00e5a0}k}$ is known, recovering the private key ${\color{#8b5cf6}d}$ is just arithmetic. A single reused nonce compromises the key forever.

The Schnorr protocol

Alice has private key ${\color{#8b5cf6}x}$ and public key ${\color{#f59e0b}P} = x \cdot G$. To sign a message $m$:

Verification works because $s \cdot G = (k + e \cdot x) \cdot G = k \cdot G + e \cdot x \cdot G = R + e \cdot P$.

Why Schnorr matters

The response equation $s = k + e \cdot x$ is linear. This seemingly simple property has profound consequences. If Alice and Bob both produce Schnorr signatures on the same message, their signatures can be added together to form a single valid multi-signature. The combined signature is the same size as a single one.

This linearity makes multi-signatures, threshold signatures, and adaptor signatures possible. ECDSA does not have this property because its equation involves $k^{-1}$, which breaks linearity.

Ed25519: Schnorr on a modern curve

Ed25519 is a Schnorr signature scheme instantiated on Curve25519 (in twisted Edwards form). Its critical improvement over classical Schnorr: the nonce is derived deterministically as a hash of the private key and message, not picked randomly.

No random number generator is involved in signing. Different messages produce different nonces by construction. Nonce reuse is impossible.

Signature malleability

Given a valid ECDSA signature $(r, s)$, the pair $(r, n - s)$ is also a valid signature on the same message. This does not break authentication, but it can break systems that use the signature as a unique identifier.

Bitcoin experienced this firsthand. Before the SegWit upgrade, transaction IDs were computed from the full transaction including the signature. An attacker could take a valid transaction, replace $s$ with $n - s$, and create a different transaction ID for the same payment. This “transaction malleability” caused real losses.

Where signatures appear

The story so far

Digital signatures solve the authentication problem. The private key creates a proof that anyone with the public key can verify, but nobody can forge. Unlike MACs, signatures provide non-repudiation.

Hash-then-sign makes signatures practical. Hash the message to a fixed-size digest, sign the digest. The collision resistance of the hash function guarantees this is as secure as signing the full message.

RSA signatures were the first practical scheme. Sign with private exponent $d$, verify with public exponent $e$. PSS padding provides the strongest security guarantees.

ECDSA provides equivalent security with much smaller signatures (64 bytes vs 256 bytes for RSA-2048). It powers most TLS certificates and blockchain transactions. But it requires a fresh random nonce per signature, and nonce reuse is catastrophic.

Schnorr signatures are the simplest discrete-log scheme. Their linear structure enables multi-signatures. Ed25519 is Schnorr on Curve25519, with deterministic nonces that eliminate the most dangerous implementation pitfall. Faster, simpler, and harder to misuse than ECDSA. The recommended choice for new systems.