8.2.3 — Public Keys, Signatures and the Quantum Question

Symmetric encryption (Chapter 8.2.1) is fast and correct and has one unsolvable problem: both sides need the same key.

If you and I have never met, how do we agree on one? Sending it over the channel we are about to protect is obviously useless. Meeting in person does not scale to a browser talking to a server it has never seen. Until 1976 the answer was couriers and physical key distribution, and it was the limiting factor on secure communication.

Asymmetric cryptography solves it with a pair of keys that are mathematically related but not derivable from each other. One is published to the world; the other never leaves the machine. That single idea makes the modern internet possible.

1. The trapdoor idea

Everything here rests on a trapdoor one-way function: easy to compute forwards, hard to reverse — unless you know one secret piece of information, which makes reversing easy again.

The everyday intuition is multiplication. Multiplying two 300-digit primes takes microseconds. Given only the product, recovering the two primes is beyond any classical computer. The trapdoor is knowing one of the factors.

A key pair has two mirror-image uses, and keeping them straight is most of the subject.

Encrypt with the public key, decrypt with the private key — anyone can send you something only you can read. This is confidentiality.

Sign with the private key, verify with the public key — anyone can check that you, and only you, produced this. This is authenticity, and because only you hold the key, non-repudiation as well.

The direction is the whole thing. The public key is public; encrypting with your private key would let anyone decrypt, which is why "encrypting with the private key" is a description of signing rather than of secrecy.

2. RSA

Rivest, Shamir and Adleman published it in 1977. The mathematics is approachable if you take it in five steps.

1. Pick two large primes p and q. Compute n = pq. n is public; p and q are the secret.
2. Compute \phi(n) = (p-1)(q-1) — how many numbers below n share no factor with it.
3. Pick a public exponent e with no common factor with \phi(n). In practice e = 65537, chosen because it is prime and has only two set bits, which makes exponentiation fast.
4. Compute d such that e \cdot d \equiv 1 \pmod{\phi(n)}. d is the private key, and computing it requires \phi(n), which requires p and q.
5. Encrypt: c = m^e \bmod n. Decrypt: m = c^d \bmod n.

A tiny worked example, with absurdly small numbers so the arithmetic is checkable: p = 61, q = 53, so n = 3233 and \phi(n) = 60 \times 52 = 3120. Take e = 17; then d = 2753, since 17 \times 2753 = 46801 = 15 \times 3120 + 1.

Encrypt m = 65: 65^{17} \bmod 3233 = 2790. Decrypt: 2790^{2753} \bmod 3233 = 65.

Security rests on factoring being hard. Anyone who factors n recovers p and q, then \phi(n), then d. Nobody knows a fast classical algorithm; the best known are sub-exponential, which is why keys must be large.

Key sizes: 2048 bits is the current minimum, 3072 is the recommendation for data that must stay secret past 2030. 1024-bit RSA is broken in practice. Note how much larger these are than symmetric keys — 3072-bit RSA is roughly comparable to a 128-bit symmetric key, because the attacks are completely different.

Textbook RSA is broken, and this matters more than the mathematics. Raw m^e \bmod n is deterministic, so identical messages give identical ciphertexts and small messages can be attacked directly (m^e may be smaller than n, making it a plain cube root). Padding is mandatory:

• OAEP for encryption — adds randomness and structure.
• PSS for signatures — the modern, provably-secure padding.
• PKCS#1 v1.5 — the old scheme, still everywhere for compatibility, and the source of the Bleichenbacher attacks that have kept resurfacing since 1998.

Never implement RSA yourself, and never call a raw modular-exponentiation function on user data.

3. Elliptic curves

RSA works and its keys are large, which costs bandwidth in every handshake and CPU in every signature. Elliptic curve cryptography gives the same security with far smaller numbers.

A curve of the form y^2 = x^3 + ax + b over a finite field has a defined way to "add" two points together, producing another point on the curve. Multiplying a point G by an integer k means adding it to itself k times, computable quickly by repeated doubling.

The one-way function: given G and kG, recovering k is the elliptic curve discrete logarithm problem, and the best known attacks are far worse than factoring — which is exactly why the keys can be smaller.

Security level	RSA	ECC
112-bit	2048	224
128-bit	3072	256
192-bit	7680	384
256-bit	15360	512

A 256-bit ECC key matches a 3072-bit RSA key. Twelve times smaller, with faster key generation and signing. That is why every modern protocol prefers it.

The curves you will meet:

• P-256, P-384 (NIST) — universal support, used throughout TLS and in most certificates. Some unease persists about how the constants were chosen, without any demonstrated weakness.
• Curve25519 / X25519 — designed by Daniel Bernstein for speed and for being hard to implement incorrectly. The default for key exchange.
• Ed25519 — the signature scheme on the same curve. The default for new signature work: small keys (32 bytes), small signatures (64 bytes), fast, and deterministic, which removes the failure in section 5.

