Prerequisites

Related

Blueprints · 1,715 words · 7 min read

Digital Signatures: Running Public-Key Crypto in Reverse

You sign with your private key. Anyone verifies with your public key. That one asymmetry underlies software updates, TLS certificates, git commits, and every system that has to trust code without trusting the channel.

Table of Contents
  1. TL;DR
  2. The Primitive, Stripped Down
  3. Why You Sign the Hash, Not the Document
  4. What a Hash Function Actually Promises
  5. Certificate Chains: Trust Through Signatures
  6. Code Signing
  7. Git and JWTs
  8. What Signatures Don’t Do
  9. The Broader Pattern

#TL;DR

RSA is symmetric in an unexpected way: the public and private keys are interchangeable in the math. Encrypting with the public key and decrypting with the private key gives you confidentiality. Reversing the direction — “encrypting” with the private key, “decrypting” with the public key — gives you authenticity: anyone can verify that only the key’s owner could have produced the result. This is a digital signature. You don’t sign the document directly; you sign a hash of it. The result underpins TLS certificates, signed Apple builds, Debian packages, JWTs, git commit signing, cryptocurrency transactions, and every other place where untrusted code has to be verified before being run.

#The Primitive, Stripped Down

The RSA post shows the two directions:

# Encryption: public key locks, private key unlocks
ciphertext = pow(message, e, n)
plaintext  = pow(ciphertext, d, n)

# Signing: private key locks, public key unlocks
signature  = pow(document_hash, d, n)
verified   = pow(signature, e, n)

The math is identical. What changes is the direction and, crucially, what the result means.

When you encrypt with someone’s public key, you’re saying: “I want only you to be able to read this.” When you sign with your own private key, you’re saying: “I want everyone to be able to verify I produced this.” The key pair does both jobs, because exponentiation mod n is commutative: (m^e)^d ≡ (m^d)^e (mod n).

This is specific to RSA. Not every public-key system is symmetric like this — Diffie-Hellman, for instance, is purely a key-agreement protocol and can’t sign directly. Signatures built on other math (DSA, ECDSA, EdDSA) are different primitives that happen to provide the same guarantee, not literally RSA-in-reverse.

#Why You Sign the Hash, Not the Document

The RSA primitive only works on numbers smaller than n. For 2048-bit RSA, that’s 256 bytes. Real documents are much bigger than that.

You could chop the document into chunks and sign each one, but that’s slow (one modular exponentiation per 256 bytes) and — more importantly — it doesn’t prove what you want to prove. Signing chunks proves you signed each chunk; it doesn’t prove you signed this sequence of chunks in this order. An attacker can reorder them, drop some, or mix signed chunks from different documents.

The fix is hash-then-sign:

  1. Compute a cryptographic hash of the entire document — a fixed-size fingerprint (typically 256 or 512 bits) that changes completely if any bit of the document changes.
  2. Sign the hash. One modular exponentiation, regardless of document size.
import hashlib

def sign(document_bytes, d, n):
    h = int.from_bytes(hashlib.sha256(document_bytes).digest(), 'big')
    return pow(h, d, n)

def verify(document_bytes, signature, e, n):
    h = int.from_bytes(hashlib.sha256(document_bytes).digest(), 'big')
    return pow(signature, e, n) == h

A one-bit change in the document produces a completely different hash, which verifies against a completely different number. The signature is effectively a commitment to this exact document, not just to the content at the signing moment.

(This is textbook RSA. Real signature schemes use structured padding — RSA-PSS — to prevent a class of attacks against raw hash-then-sign. Same idea, more care.)

#What a Hash Function Actually Promises

Digital signatures are only as strong as the hash function they use. The hash has to have three properties:

  • Pre-image resistance. Given a hash h, it’s infeasible to find a message m such that hash(m) = h. Without this, an attacker could forge a document to match an existing signature.
  • Second pre-image resistance. Given a message m and its hash hash(m), it’s infeasible to find a different message m' with the same hash. Without this, an attacker given a signed document could produce another document with the same signature.
  • Collision resistance. It’s infeasible to find any pair m, m' with hash(m) = hash(m'). Without this, an attacker can construct two documents ahead of time with the same hash, get you to sign one, and claim you signed the other.

Collision resistance is the strongest and easiest to break. The hash function lineup tells the story:

  • MD5 — 128-bit hash, broken. Collisions demonstrated in 2004, weaponized against Windows code-signing in 2008 (the Flame malware), now used only for non-security checksums.
  • SHA-1 — 160-bit, broken. Google demonstrated a collision in 2017 (the “SHAttered” paper). Git, which uses SHA-1, has been gradually migrating.
  • SHA-256, SHA-512 — part of the SHA-2 family, currently secure. This is what most modern signing uses.
  • SHA-3 — a different construction (Keccak-based) standardized in 2015 as a hedge against SHA-2 weaknesses that never materialized. Rarely the default but available.
  • BLAKE2, BLAKE3 — modern alternatives, faster than SHA-2 on most hardware, considered secure.

When SHA-1 was broken, every protocol that signed SHA-1 hashes of certificates suddenly had a migration problem. The signatures themselves were still cryptographically sound — but the underlying hash wasn’t, so the signature’s guarantees didn’t hold. “Our signature scheme uses SHA-1” was a sentence that caused years of emergency protocol updates.

