Cryptography Foundations · Part 5 of 8·Anonymity Engineering·2026-05-02·15 min read·advanced

Digital signatures

Digital signatures from first principles: RSA-PSS, ECDSA's nonce trap, why Ed25519 is the modern default, and what verification actually proves.

A digital signature is what makes the public-key world useful for more than just key agreement. With signatures, anyone holding the public key can verify that a message was authored by the holder of the private key — and only by them. Certificate authorities, code-signing systems, package managers, software releases, Git tags, blockchain transactions, mobile-app distribution, and a long list of other systems all depend on signatures as their root of identity. The interesting parts aren't whether signatures exist — they obviously do — but the engineering details that determine whether your specific signing scheme is robust against the failure modes that have historically broken signature systems in practice. This module is the foundational pass: enough to read a TLS or X.509 spec and know what a signature is actually claiming, and to recognize when a protocol design is making an unsafe choice.

Prerequisites

Module 2.3 — Hash functions and message authentication. Signatures are nearly always over hashes; understanding the hash properties is needed.
Module 2.4 — Asymmetric crypto: RSA and the discrete-log family. Signature primitives are public-key constructions.

Learning objectives

By the end of this module you should be able to:

State the security goal of a digital signature and articulate the gap between signing, MACing, and encrypting.
Compare RSA-PSS, ECDSA, and Ed25519 at the engineering level — key sizes, signature sizes, nonce behavior, side-channel exposure.
Explain why deterministic signing (Ed25519, RFC 6979 ECDSA) is a security improvement rather than a regression.
Verify a real signature with openssl and articulate what verification proves and what it does not.
Recognize the most common signature-system failure modes — bad randomness, bytes-mismatch, missing domain separation, confused-deputy protocol bugs.

What signatures buy that MACs do not

A MAC (Module 2.3) authenticates a message under a shared secret key: anyone with the key can produce or verify the tag. A digital signature authenticates a message under a private key, and verification works with the corresponding public key. The asymmetry is the entire reason signatures matter:

Public verifiability. Anyone with the public key can verify the signature. The verifier doesn't need a shared secret with the signer. This makes signatures suitable for distributing trust at scale: a CA's signature on a certificate is verifiable by every browser without anyone having to share a key with the CA.
Origin authentication. A valid signature proves the holder of the private key produced this message (or hash). MACs prove the message came from "someone with the shared key" — which could be either party.
Non-repudiation, in a technical sense. The signer cannot plausibly claim "I didn't sign that"; their key did. The legal and organizational consequences depend on context (was the key controlled by the signer? Was it stolen?), but the cryptographic property is that without the private key, no one else could have produced this signature.

The trade-off vs MACs is performance and complexity. Signature operations involve large-number arithmetic and run in milliseconds; HMAC tags are computed in microseconds. Protocols use signatures sparingly — for handshake authentication, for releases, for one-time identity proofs — and use MACs or AEAD for high-volume per-message authentication.

A clean conceptual split:

MACs: shared-secret, fast, every-message.
Signatures: public-key, slow, identity-and-roots-of-trust.

Signatures are over digests, transcripts, or structured messages

In practice, signature schemes don't sign the raw message; they sign a hash. Three reasons:

Performance. Signing a 32-byte hash is fast; signing a megabyte of bytes is much slower for any signature scheme.
Length-independence. Signature primitives operate on fixed-size inputs (RSA modulus size, curve point size). Hashing absorbs arbitrary length into fixed length.
Structure preservation. Signing a hash of a canonical encoding ensures the signature commits to a specific message representation. Without canonicalization, two semantically-equivalent messages might have different bytes and thus different hashes.

This makes the hash function choice consequential. If the hash has weak collision resistance, an attacker can find two distinct messages with the same hash, get a signature on one, and present it as a signature on the other. This is exactly the SHA-1-deprecation story: SHA-1 collisions made signatures over SHA-1 hashes unsafe for messages an attacker could choose.

For modern signatures, the hash is typically:

SHA-256 for ECDSA over P-256 and RSA-PSS at 2048-bit security.
SHA-384 for ECDSA over P-384 and RSA-PSS at 3072-bit security.
SHA-512 internally for Ed25519 (the spec includes the hash as part of the algorithm).

