0.6 Digital signatures and certificates

What a signature proves

Think of a wax seal that anyone can inspect but only one person can press. You sign a message with your private key, which never leaves your machine. Anyone who has your public key can check the result. If the check passes, three things follow:

• Authenticity: the signature was made by whoever holds the private key.
• Integrity: the message is exactly what was signed. Change one bit and the check fails.
• Non-repudiation: the signer cannot later claim someone else made it, because nobody else had the key.

A signature does not hide the message. It is sent alongside the message in the clear. If you also need secrecy, you encrypt as well (see 0.3).

Signatures versus MACs

A message authentication code such as HMAC also gives authenticity and integrity, but with a shared key. Both sides can create valid tags, so a tag convinces the receiver but proves nothing to a third party. A signature splits the roles: only the signer can create, everyone can verify. MACs are much faster and are the right choice inside a single protected channel; signatures are the right choice when the verifier is someone you have never met, such as the users downloading your software.

Sign and verify

Every signature scheme has the same three operations:

The same flow in Python with the cryptography library. The key comes from a fixed seed so the output below is reproducible:

from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
from cryptography.hazmat.primitives import serialization
from cryptography.exceptions import InvalidSignature

# Fixed 32-byte seed so the output is reproducible. In real code: Ed25519PrivateKey.generate()
sk = Ed25519PrivateKey.from_private_bytes(bytes(range(32)))
pk = sk.public_key()

msg = b"Pay Bob 10 dollars"
sig = sk.sign(msg)
raw_pk = pk.public_bytes(serialization.Encoding.Raw, serialization.PublicFormat.Raw)
print("public key:", len(raw_pk), "bytes", raw_pk.hex()[:32] + "...")
print("signature: ", len(sig), "bytes", sig.hex()[:32] + "...")
print("same signature again:", sk.sign(msg) == sig)

pk.verify(sig, msg)            # returns None: valid
print("verify original: ok")
try:
    pk.verify(sig, b"Pay Bob 1000 dollars")
except InvalidSignature:
    print("verify edited message: InvalidSignature")

public key: 32 bytes 03a107bff3ce10be1d70dd18e74bc099...
signature:  64 bytes a720dcb3cfd8336066e0db2899679f9a...
same signature again: True
verify original: ok
verify edited message: InvalidSignature

Notice the line same signature again: True. Ed25519 is deterministic: the same key and message always give the same signature. The next section explains why that is a feature.

Hash, then sign

Signature algorithms work on fixed-size numbers, but messages can be gigabytes. So every scheme first runs the message through a hash function and signs the short digest. This is safe because the hash is collision-resistant: finding two messages with the same digest, and so the same signature, is infeasible. It also means a signature is only as strong as its hash. Signatures built on MD5 or SHA-1 were retired once collisions in those hashes became practical.

The schemes you will meet

RSA-PSS

RSA signing raises a padded digest to the private exponent modulo a large number $N$ (see 0.5). Signatures and public keys are as long as $N$: 256 bytes at 2048 bits. PSS is the modern randomized padding; the older PKCS#1 v1.5 padding is still everywhere but PSS is preferred for new designs. RSA is slow to sign and fast to verify.

ECDSA

ECDSA works on an elliptic curve, usually P-256. Keys and signatures are small (64 bytes of raw signature), and it is the standard choice in TLS certificates, smart cards and many blockchains. Each signature uses a fresh secret number, the nonce $k$.

Ed25519

Ed25519 (RFC 8032) is a Schnorr-style signature on the Edwards form of Curve25519. It has 32-byte public keys, 64-byte signatures, fast constant-time implementations, and no parameters to get wrong. It is the default in SSH, WireGuard, Signal, Git commit signing and many package managers. If you are choosing today and do not need FIPS-only algorithms, choose Ed25519.

Why the nonce matters

ECDSA and Schnorr signatures mix a secret per-signature nonce into the result. The whole scheme relies on that nonce being unpredictable and never reused. If the same nonce signs two different messages, simple algebra on the two signatures reveals the private key. Even a nonce that is only slightly biased, a few predictable bits out of 256, leaks the key after enough signatures; the hidden number problem guide shows the mathematics behind that. Real incidents have come from broken random number generators, not from broken curves.

The fix is to stop depending on randomness at signing time. Ed25519 derives the nonce by hashing a secret half of the key together with the message, and RFC 6979 does the same for ECDSA. The signature becomes deterministic, which is why the Python example produced the same bytes twice.

Sizes at a glance

Classical sizes were measured with the cryptography library; the ML-DSA row is from FIPS 204. RSA public keys also carry the exponent and encoding overhead, so a DER-encoded 2048-bit key is about 294 bytes.

Certificates and PKI

A signature tells you a message came from the holder of a particular public key. It does not tell you whose key that is. If an attacker hands you their own public key and claims it belongs to your bank, every signature they make will verify. Certificates solve this binding problem.

A certificate is a small document saying “the public key K belongs to example.com, valid until this date”, signed by a certificate authority (CA). The CA checked that the requester controls the domain before signing. Your browser and operating system ship with a list of about a hundred root CA public keys. When a site presents its certificate, the browser checks a chain: the site certificate is signed by an intermediate CA, whose certificate is signed by a root the browser already trusts. This whole system of CAs, chains and revocation is called a public key infrastructure (PKI).

In a TLS handshake the server sends its certificate chain and then signs the handshake transcript with the certificate's private key. That signature proves the server really holds the key named in the certificate. The session itself is then protected by a key agreed with key exchange and encrypted with symmetric encryption; see hybrid TLS for the post-quantum version.

Where signatures are used

• Software updates and code signing. Your OS installs an update only if it is signed by the vendor's key, so a compromised download mirror cannot push malware.
• Package managers and Git. Signed packages and commits let you check who published a release.
• Tokens. A JSON Web Token (JWT) carries a signature over its claims so an API can trust them without a database lookup.
• Documents and email. PDF signatures, S/MIME and PGP.

Common mistakes

• Trusting the algorithm field. Old JWT libraries accepted "alg": "none" (no signature at all), or verified an RSA-signed token with HMAC using the public key as the secret. Pin the expected algorithm and key on the server; never let the token choose.
• Verifying a public key you got from the same untrusted channel. A signature checked against an attacker's key proves nothing. Get keys from a certificate chain, a pinned value, or a trusted registry.
• Rolling your own nonces. Use Ed25519 or a library that implements RFC 6979 instead of generating ECDSA nonces yourself.
• Signing something ambiguous. Sign a canonical encoding that includes the context (who, what, when). Signing loosely formatted JSON lets two different readings share one signature.
• Confusing signing with encryption. A signed message is readable by anyone.

Post-quantum signatures are coming

RSA, ECDSA and Ed25519 all rest on factoring or discrete logarithms, which Shor's algorithm would solve on a large quantum computer (see 0.7). NIST has standardized replacements: ML-DSA (lattice-based, FIPS 204), SLH-DSA (hash-based, FIPS 205), and FN-DSA, the upcoming standard based on Falcon. They keep the same sign/verify API, with larger keys and signatures. Signatures are less urgent than encryption, because a signature only has to resist forgery until it is checked, but long-lived roots of trust such as CA keys and firmware signing keys are being migrated first.

Further reading

• RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA), and RFC 6979, Deterministic Usage of DSA and ECDSA.
• NIST FIPS 186-5, Digital Signature Standard (RSA, ECDSA and EdDSA).
• David Wong, Real-World Cryptography, chapter 7 on signatures (chapter number cited from memory).

Next: 0.7 Quantum computers and KEMs, what breaks and what replaces it.