Classical Crypto Today

Two parties agree on a shared secret over a public channel, without ever transmitting the secret itself — the idea that started public-key cryptography.

The original public-key idea

Published by Whitfield Diffie and Martin Hellman in 1976, the Diffie-Hellman (DH) key exchange was the first published practical method for two parties to establish a shared secret over an insecure channel — without any prior shared secret.

The classical version relies on the discrete logarithm problem in modular arithmetic: given a large prime p, a generator g, and g^a mod p, it's hard to recover a. Alice picks a secret a and sends g^a mod p; Bob picks a secret b and sends g^b mod p. Each raises the received value to their own secret: (g^b)^a = (g^a)^b = g^ab mod p — the shared secret, which an eavesdropper watching only g^a and g^b cannot feasibly compute.

Diffie-Hellman key exchange

Both then compute the same value independently: Alice raises B to her secret a; Bob raises A to his secret b. Neither ever transmits a or b.

A = g^{a} \bmod p \qquad B = g^{b} \bmod p

Alice and Bob each compute a public value from their own secret exponent.

B^{a} \bmod p = g^{ab} \bmod p = A^{b} \bmod p

Both sides land on the same shared secret — without ever transmitting a or b.

A worked example with small numbers

Take the small prime p = 23 and generator g = 5. Alice picks secret a = 6 and computes A = 5⁶ mod 23 = 8. Bob picks secret b = 15 and computes B = 5¹⁵ mod 23 = 19. They exchange A and B in the open.

Alice now computes B^a mod p = 19⁶ mod 23 = 2. Bob computes A^b mod p = 8¹⁵ mod 23 = 2. Same answer, reached independently — and an eavesdropper who saw p, g, A, and B has to solve a discrete logarithm to recover a or b, which is infeasible once these numbers are hundreds of digits long instead of two.

p=23,\ g=5,\ a=6,\ b=15

A = 5^{6} \bmod 23 = 8 \qquad B = 5^{15} \bmod 23 = 19

19^{6} \bmod 23 = 8^{15} \bmod 23 = 2 \quad\text{(the shared secret)}

From shared secret to symmetric key

The raw shared secret — a single large integer both sides computed — is never used directly as an AES key. It's run through a hash function first (in modern designs, through HKDF, covered in the KDF module), producing a fixed-size digest that's then truncated or expanded to exactly the key length needed. This matters because the shared secret's size depends on the modulus p, while AES needs a specific fixed key size regardless of which DH group produced the secret.

Worked example: a DH exchange over a 2048-bit prime produces a shared secret that, once hashed with SHA-256, gives a 32-byte (256-bit) digest. An application needing an AES-128 key uses only the first 16 bytes of that digest and discards the rest — the extra bytes aren't wasted security, they're simply more output than an AES-128 key requires.

K = \mathrm{SHA\text{-}256}(\text{shared secret})[:16] \quad \text{for AES-128}

Practice

A DH shared secret is hashed with SHA-256, producing a 32-byte digest. The application needs only an AES-128 key (16 bytes) from it. How many bytes of the digest are discarded?

Why DH alone isn't enough: the man-in-the-middle problem

Plain Diffie-Hellman guarantees secrecy from a passive eavesdropper, but nothing about who's actually on the other end. An active attacker sitting between Alice and Bob can run two separate DH exchanges — one with each of them — and relay traffic through itself, decrypting and re-encrypting everything, while both Alice and Bob believe they're talking directly to each other.

This is exactly why real protocols never use bare DH: TLS combines the DH (or ECDH) exchange with a certificate-backed signature over the handshake transcript, and the Signal Protocol's X3DH verifies identity keys out of band — the key exchange handles secrecy, but authentication has to come from somewhere else entirely.

Man-in-the-middle against unauthenticated DH

1
Alice → "Bob"
Alice starts a DH exchange, but Mallory intercepts it and impersonates Bob.
2
Mallory → real Bob
Mallory starts a second, separate DH exchange with Bob, impersonating Alice.
3
Two independent shared secrets
Alice shares a secret with Mallory; Bob shares a different secret with Mallory. Neither shares one with the other.
4
Mallory relays and reads everything
Every message is decrypted, read (and optionally altered), and re-encrypted as it passes through — invisibly to both sides.

Go deeperParameter injection: an active attacker doesn't need to break the math⌄

An attacker positioned to rewrite messages in transit (not just read them) has a far cheaper option than solving a discrete logarithm: replace the public generator g itself with a degenerate value before either side uses it. Three substitutions each force the resulting shared secret to one of a tiny handful of possible values, regardless of how large and random Alice's and Bob's real secret exponents are.

The simplest: substitute g = 1. Then every public value A = 1ᵃ mod p and B = 1ᵇ mod p is just 1, and the final shared secret gᵃᵇ = 1ᵃᵇ mod p is always 1 — for every possible a and b. Alice and Bob each still compute something and believe the exchange succeeded, but the "secret" was never actually secret; it's a fixed public constant the attacker knew before the handshake even began.

g = 1 \;\Rightarrow\; A = B = 1 \;\Rightarrow\; \text{shared secret} = 1^{ab} \bmod p = 1 \ \text{(always)}

Practice

A MITM attacker rewrites the DH parameters in transit, substituting g = 1 for the real generator, over a prime p = 97. What will the resulting shared secret always equal, no matter what secret exponents Alice and Bob each pick?

