0.5 Public-key cryptography and key exchange

The key-distribution problem

The symmetric ciphers in 0.3 are fast and secure, but both sides need the same secret key first. Two people in the same room can share it on paper. A browser talking to a server it has never seen before cannot: every byte it sends travels over networks that anyone may read.

For centuries this was the hard part of cryptography. Governments shipped code books by courier. In 1976 Whitfield Diffie and Martin Hellman published a way to agree on a key using only public messages. That idea, and the family of techniques that grew from it, is public-key cryptography: each party has a private key it never shares and a public key it can show to anyone.

One-way functions

Public-key cryptography needs operations that are easy in one direction and hard in the other. Mixing paint is a good picture: combining yellow and blue is instant, but given the green you cannot easily say how much of each went in. In mathematics the standard examples are:

• Modular exponentiation. Computing $g^a \bmod p$ takes a few hundred multiplications even for 3000-bit numbers. Recovering $a$ from the result, the discrete logarithm, has no known fast method.
• Multiplying primes. Multiplying two 1500-bit primes is instant. Factoring their product back into the primes is far beyond current computers.
• Scalar multiplication on an elliptic curve. Adding a point to itself $k$ times is fast; finding $k$ from the result is the elliptic-curve discrete logarithm.

Some one-way functions have a trapdoor: a piece of secret information that makes the reverse direction easy. RSA is built on such a trapdoor. Diffie–Hellman does not need one.

A two-minute warm-up: arithmetic mod p

All of these schemes compute with remainders. Working modulo $p$ means you keep only the remainder after dividing by $p$, like hours on a clock: 10 o’clock plus 5 hours is 3 o’clock, because $15 \bmod 12 = 3$. The same works for multiplication and powers. With $p = 23$:

The powers of 5 modulo 23 jump around: 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, … and they visit every number from 1 to 22 before repeating. A number with this property is called a generator. The notation $a \equiv b \pmod p$ and the other symbols are collected in 8.1 Numbers, sets and modular arithmetic.

Diffie–Hellman key exchange

Check it by hand with $p = 23$, $g = 5$, $a = 6$, $b = 15$. Alice sends $A = 5^6 \bmod 23 = 8$, Bob sends $B = 5^{15} \bmod 23 = 19$. Then Alice computes $19^6 \bmod 23 = 2$ and Bob computes $8^{15} \bmod 23 = 2$. The shared secret is 2, and it never crossed the network.

p, g = 23, 5          # public: a small prime and a generator
a, b = 6, 15          # private: Alice's and Bob's secrets

A = pow(g, a, p)      # Alice sends A
B = pow(g, b, p)      # Bob sends B

print("A =", A, " B =", B)
print("Alice computes", pow(B, a, p), " Bob computes", pow(A, b, p))

A = 8  B = 19
Alice computes 2  Bob computes 2

An eavesdropper sees 23, 5, 8 and 19. To get the secret they would have to find $a$ with $5^a \equiv 8 \pmod{23}$. For such a small prime you can simply try all 22 values. Real Diffie–Hellman uses primes of 2048 bits or more, where the best known algorithms would take longer than the age of the universe on all the world’s computers. This is the discrete-logarithm assumption: nobody has proved it, but decades of work have not broken it for large, well-chosen groups.

RSA: a trapdoor you can publish

RSA (Rivest, Shamir and Adleman, 1977) works differently. Instead of agreeing on a secret, anyone can encrypt a short message to your public key, and only you can decrypt it. The trapdoor is the factorization of a large number.

The toy version is useful for understanding and dangerous to use. “Textbook” RSA is deterministic, so encrypting the same message twice gives the same ciphertext, and it leaks structure an attacker can exploit. Real RSA encryption always adds randomized padding first (RSA-OAEP, standardized in RFC 8017), and real keys use a modulus of 2048 or 3072 bits. Most new protocols no longer use RSA for key exchange at all; they use elliptic curves.

Elliptic curves without the heavy algebra

An elliptic curve is the set of points $(x, y)$ that satisfy an equation such as $y^2 = x^3 + ax + b$, with all arithmetic done modulo a prime. The key fact is that you can add two points on the curve and get a third point on the curve, using a fixed geometric rule: draw the line through them, find where it meets the curve again, and reflect.