Outside of standard hashing, canonicalization matters. Two engineers who agree to "sign this JSON object" can produce different signatures if their JSON serialization differs in whitespace, key ordering, or number representation. Either both sides commit to a canonical form, or the signature is over a hash of a content-addressed binary blob that doesn't have multiple valid encodings. Protocols like X.509, JWT, and CBOR have explicit canonical encoding rules; ad-hoc protocols often don't, leading to signature-confusion bugs.

RSA signatures and PSS

RSA-the-primitive can sign and encrypt because both operations use the same modular exponentiation. To sign:

signature = hash(m)^d mod n        (with proper padding)

To verify:

hash(m) == signature^e mod n       (verify the recovered hash matches)

Two padding schemes for RSA signatures:

PKCS#1 v1.5 signatures. A 1990s padding format: 0x00 0x01 0xff...0xff 0x00 || hash_oid || hash. The hash is wrapped in a deterministic structure that's easy to verify and easy to construct. Still used widely in legacy systems (X.509 certificates, lots of TLS deployments), but the security proofs are weaker than the alternative. The main historical attack — Bleichenbacher's "signature forgery from variable hash bits" — has been mitigated in implementations, but the design is considered legacy.

RSA-PSS (Probabilistic Signature Scheme). The modern padding for RSA signatures. Adds randomness via a salt and a mask-generation function (MGF1, typically built on the same hash). The padding is provably secure under standard RSA assumptions, where PKCS#1 v1.5 is not. RSA-PSS is what TLS 1.3 mandates; PKCS#1 v1.5 signatures are still accepted for backward compatibility but discouraged.

The key takeaway: for new RSA signature deployments, use RSA-PSS. For verification, accept both PKCS#1 v1.5 and PSS to handle existing certificate ecosystems.

ECDSA and the nonce problem

ECDSA (Elliptic Curve Digital Signature Algorithm) is the elliptic-curve analogue of DSA. The signing operation:

Compute e = hash(message).
Pick a random per-signature value k (the "nonce").
Compute R = k * G (curve point); let r = R.x mod n.
Compute s = k^-1 (e + r * d) mod n, where d is the private key and n is the curve order.
Output the signature (r, s).

The crucial detail: the per-signature nonce k must be unique and unpredictable. Reusing k across two signatures with the same private key is catastrophic — the attacker can solve for d algebraically:

s1 = k^-1 (e1 + r * d) mod n
s2 = k^-1 (e2 + r * d) mod n      (same k, same r, different e)

Subtracting and rearranging:

k = (e1 - e2) / (s1 - s2) mod n
d = ((s1 * k) - e1) / r mod n

The attacker recovers the private key directly. The 2010 PlayStation 3 hack famously exploited exactly this — Sony's signing implementation used a constant k for ECDSA, and once anyone noticed, the PS3's master signing key was recoverable.

Even partial nonce predictability can leak keys via lattice attacks. A bias of just a few bits in k over many signatures can be enough.

The fix: deterministic ECDSA (RFC 6979) replaces the random k with a deterministic value derived from the message and the private key via HMAC. The signing process is reproducible — sign the same message twice and you get the same signature — but each message produces a different k, eliminating the nonce-reuse and bias-attack vectors.

Modern ECDSA implementations should use RFC 6979. Most major libraries (OpenSSL since 1.1, libsodium, BoringSSL) do by default. Implementations that don't are subtle latent bugs.

Ed25519 and the modern signature instinct

Ed25519 is the signature scheme designed by Daniel J. Bernstein et al. on the Edwards form of Curve25519. Published 2011, standardized in RFC 8032 in 2017, now ubiquitous in modern systems.

Engineering virtues:

Deterministic by construction. The "nonce" r is derived as hash(secret || message). No randomness needed at signing time. Reproducible signatures, no entropy-failure attacks.
Constant-time-friendly. The Edwards curve form admits efficient constant-time arithmetic. Side-channel attacks are easier to defend against.
Compact. 32-byte private keys, 32-byte public keys, 64-byte signatures. A signature plus a public key fits in 96 bytes; an entire keypair fits on one line.
Fast. A modern CPU can do tens of thousands of Ed25519 signatures per second per core, and verifications are even faster.
Simple specification. RFC 8032 is one of the shortest signature standards. Implementations are easier to audit.
No nonce vulnerability class. Determinism removes the entire ECDSA-style nonce-leak attack space.

