Chapter V
Public-key cryptography
Two strangers agree on a secret in public, thanks to math that is easy one way and infeasible the other.
The key distribution problem
With shared keys only, N people need N(N−1)/2 keys, each one exchanged in advance over a safe channel.
Public-key cryptography splits the key in two. The public half, published, lets anyone encrypt to you or check your signature; the private half, kept, decrypts and signs.
One-way functions
Multiplying primes or exponentiating modulo a prime is fast. Undoing it, factoring or taking a discrete logarithm, is infeasible at real sizes.
“mod 23” keeps the remainder after dividing by 23: arithmetic on a clock of 23 hours. Undoing the power is the discrete logarithm.
Diffie-Hellman
Each side raises a public base to a private exponent. Both reach the same secret; an eavesdropper sees only the public halves.
Both reach the same number because exponents multiply in either order: (gb)a = (ga)b. Real exchanges use a 2048-bit prime or, far more often, an elliptic curve.
RSA
Multiply two secret primes into a public modulus. Only someone who knows the primes can compute the exponent that undoes encryption.
Computing d needs φ(n), and φ(n) needs the factors of n: they are the trapdoor.
Intercepted ciphertext 2790 under the public key n = 3233, e = 17
She sends 2790 × 217 mod 3233 = 3017
Bob decrypts it to 130 = 2 × 65. Mallory never learned 65 or the private exponent.
Elliptic curves
Points on a curve can be added. Multiplying a point by a number is easy, undoing it is hard, and keys are about ten times smaller than RSA’s.
k·G = (5, 1)
The 18 dots are all the solutions of y² = x³ + 2x + 2 mod 17; plus the point at infinity, O, they make 19 points. Starting from G = (5, 1), each step adds G once more. The public key is where the walk stops; the private key is the number of steps.
On a well-chosen curve the best attacks cost about √n steps for n points, so a 256-bit curve gives 128-bit security.
Hybrid encryption and forward secrecy
Public-key crypto only agrees on a fresh symmetric key. The data itself goes through AEAD, and ephemeral keys protect past sessions.
Public-key operations are slow and small, 190 bytes for 2048-bit RSA-OAEP with SHA-256, so they only agree on a key; an AEAD (chapter IV) carries the data.
Forward secrecy goes further: both sides’ keys are ephemeral, and the long-term key only signs.
In one breath
- The key distribution problem. With shared keys only, N people need N(N−1)/2 keys, each one exchanged in advance over a safe channel.
- One-way functions. Multiplying primes or exponentiating modulo a prime is fast. Undoing it, factoring or taking a discrete logarithm, is infeasible at real sizes.
- Diffie-Hellman. Each side raises a public base to a private exponent. Both reach the same secret; an eavesdropper sees only the public halves.
- RSA. Multiply two secret primes into a public modulus. Only someone who knows the primes can compute the exponent that undoes encryption.
- Elliptic curves. Points on a curve can be added. Multiplying a point by a number is easy, undoing it is hard, and keys are about ten times smaller than RSA’s.
- Hybrid encryption and forward secrecy. Public-key crypto only agrees on a fresh symmetric key. The data itself goes through AEAD, and ephemeral keys protect past sessions.