4. Diffie-Hellman, restated

Chapter 5.7 developed this with the paint analogy for TLS; here is the placement in the family.

Both sides agree publicly on a generator. Each picks a secret, computes its public value, and sends it. Each then combines their own secret with the other's public value, and both arrive at the same shared number. An eavesdropper who saw both public values cannot compute it.

Diffie-Hellman is not encryption and not signing — it is agreement. Its output is a shared secret, which is then used as a symmetric key.

The E for ephemeral is the part that matters operationally. ECDHE generates a fresh key pair per connection and discards it, giving forward secrecy: stealing the server's long-term private key tomorrow does not decrypt traffic recorded today.

And Diffie-Hellman alone is defenceless against an attacker in the middle, who simply runs two exchanges. That is why key exchange is always paired with authentication — a signature over the exchange, verified against a certificate.

5. Digital signatures

You do not sign the message. You sign its hash.

Three reasons: asymmetric operations are slow and a hash is small and fixed-size; RSA cannot sign anything larger than its modulus anyway; and the hash is what gets padded and transformed.

This is why a collision in the hash breaks the signature (Chapter 8.2.2). If an attacker finds two documents with the same hash, a signature over one is a valid signature over the other. That is the concrete reason SHA-1 certificates had to die.

The algorithms:

RSA-PSS — well understood, large signatures.

ECDSA — the elliptic-curve standard, used in TLS certificates and in Bitcoin. It has one dangerous property: each signature requires a random nonce, and reusing that nonce with the same key reveals the private key through simple algebra. This is not theoretical — Sony's PlayStation 3 used a constant nonce, and the signing key was recovered and published in 2010. The same bug has drained Bitcoin wallets whose implementations had weak randomness.

Ed25519 — derives the nonce deterministically from the message and the private key, so the failure above cannot happen. Smaller, faster, and easier to implement safely. Use it unless something forces otherwise.

Verification depends entirely on trusting the public key. A signature verifying against a public key proves the message came from whoever holds the matching private key — it says nothing about who that is. Binding a key to an identity is the job of certificates and a trust hierarchy, which is Chapter 8.3.1, or of a web of trust, which is how PGP tried to do it.

MAC or signature? A MAC (Chapter 8.2.2) is faster and uses a shared key, so either party could have produced it. A signature uses a private key, so only one party could, which is what lets a third party adjudicate. Choose a MAC when both ends are yours; choose a signature when a third party must be convinced or when the verifier must not be able to forge.

6. Hybrid encryption: what actually happens

Asymmetric encryption is never used for bulk data. It is roughly a thousand times slower than AES, and RSA cannot encrypt more than its key size minus padding — about 190 bytes for a 2048-bit key.

So every real system uses hybrid encryption:

1. Generate a random symmetric key.
2. Encrypt the data with it, using AES-GCM (Chapter 8.2.1).
3. Encrypt the symmetric key with the recipient's public key.
4. Send both.

TLS does this, PGP does this, and the envelope encryption of Chapter 8.2.1 is the same shape with a key management service in the role of the private key holder. When someone says "encrypted with RSA", what happened is almost always this.

7. The quantum question, honestly

Shor's algorithm (1994) factors integers and computes discrete logarithms in polynomial time on a sufficiently large quantum computer. That breaks RSA, Diffie-Hellman and elliptic curves — all of them, completely, not by weakening them.

Symmetric cryptography is far less affected. Grover's algorithm gives a square-root speed-up on brute force, which halves the effective key length: AES-128 drops to 64-bit strength, AES-256 to 128-bit. The response is to use AES-256 and move on. Hash functions are similarly affected and similarly manageable.

No quantum computer today can factor a meaningful key, and estimates for when one might range from a decade to never. So why act now?

Harvest now, decrypt later. An adversary can record encrypted traffic today and decrypt it when the capability exists. For data with a long secrecy requirement — health records, state secrets, identity documents — that is a present risk with a future exploit.

NIST standardised the replacements in August 2024:

• ML-KEM (FIPS 203), formerly Kyber — key encapsulation, replacing Diffie-Hellman.
• ML-DSA (FIPS 204), formerly Dilithium — signatures.
• SLH-DSA (FIPS 205), formerly SPHINCS+ — hash-based signatures, slower and larger, resting on much more conservative assumptions.

Deployment is happening as hybrids. TLS is being deployed with X25519 combined with ML-KEM, so the connection is secure if either holds. Chrome and Cloudflare enabled this by default during 2024, and a meaningful share of TLS connections already use it. That is the pattern to expect: not a switch, but a period of doubled-up key exchange.