#Certificate Chains: Trust Through Signatures

The most common digital signature you interact with — every time you load a web page — is a TLS certificate. The chain works like this:

Root CA certificate (DigiCert, Let's Encrypt, etc.)
   │
   │  signs
   ▼
Intermediate CA certificate
   │
   │  signs
   ▼
Server certificate  (for example.com)
   │
   └─ contains the server's public key

Your browser ships a list of trusted root certificate authorities — 100 or so root certificates burned into the OS or browser. When you connect to example.com:

  1. The server sends its certificate, which includes its public key, its domain name, and a signature.
  2. The signature was produced by an intermediate CA’s private key; the browser verifies it using the intermediate CA’s public key (also in the chain).
  3. The intermediate’s certificate was signed by a root CA, whose public key the browser already trusts.
  4. Every signature verifies → the browser trusts the server’s public key belongs to example.com → TLS can proceed.

Every link in the chain is a digital signature over a hash of a certificate’s contents. Break any link, you break the chain. The entire PKI — the public key infrastructure of the web — is an enormous tree of RSA or ECDSA signatures, rooted in about 100 keys that browsers trust by fiat.

#Code Signing

Every time your phone installs an app, it verifies a signature:

  • iOS and macOS. Every app is signed by an Apple developer certificate, and Apple itself re-signs every App Store app with its own key. The OS refuses to run unsigned code unless you explicitly override. “Notarization” adds a second signature from Apple confirming the app passed a malware scan.
  • Windows. Code signing is optional but heavily incentivized — unsigned installers produce scary UAC prompts. Kernel drivers require signed certificates.
  • Android. APKs are signed by the developer. Installation verifies the signature. Updates must be signed with the same key as the original; this is what prevents a malicious developer from publishing a “look-alike” update.
  • Debian, Fedora, Arch. Every package in the distribution is signed by a distribution-trusted key. apt and dnf refuse to install packages whose signatures don’t verify.

The common pattern: don’t run code unless someone you trust signed it. The signature doesn’t prove the code is good — a compromised developer key signs bad code just as happily as good — but it proves provenance. You know whose bug you’re running.

This is the model the internet settled on for software distribution and has been attacked from every angle since. Supply-chain compromises (SolarWinds, XZ Utils backdoor, 3CX) all had valid signatures, because the attackers had compromised the signing keys. A signature’s guarantee is structural, not semantic — it proves who, not what.

#Git and JWTs

Two places you see signatures every day at a lower level:

  • Signed git commits and tags. git commit -S signs the commit object with your GPG or SSH key. Anyone with your public key can verify you made the commit. GitHub displays a “Verified” badge. This was largely ignored for the first fifteen years of git’s existence and became important after it became clear that “commit author” and “actual person who made the commit” weren’t the same, and unsigned commits could be forged trivially.
  • JWTs (JSON Web Tokens). The structure is base64(header).base64(payload).base64(signature). The signature is a digital signature over header.payload — usually RS256 (RSA with SHA-256), ES256 (ECDSA with SHA-256), or HS256 (HMAC-SHA256 with a shared secret, not really a public-key signature but uses the same structure). A validly signed JWT is a self-contained claim that the server can verify without looking anything up.

The JWT example is a good illustration of how the signature primitive shifts a system’s trust model. Without signatures, sessions require a database lookup (is this session ID valid?). With signatures, the session is self-describing and verifiable, because the token contains its own proof that the server issued it.

#What Signatures Don’t Do

Digital signatures are widely misunderstood. Two things they explicitly don’t do:

  • They don’t encrypt. A signed document is entirely readable by anyone. If you need the contents to be secret, you encrypt separately, using a different key (and usually a different cryptosystem — sign with RSA, encrypt with AES).
  • They don’t timestamp. A signature proves who signed, not when. To get “signed at time T,” you need a separate timestamp authority — a trusted third party that signs (document_hash, timestamp) at the time of signing. Without this, an attacker who later compromises your key can produce backdated signatures that look valid.

They also don’t prove intent. A signature proves you held the key when it was used. It doesn’t prove you knew what you were signing, that you read the document, or even that you were aware you were signing at all. This is why hardware security tokens (YubiKeys, smart cards) typically require a physical button-press — it’s weak evidence of intent, but it’s something.

#The Broader Pattern

The RSA post frames digital signatures as “RSA’s second trick.” That framing is accurate for RSA but undersells the generality. Digital signatures are one of the two or three foundational primitives of modern cryptography, and they show up in places that have little to do with encrypting messages:

  • Blockchain transactions — every bitcoin transaction is a chain of ECDSA signatures proving ownership.
  • DNSSEC — DNS records are signed, so you can verify they weren’t tampered with between the authoritative server and your resolver.
  • Software updates — autoupdaters refuse to install unsigned updates.
  • SSH. Even server authentication (known_hosts) is verified against the server’s signed host key.
  • Certificate transparency logs — append-only logs of every certificate ever issued, each log entry signed, so a rogue CA can’t issue certificates secretly.

The primitive is deceptively simple: one key to sign, another to verify, a hash in the middle. Everything that has to verify the provenance of data in an adversarial environment is a downstream consumer of that simple idea — forty-nine years old, invented one April morning at MIT, still doing the job.