Elliptic-curve Diffie-Hellman (ECDH)

The same idea maps onto elliptic curves: instead of modular exponentiation, parties combine points on a curve, using exactly the scalar multiplication (kG) and point addition covered in the ECC module. X25519 (ECDH over Curve25519) is the default key exchange in TLS 1.3 and in most modern SSH and messaging protocols, valued for speed and resistance to several classes of implementation error.

A = a \cdot G \qquad B = b \cdot G \qquad \text{shared secret} = a \cdot B = b \cdot A = ab \cdot G

Structurally identical to classical DH — modular exponentiation is simply replaced with elliptic-curve scalar multiplication.

Safe primes and small-subgroup attacks

The choice of p and g isn't arbitrary. If p is chosen carelessly, the group of values reachable by exponentiation can have small subgroups, and an attacker can sometimes force a DH exchange into one of those subgroups, drastically shrinking the search space for the discrete logarithm. Real implementations use "safe primes" (p where (p−1)/2 is also prime) specifically to avoid this, and validate that received public values aren't degenerate (like 0 or 1) before using them.

Go deeperLogjam: downgrading to export-grade parameters⌄

The 2015 Logjam attack targeted a different weakness: leftover "export-grade" DH cipher suites from 1990s-era US cryptography export restrictions, which capped key exchange parameters at a deliberately weak 512 bits. An active MITM attacker could rewrite the handshake's cipher-suite negotiation to force both a modern client and server down to this legacy 512-bit option, even though neither side actually wanted it.

Once forced down to 512 bits, the discrete logarithm problem becomes tractable — not instantly, but within reach of a well-resourced attacker who precomputes most of the work for one fixed, widely reused prime ahead of time, then finishes the specific discrete log for each intercepted connection in minutes. The lesson generalizes well beyond DH: a protocol that still offers a deliberately weak option, even one nobody chooses under normal conditions, gives an active attacker a downgrade lever — the fix was simply retiring export-grade cipher suites entirely, not trying to strengthen them.

Practice

Export-grade DH was capped at 512-bit primes. Modern deployments use 2048-bit primes as a minimum. Roughly how many times larger, in bits, is a modern DH prime compared to an export-grade one?

Go deeperSmall-subgroup confinement, worked by hand⌄

Here's the attack concretely. Take p = 23, so p−1 = 22 = 2×11. The element 22 (which is −1 mod 23) has order exactly 2, since 22² = 484 ≡ 1 (mod 23). If a malicious or compromised peer substitutes g = 22 in place of the real generator, then no matter what secret exponent b the victim picks — a huge, perfectly random 256-bit number — the result 22ᵇ mod 23 can only ever be 22 (if b is odd) or 1 (if b is even). The victim's secret is completely irrelevant; there are only two possible outputs, and an attacker checks both instantly.

This is exactly why real implementations validate the order of a received public value before using it, not just its range — a value that happens to generate only a tiny subgroup is just as dangerous as an out-of-range one, even though it looks like a perfectly ordinary number.

22 \equiv -1 \pmod{23}, \quad \mathrm{ord}(22) = 2 \quad\Rightarrow\quad 22^{b} \in \{1, 22\} \ \text{for every } b

Go deeperBreaking small discrete logs: brute force and baby-step giant-step⌄

The security of Diffie-Hellman rests entirely on the discrete logarithm problem being hard — but for small groups, it isn't hard at all. Worked example: with g = 5 and p = 23 (5 turns out to be a primitive root, generating all 22 non-zero values), find x such that 5ˣ ≡ 10 (mod 23). Just compute 5¹, 5², 5³, ... until one matches: 5¹=5, 5²=2, 5³=10 — found it, x = 3.

Brute force like this takes O(p) time — fine for p = 23, hopeless for a 2048-bit prime. Baby-step giant-step (BSGS) does much better, in O(√p) time, by splitting the exponent into two halves and meeting in the middle: precompute a table of gʲ for j = 0 to ⌈√p⌉, then repeatedly multiply the target h by g⁻ᵐ (for the same m = ⌈√p⌉) until the result lands in that table. The matching table entry and the number of giant steps taken combine into the full exponent. For g = 5, p = 97, h = 44, BSGS finds x = 58 — the same answer brute force would eventually reach, but touching roughly 2×√96 ≈ 20 values instead of up to 96.

x = i \cdot m + j \quad \text{where } g^{j} = h \cdot g^{-mi}, \quad m = \lceil \sqrt{p} \rceil

Practice

g = 5 is a primitive root mod p = 23. Find x such that 5ˣ ≡ 19 (mod 23), by brute-force computing powers of 5.

Forward secrecy

When DH parameters are generated fresh for each session (ephemeral Diffie-Hellman, denoted DHE or ECDHE), a compromise of a server's long-term private key doesn't let an attacker decrypt previously recorded sessions — each session's key existed only in memory and is gone once the connection ends. This property, forward secrecy, is now mandatory in TLS 1.3.

Static key exchange (no forward secrecy)

•The same long-term key pair is reused across many sessions
•If that private key is ever compromised, every past recorded session can be decrypted retroactively
•This is exactly the classical half of the harvest-now-decrypt-later risk

Ephemeral DH/ECDH (DHE/ECDHE)

•A fresh key pair is generated for every single session
•The session key exists only in memory and is discarded afterward
•Compromising a server's long-term identity key doesn't expose any past session's content