Trade-offs:

Less standardized in compliance regimes. NIST took until 2019 to add Ed25519/Ed448 to FIPS 186-5. Some compliance contexts still mandate ECDSA over P-256/P-384 and don't accept Ed25519.
Hardware acceleration is less common than for ECDSA. Modern CPUs do EdDSA fast in software but lack dedicated instructions like AES-NI; this matters for embedded/HSM contexts.

The pragmatic 2026 choice: for new protocols and applications, use Ed25519 unless interop or compliance forces otherwise.

There's also Ed448 — the same construction over Curve448, providing higher security margin (224-bit security versus Ed25519's 128-bit). Used in TLS for post-quantum-leaning deployments, but rare in practice.

Signature verification in protocols

Signatures show up in many distinct protocol roles:

Server-certificate signatures. A CA signs the server's public key plus identity attributes; the resulting X.509 certificate proves the binding. Browsers verify the chain to a root in their trust store. This is what the lock icon in your browser ultimately rests on.

TLS handshake signatures. TLS 1.3's CertificateVerify message is a signature over the handshake transcript (Module 1.11). The signer proves possession of the certificate's private key, which the certificate's CA-issued binding to a hostname makes useful.

Software releases. GPG signatures on tarballs, npm package signatures, container image signatures (cosign, Sigstore). The chain of trust is "we trust this signing key, this signing key was used on this artifact, the signature verifies."

Git tags and commits. GPG-signed commits and tags. Signature-verifying CI ensures only signed commits make it into protected branches. Many recent installations now use Sigstore's keyless signing tied to OIDC identity instead of long-lived GPG keys.

Configuration management. Signed configs, signed firmware, signed boot images. The chain at boot time — Secure Boot → bootloader signature → kernel signature → initramfs signature — depends on all-the-way-down signature verification.

WireGuard tooling. WireGuard configs use Ed25519 keypairs. The signing/verification model is implicit in the protocol; routes only complete handshakes with peers whose public keys are pre-listed.

The unifying observation: a signature is meaningful only against a specific set of bytes interpreted in a specific context. The signature on a TLS transcript proves the server holds a certificate's key; it says nothing about the contents of HTTP responses. The signature on a software release proves the release matches a committed-to set of bytes; it says nothing about whether those bytes are bug-free. Signature scope is everything, and confusing different scopes is how systems get exploited.

Failure modes

A whirlwind tour of how signature systems break in real deployments:

Bad randomness. ECDSA without RFC 6979 can leak keys when k is poorly generated. Famously, the Debian OpenSSL bug of 2008 reduced the entropy pool's randomness in a way that produced reproducible k values across signatures. Years of compromised keys followed.

Signing the wrong bytes. A protocol that signs hash(message) instead of hash(canonical_encoding(message)) is vulnerable when two parties disagree about the canonical form. The signature is valid for whatever bytes were hashed, but those bytes may not be what the other party verified. This is how some JWT verification bugs and assorted protocol-confusion attacks have worked.

Missing domain separation. A signing key used for two purposes — say, signing TLS transcripts and signing software releases — can be tricked: if an attacker can get a signature on bytes from one domain that look like the other domain's hash input, they cross-domain-forge. The fix is a domain prefix: hash("transcript:" + transcript) is unambiguous; hash(transcript) may not be.

Confused deputy. A verifier checks a signature without verifying the claimed subject of the signature. Example: "this signature is valid" without checking "for the message I expected." Signed but not over your bytes is a confused-deputy bug.

Revocation. A signing key is compromised; the verifier doesn't know. Revocation lists (CRLs, OCSP) and short-lived certificates address this, with various deployment frictions.

Algorithm downgrade. A protocol that lets the verifier accept SHA-1 signatures because the standard says it's optional opens itself to SHA-1 collision attacks if attackers can inject crafted messages. TLS 1.3 limits accepted signature algorithms to a curated list specifically to prevent downgrade.