Adding a starting point $G$ to itself $k$ times gives $kG$. On the small curve $y^2 = x^3 + 2x + 2$ modulo 17 with $G = (5, 1)$, the multiples go $2G = (6, 3)$, $3G = (10, 6)$, $4G = (3, 1)$, and after 19 steps return to the starting point. Computing $kG$ for a 255-bit $k$ takes about 255 doublings and additions. Finding $k$ from $kG$ is the elliptic-curve discrete logarithm, and for well-chosen curves the best known method needs about $2^{128}$ operations.

Elliptic-curve Diffie–Hellman (ECDH) is Diffie–Hellman with points instead of powers: Alice sends $aG$, Bob sends $bG$, and both compute $abG$. The two curves you will meet most often are:

• X25519 (Curve25519, RFC 7748). Designed so that simple code is fast and constant-time. Public keys and shared secrets are 32 bytes. It is the default key exchange in TLS 1.3, SSH, Signal and WireGuard.
• P-256 (secp256r1, NIST). Widely supported by hardware security modules and required by some compliance regimes.

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey

alice_private = X25519PrivateKey.generate()
bob_private = X25519PrivateKey.generate()

# Each side sends only its public key (32 bytes) over the network.
alice_public = alice_private.public_key()
bob_public = bob_private.public_key()

alice_shared = alice_private.exchange(bob_public)
bob_shared = bob_private.exchange(alice_public)

print(len(alice_shared), "bytes")
print(alice_shared == bob_shared)

32 bytes
True

How big should keys be?

Security is measured in bits: $k$-bit security means the best known attack needs about $2^k$ operations. Elliptic-curve keys are much shorter than RSA keys for the same level, because the best attacks on elliptic curves are much slower than the best factoring algorithms.

The table follows NIST SP 800-57 Part 1. Sizes are key lengths in bits. All of these numbers assume classical computers; 0.7 explains why a large quantum computer would break RSA, Diffie–Hellman and elliptic curves at every size.

Key exchange needs authentication

Diffie–Hellman protects against someone who only listens. Someone who can change traffic can sit in the middle: they run one exchange with Alice while pretending to be Bob, and another with Bob while pretending to be Alice. Each side ends up with a key shared with the attacker, and nothing in the math looks wrong.

The fix is to authenticate the public keys. In TLS the server signs its key-exchange message with a key that a certificate authority has vouched for, so the browser can check it really came from the site. That is the job of digital signatures, covered in 0.6.

Putting it together: hybrid encryption

Public-key operations are thousands of times slower than symmetric encryption and handle only short inputs. So real systems use each for what it is good at:

1. A key exchange (or a key-encapsulation mechanism, see 0.7) produces a shared secret.
2. A key-derivation function (0.4) turns that secret into symmetric keys.
3. An AEAD cipher such as AES-GCM or ChaCha20-Poly1305 (0.3) encrypts and authenticates the actual data.

Every HTTPS connection you open follows this pattern. The same pattern appears in the post-quantum world: ML-KEM replaces the key exchange, and in hybrid TLS it runs alongside X25519.

Common mistakes

• Using textbook RSA. Always use a vetted scheme with padding (RSA-OAEP for encryption), or better, X25519 with a KEM or HPKE (RFC 9180).
• Using the shared secret directly as a key. Run it through a KDF such as HKDF first; raw Diffie–Hellman outputs are not uniformly random bytes.
• Skipping authentication. An unauthenticated key exchange gives an attacker in the middle full access.
• Choosing parameters yourself. Use named, standard groups and curves (X25519, P-256, RFC 7919 groups). Custom primes and curves are a common source of weaknesses.
• Writing your own implementation. Timing differences can leak private keys. Use a maintained library such as the Python cryptography package, libsodium or your platform’s crypto API.

Further reading

Diffie and Hellman, “New Directions in Cryptography” (1976), the original paper. NIST SP 800-57 Part 1 Rev. 5, “Recommendation for Key Management”, for the security-level table. David Wong, Real-World Cryptography (Manning, 2021), chapters 5 and 6, for key exchange and asymmetric encryption in practice. These references are cited from memory.

Next: 0.6 Digital signatures, which solve the authentication problem.