What to do now, in order: use AES-256 rather than AES-128 for anything long-lived; keep an inventory of where cryptography is used and what algorithm each place assumes, because the hard part of migration is discovery rather than mathematics; build crypto agility into new systems — the version byte from Chapter 8.2.1, negotiated algorithms, no format that hardcodes a key length; and for data that must remain secret for more than a decade, plan a hybrid deployment. Do not rewrite working systems today, and do not use a proprietary "quantum-safe" product that is not one of the standardised algorithms.

8. Choosing

Need	Use
Agree a key with a stranger	X25519 (ECDHE), plus authentication
Sign something	Ed25519, or ECDSA P-256 for compatibility
Encrypt for a recipient	Hybrid: random AES key, wrapped with their public key
Prove origin to a third party	Signature
Prove origin between two systems you own	HMAC — faster and simpler
Long-lived confidentiality	AES-256, and plan a hybrid post-quantum key exchange

What the interviewer will push on

"What problem does public-key cryptography solve?" Key distribution — agreeing a secret with someone you have never met over a channel anyone can read. Then the two mirror uses: encrypt with the public key for confidentiality, sign with the private key for authenticity and non-repudiation.

"Why is a 256-bit ECC key as strong as a 3072-bit RSA key?" Because the underlying problems differ: factoring has sub-exponential attacks, the elliptic-curve discrete log does not, so ECC needs fewer bits for the same work factor. That is what makes it the default in bandwidth-sensitive protocols.

"How does signing actually work?" Hash the message, then transform the hash with the private key using a proper padding scheme. Then the consequence that matters: a hash collision forges the signature, which is exactly why SHA-1 certificates had to be removed.

"What is wrong with ECDSA?" It needs a random nonce per signature, and reusing one with the same key reveals the private key algebraically. Name the PlayStation 3 (a constant nonce, key recovered in 2010) and the drained Bitcoin wallets. Then give the fix: Ed25519 derives the nonce deterministically, so the failure is impossible.

"How is a large file encrypted with someone's public key?" It is not. Hybrid encryption: random symmetric key, encrypt the data with AES-GCM, encrypt only the key asymmetrically. Asymmetric is a thousand times slower and RSA cannot encrypt more than ~190 bytes with a 2048-bit key.

"What does quantum computing break, and what should you do?" RSA, Diffie-Hellman and ECC completely, via Shor. Symmetric and hashes lose half their strength via Grover, so AES-256 is the answer there. Act now only because of harvest now, decrypt later; the practical steps are AES-256 for long-lived data, an inventory of where cryptography lives, crypto agility, and hybrid TLS with ML-KEM.

One thing to volunteer: point out that the hard part of a post-quantum migration is discovery, not mathematics — most organisations cannot list where cryptography is used, which algorithm each place assumes, or which formats have a key length baked in. Building an inventory and a version field into new formats is the work that pays off, and it is useful regardless of quantum computers.

Recall

• Asymmetric cryptography solves key distribution. Encrypt with the public key for confidentiality; sign with the private key for authenticity and non-repudiation. The direction is the whole idea.
• RSA rests on factoring being hard: n = pq public, p and q secret, e = 65537, d derivable only from \phi(n). 2048 bits minimum, 3072 for anything long-lived. Textbook RSA is broken — OAEP for encryption, PSS for signatures, never raw.
• ECC rests on the elliptic curve discrete logarithm problem, which has no sub-exponential attack, so 256-bit ECC ≈ 3072-bit RSA. X25519 for exchange, Ed25519 for signatures.
• Diffie-Hellman is agreement, not encryption, and is defenceless against an attacker in the middle without authentication. Ephemeral keys give forward secrecy.
• You sign the hash, not the message — which is why a hash collision forges a signature and why SHA-1 certificates had to die.
• ECDSA's per-signature nonce is fatal if reused — the PlayStation 3's constant nonce leaked Sony's signing key in 2010. Ed25519 derives it deterministically and cannot fail this way.
• Asymmetric never encrypts bulk data. Hybrid encryption: random AES key for the data, public key wraps only the key. TLS, PGP and envelope encryption are all this shape.
• Shor breaks RSA, DH and ECC entirely; Grover halves symmetric strength, so use AES-256. Act now because of harvest now, decrypt later. NIST standardised ML-KEM, ML-DSA and SLH-DSA in 2024, deployed as hybrids alongside X25519. The hard part of migration is inventory and crypto agility, not mathematics.

Self-test: Which key encrypts and which decrypts, and why does the reverse mean signing? · Why does ECC need a twelfth of RSA's key size? · What does a hash collision do to a signature? · What happened when Sony reused an ECDSA nonce? · What actually happens when a file is "encrypted with RSA"? · Why act on post-quantum now if no quantum computer exists?

Next: 8.3.1 turns keys into identities — certificates, the chain of trust, and the file formats (.pem, .key, .pfx, .csr, .ppk) that everyone confuses at least once.