The clean engineering principle: use modern primitives (Ed25519, RSA-PSS), use determinism wherever you can (Ed25519, RFC 6979 ECDSA), domain-separate signed inputs explicitly, sign canonical encodings, and treat the verifier's algorithm-acceptance list as a security parameter not a default.

Hands-on exercise

Exercise 1 — Generate and verify an Ed25519 signature

# Generate keypair
openssl genpkey -algorithm Ed25519 -out /tmp/ed25519-priv.pem
openssl pkey -in /tmp/ed25519-priv.pem -pubout -out /tmp/ed25519-pub.pem

# Sign a file
echo "the message I want to sign" > /tmp/msg.txt
openssl pkeyutl -sign -inkey /tmp/ed25519-priv.pem \
  -rawin -in /tmp/msg.txt -out /tmp/msg.sig

# Verify (good)
openssl pkeyutl -verify -pubin -inkey /tmp/ed25519-pub.pem \
  -rawin -in /tmp/msg.txt -sigfile /tmp/msg.sig

# Tamper with the message and verify (bad)
echo "tampered" > /tmp/msg-bad.txt
openssl pkeyutl -verify -pubin -inkey /tmp/ed25519-pub.pem \
  -rawin -in /tmp/msg-bad.txt -sigfile /tmp/msg.sig

Expected output: the first verify says Signature Verified Successfully. The tampered verify says Signature Verification Failure.

Look at the file sizes: the private key file is small, the public key is small, the signature is exactly 64 bytes (raw — the PEM/DER encoding adds a small overhead). Compare to RSA-2048: the private key is ~1.7 KB, public key ~270 bytes, signature 256 bytes. The size difference is structural — Ed25519 is the better-fitting primitive for protocols where signatures travel in fixed-size headers.

Exercise 2 — Compare signature sizes

# Generate an RSA-2048 keypair and sign the same message
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out /tmp/rsa-priv.pem
openssl pkey -in /tmp/rsa-priv.pem -pubout -out /tmp/rsa-pub.pem
openssl dgst -sha256 -sign /tmp/rsa-priv.pem -out /tmp/msg-rsa.sig /tmp/msg.txt

# Sizes
echo "Ed25519 signature size:"
wc -c < /tmp/msg.sig

echo "RSA-2048 SHA-256 signature size:"
wc -c < /tmp/msg-rsa.sig

Output: Ed25519 signature is 64 bytes, RSA-2048 signature is 256 bytes. Same security level (~128-bit), 4× the bytes for RSA. Multiplied across millions of TLS handshakes per day at a CDN, the bandwidth difference is real.

The other comparison worth running: time. ECDSA P-256 and Ed25519 sign in tens of microseconds; RSA-2048 takes 1-2 ms per sign. For services that sign millions of tokens per second (OAuth providers, identity systems), the throughput difference matters more than the bandwidth.

Common misconceptions

"A signature encrypts the message." A signature authenticates; encryption hides. They're orthogonal services. Some applications need both (encrypted-and-signed) — typically via separate primitives composed correctly, or via a unified construction like signed-encryption.

"MACs and signatures are basically the same." MACs use shared secrets (anyone with the key can produce or verify). Signatures use private/public split (only the signer can produce; anyone can verify). The asymmetry is the entire reason signatures exist.

"Deterministic signatures are less secure because they're predictable." They're more secure in practice. The "predictability" only means signing the same message twice produces the same signature — which is no leak, because anyone with the private key could have produced that signature anyway. The security improvement is removing the entire class of bad-randomness vulnerabilities that have broken ECDSA implementations for decades.

"Any bytes can be signed safely." The bytes you sign must be canonical and unambiguously typed. Two signed bytes that decode the same way under different parsers are a recipe for protocol confusion. Domain separation, canonical encoding, and signed context are how this is solved.

"If verification passes, the signer is morally trustworthy." Verification proves the signer holds the private key for the public key you trust, and that signer signed those specific bytes. It says nothing about whether the signer is benevolent, whether the bytes are correct, or whether the signer is who they claim to be in a deeper sense. Trust is a multi-layered judgment; signatures are one (technical) layer.