Chapter 21 — Digital signatures

In one sentence

A digital signature uses a private key to produce a tag that anyone with the matching public key can verify, proving the message is unchanged and came from the key's owner — and, unlike a MAC, proving it to third parties.

The problem

HMAC (Chapter 11) proves integrity and authenticity, but both parties share the key, so Bob can't prove to a judge that Alice — not Bob himself — produced a given tag. And HMAC needs a pre-shared secret, which brings back key distribution.

Signatures fix both:

   HMAC                              SIGNATURE
   ----                              ---------
   shared secret key                 private key signs / public key verifies
   either party can produce a tag    only the private-key holder can sign
   verifier could have forged it     verifier demonstrably could NOT have
   -> no non-repudiation             -> NON-REPUDIATION
   needs key pre-shared              public key can be published freely

Non-repudiation — the signer cannot credibly deny signing — is the property that makes signatures the basis of code signing, certificates, contracts, blockchains, and software updates.

How it actually works

You never sign the raw message (it's too big, and raw sign operations have structure). You sign its hash:

   SIGNING                                VERIFYING
   -------                                ---------
   1. h = SHA-256(message)                1. h  = SHA-256(received message)
   2. sig = Sign(private_key, h)          2. h' = Verify(public_key, sig)
   3. send (message, sig)                 3. accept iff h == h'

Consequences of the "sign the hash" design:

   - A broken hash breaks the signature scheme. SHA-1 collisions (Ch 9) meant
     an attacker could get a benign document signed and swap in a malicious
     one with the same hash. This is why CAs abandoned SHA-1.
   - The signature size depends only on the algorithm, not the message.
     A 10 GB file and a 10-byte file get the same 64-byte Ed25519 signature.

The algorithms

Scheme	Key type	Sig size (approx)	Notes
Ed25519	Curve25519	64 bytes	First choice. Deterministic, fast, misuse-resistant
ECDSA P-256	NIST P-256	~64-72 bytes (DER)	Ubiquitous in TLS; needs safe `k` (RFC 6979)
RSA-PSS	RSA-2048+	256+ bytes	Modern RSA signatures; use over PKCS#1 v1.5
RSA PKCS#1 v1.5	RSA-2048+	256+ bytes	Legacy but everywhere (JWT `RS256`); acceptable
Ed448	Curve448	114 bytes	Higher security margin, rarer
SLH-DSA / ML-DSA	post-quantum	7 KB - 50 KB	Part 6

What a signature does and does NOT prove

   PROVES:
     [x] the message wasn't altered after signing
     [x] whoever signed held the private key
     [x] (to a third party) that the key-holder signed -- non-repudiation

   DOES NOT PROVE:
     [ ] WHO the key-holder is         -> needs a certificate / web of trust
     [ ] WHEN it was signed            -> needs a trusted timestamp
     [ ] that the signer MEANT it / read it   ("what you see is what you sign")
     [ ] that the key isn't stolen or the signer isn't coerced
     [ ] freshness -- an old validly-signed message can be REPLAYED unless
         the signed content includes a nonce/timestamp

The gap between "valid signature" and "trustworthy message" is filled by PKI (Part 7) for identity, and by protocol design (nonces, timestamps, expiry) for freshness.

Where you'll use signatures

   TLS certificates        CA signs "this public key belongs to example.com"
   TLS handshake           server signs the ephemeral ECDHE params (authenticity)
   Code signing            Apple/Microsoft/distro signs binaries and packages
   Software updates        the update file is signed; the updater verifies
                             before installing (TUF, Sigstore)
   JWT (RS256/ES256/EdDSA) the token issuer signs the claims
   Git                     signed commits and tags (git commit -S)
   SSH                     server host key signs to prove identity; user key
                             signs to authenticate (Part 8)
   Blockchains             every transaction is a signature
   Secure boot             each stage verifies the next stage's signature

Worked example (run it)

cd ~/sec-lab/scratch

# --- Ed25519 end to end ---
openssl genpkey -algorithm ed25519 -out signer.pem
openssl pkey -in signer.pem -pubout -out signer.pub

cat > update.json <<'EOF'
{"version":"4.2.0","url":"https://cdn.example.com/app-4.2.0.tar.gz",
 "sha256":"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"}
EOF

# sign
openssl pkeyutl -sign -inkey signer.pem -rawin -in update.json -out update.sig

# verify (this is what the updater does before trusting the manifest)
openssl pkeyutl -verify -pubin -inkey signer.pub -rawin -in update.json \
        -sigfile update.sig

# attacker swaps the download URL
sed -i.bak 's#cdn.example.com#evil.example#' update.json
openssl pkeyutl -verify -pubin -inkey signer.pub -rawin -in update.json \
        -sigfile update.sig            # FAILS -- the manifest is rejected

# --- MAC vs signature: the non-repudiation difference ---
.venv/bin/python - <<'PY'
import hmac, hashlib
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

msg = b"Alice agrees to pay Bob 500."

# HMAC: Bob ALSO has the key, so Bob could have made this himself.
k = b"shared-key"
tag = hmac.new(k, msg, hashlib.sha256).hexdigest()
print("HMAC tag:", tag[:32], "...")
print("  -> a judge can't tell if Alice or Bob produced it. No non-repudiation.")

# Signature: only Alice has the private key.
alice = Ed25519PrivateKey.generate()
sig = alice.sign(msg)
alice.public_key().verify(sig, msg)      # raises if invalid
print("\nEd25519 signature verified against Alice's PUBLIC key.")
print("  -> only Alice's private key could produce it. Non-repudiation.")
PY

# --- signed Git commits ---
# git config --global user.signingkey <key>
# git config --global commit.gpgsign true      # or gpg.format ssh + user.signingkey
git init -q demo && cd demo
git config gpg.format ssh
git config user.signingkey "$PWD/../signer.pub"
git config gpg.ssh.allowedSignersFile /dev/null
echo hi > f && git add f
git -c commit.gpgsign=true commit -q -S -m "signed commit" 2>&1 | head -2 || true
git log --show-signature -1 2>&1 | head -8
cd ..

Practice (35 min)

Sign a release manifest with Ed25519; verify it; tamper with one byte of the manifest; confirm verification fails.
Sign the same manifest with RSA-PSS and with ECDSA P-256. Compare signature sizes and openssl speed sign/verify rates across all three.
Run the MAC-vs-signature script. Write, in notes.md, a two-sentence explanation of non-repudiation you could give a non-engineer.
Set up SSH-based signed Git commits (gpg.format ssh). Make a signed commit. Break the signature by amending the message with --no-gpg-sign and see git log --show-signature flag it.
Explain why "valid signature" does not mean "safe to run this binary". List three things still required.

Common confusions

"A signature encrypts the message." No. The message travels in the clear; the signature only proves integrity + origin. Combine with encryption if you need secrecy.
"Verifying a signature means I can trust the content." It means the content wasn't altered since signing by that key. Whether to trust that key is PKI's job.
"Sign then encrypt" vs "encrypt then sign". Both have pitfalls (identity stripping, surreptitious forwarding). Prefer a construction that binds identity into the signed/encrypted data, or use a vetted protocol.
"Old signatures stay valid forever, so replays are fine." A validly-signed message can be replayed. Put a timestamp/nonce/expiry inside the signed data.
"RSA signing = RSA decryption." Structurally similar, but different padding (PSS vs OAEP) and you must never share a key between the two roles.

Check yourself

What does a signature give you that an HMAC does not?
Why do you sign the hash of a message rather than the message itself?
What does a broken hash function do to a signature scheme? Give the real example.
List three things a valid signature does not prove.
How do you stop a validly-signed message from being replayed?