Skip to content
CryptoVault

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.

  1. V.1The key distribution problem
  2. V.2One-way functions
  3. V.3Diffie-Hellman
  4. V.4RSA
  5. V.5Elliptic curves
  6. V.6Hybrid encryption and forward secrecy

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.

a shared key per paira key pair eachdirectorypublic keys15 shared secret keys1,000 people: 499,5006 private keys, kept1,000 people: 1,000
Public keys can be published. What remains is knowing whose key you hold: chapter VI.

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.

factoringdiscrete logarithm61 × 53multiply?323301234567891011121314151617181920212261 × 53 = 3233back: 27 trial divisions56 mod 23 = 8back: 7 tries
At real sizes the forward arrows stay instant; the way back becomes infeasible.
RSA rests on factoring; Diffie-Hellman and DSA on the discrete logarithm modulo a prime; ECDH, ECDSA and Ed25519 on its elliptic-curve version. A large quantum computer would break all three (chapter IX).

Diffie-Hellman

Each side raises a public base to a private exponent. Both reach the same secret; an eavesdropper sees only the public halves.

the public wirep = 23, g = 5AAlicea = 656 mod 23A = 8196 mod 23 = 2BBobb = 15515 mod 23B = 19815 mod 23 = 2819EEvesees 23, 5, 8, 19needs 6 or 15

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.

PitfallIt stops Eve, who listens, not Mallory, who changes messages: she runs one exchange with each side and reads everything (chapter VI).

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.

p = 61, q = 53n = 3233p × qφ = 3120(p − 1)(q − 1)e = 17chosend = 2753e−1 mod φinvertpublic keykept secret65279065encrypt with edecrypt with d6517 mod n27902753 mod n
Try it: edit a number you cannot read

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.

PitfallTextbook RSA is deterministic, so anyone can encrypt a guess and compare, and malleable, as above. Real RSA pads with randomness first, OAEP to encrypt and PSS to sign, with e = 65537 and n of 2048 bits or more.

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.

y2 = x3 + 2x + 2over the real numbersmodulo 17PQP + QG2G3G016
Adding G to itself k times gives k·G. Modulo 17, the multiples land in no visible order.
Try it: walk the 19 points

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.

00881616G

On a well-chosen curve the best attacks cost about √n steps for n points, so a 256-bit curve gives 128-bit security.

securityRSA moduluselliptic curve112-bit2,048224–255128-bit3,072256–383192-bit7,680384–511256-bit15,360512+
Comparable strengths, from NIST SP 800-57 Part 1, revision 5.
X25519 for key exchange, Ed25519 or ECDSA on P-256 for signatures.

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.

sent to BobBob’s public keyde9e db7d …fresh private key7707 6d0a …its public half8520 f009 …X25519shared secret4a5d 9d5b …HKDFAES-256 keyff9c 04b4 …KEMagree on a keyDEMencrypt the dataMeet me at noonAES-GCMciphertext, 31 bytesc7de 0423 …
Bob redoes X25519 with his private key and the public half, and finds the same AES key.

Forward secrecy goes further: both sides’ keys are ephemeral, and the long-term key only signs.

the sessionrecorded by Evea year laterRSA key transport (TLS 1.2 and earlier)session key656517 mod 32332790d = 2753 leaks65: readephemeral Diffie-Hellman (TLS 1.3)a and b, then erased6, 15A and B8, 19signing key leaksnothingsession key 2, never sent
Erase ephemeral keys, and yesterday’s traffic survives tomorrow’s leak.

In one breath

  1. 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.
  2. 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.
  3. Diffie-Hellman. Each side raises a public base to a private exponent. Both reach the same secret; an eavesdropper sees only the public halves.
  4. RSA. Multiply two secret primes into a public modulus. Only someone who knows the primes can compute the exponent that undoes encryption.
  5. 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.
  6. 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.