Diffie–Hellman Key Exchange

Alice and Bob agree on a key over a public channel. The attacker sees every number they send. Then an attacker in the middle swaps the numbers, and nobody notices.

Public-key cryptographyKey exchangedemo

Objectives

Compute A, B and the shared secret K from p = 19, g = 2 and two secrets, and explain why both sides get the same K.
Read a secret from the table of 2^x mod 19, and explain why a table cannot work when p has 2048 bits.
Explain how an attacker in the middle gives Alice and Bob two different keys, and why the exchange needs authentication.

25%

Agree on a key over a public channel, then let an attacker read it, and then let an attacker change it.

A = g^a mod p B = g^b mod p K = B^a mod p = A^b mod p

A Diffie–Hellman exchange modulo 19

Example: p = 19 and g = 2. Alice chooses a secret a. Bob chooses a secret b. Only their public values A and B are sent. Each side computes the same shared secret K. The secret itself never crosses the network.

In the mixing-color picture, p and g are the public color, a and b are the private colors, A and B are the public mixtures, and K is the same final color. Mixing is easy. Separating the mixture, which means finding a from A, is the discrete logarithm problem.

Alice

Knows her secret a.

Alice's secret a

Computes A = g^a mod p = 2^11 mod 19 = 15, and sends A.

Receives B = 3 from Bob.

Computes K = B^a mod p = 3^11 mod 19 = 10

Public channel

Everything here is visible to the attacker.

Agreed in advance: p = 19, g = 2

Alice to Bob: A = 15 →

← Bob to Alice: B = 3

The attacker does not see a, b or K. Those three never leave Alice and Bob.

Bob

Knows his secret b.

Bob's secret b

Computes B = g^b mod p = 2^13 mod 19 = 3, and sends B.

Receives A = 15 from Alice.

Computes K = A^b mod p = 15^13 mod 19 = 10

why both sides get the same shared secret

B^a = (g^b)^a = g^(ab) = (g^a)^b = A^b both are 2^(11*13) = 2^143 = 2^(7*18+17) = 2^17 = 10 (mod 19) Fermat: 2^18 ≡ 1 (mod 19), so exponents can be reduced modulo 18.

Public values are printed in bold. Secret values sit in a filled chip. Both outer columns end with the same chip: K = 10. Move either slider. The two results change together and stay equal.

Why the small example is easy to break

A passive attacker (an eavesdropper) records p, g, A and B. The secrets a, b and K are never sent. To find K, it must compute g^(ab) mod p from g^a and g^b. This is the computational Diffie–Hellman (CDH) problem. If the attacker can solve discrete logarithms, it finds a and then K. Finding x from g^x mod p is the discrete logarithm problem. With p = 19 it is easy: the attacker lists every power of 2 and looks up A.

Every power of 2 modulo 19. The attacker looks up A = 15 and finds a = 11, and looks up B = 3 and finds b = 13.
x	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
2^x mod 19	2	4	8	16	13	7	14	9	18	17	15	11	3	6	12	5	10	1
attacker finds											↑ a		↑ b

A = 15 sits under x = 11, so a = 11. Searching from x = 1, that took 11 tries. B = 3 sits under x = 13, so b = 13. Now the attacker computes K = B^a mod p = 3^11 mod 19 = 10, the same key as Alice and Bob.

A table is practical here because the group has only 18 elements. Every value from 1 to 18 appears exactly once in the second row, so the lookup always gives one answer: g = 2 generates the whole group.

The attacker in the middle (MITM)

Plain Diffie–Hellman does not say who sent A or B. An active attacker between Alice and Bob replaces both values with its own M = g^m mod p. Alice thinks M came from Bob. Bob thinks M came from Alice.

The attacker sits in the middle and swaps the values

The attacker's secret m

Alice

Secret a = 11.

Sends A = 15.

Receives 16 and believes it is B from Bob.

Computes K = 16^11 mod 19 = 9

The attacker in the middle

Secret m = 4.

Keeps A = 15. Sends M = 2^4 mod 19 = 16 to Bob.

Keeps B = 3. Sends M = 16 to Alice.

Key with Alice: A^m = 15^4 mod 19 = 9

Key with Bob: B^m = 3^4 mod 19 = 5

Bob

Secret b = 13.

Sends B = 3.

Receives 16 and believes it is A from Alice.

Computes K = 16^13 mod 19 = 5

result

Alice holds 9. Bob holds 5. The two keys are different, and the attacker knows both of them.

Alice and Bob each share a secret with the attacker. The attacker can derive both session keys and read or change their messages. Both exchanges succeed, but neither peer's identity has been checked: Alice expected some number from 1 to 18, and she got one. A bare number does not say who sent it.

The fix is to sign the exchange with a key the other side trusts. In TLS 1.3 the server signs a transcript hash that covers both key shares (the CertificateVerify message), and the client checks the certificate for the expected server name. Replacing a key share changes the signed transcript, so verification fails. SSH signs with a trusted host key in the same way.

Prime size is not security strength

The table has one row for every x, so it has about as many rows as p. Each extra bit in p doubles the table. Move the slider.

size of p, in bits

rows in the table

about 2^32 = 4,294,967,296

storage, at 8 bytes per row (x and g^x)

about 34 GB

A 5-bit p, like 19, gives a table you can write on one line. A 64-bit p already needs hundreds of exabytes. Real Diffie–Hellman uses a p of 2048 bits or more.

Group sizes in use, the number of rows a table would need, and the security strength NIST SP 800-57 Part 1 Rev. 5 assigns to each.
Group	Table rows	Security strength
Diffie–Hellman, 2048-bit p	2^2048	112 bits
Diffie–Hellman, 3072-bit p	2^3072	128 bits
Elliptic curve, 256-bit group (for example P-256)	2^256	128 bits

A security strength of s bits means that the best known attack needs about 2^s operations. Prime size is not security strength: for a 2048-bit prime, the attacker does not check all 2^2048 rows. The number field sieve is faster than table lookup, but still far out of reach at these sizes. With suitable subgroup sizes, NIST estimates 112-bit security for 2048-bit primes and 128-bit security for 3072-bit primes (SP 800-57 Part 1 Rev. 5, Table 2). Nothing on this page measures them.

The last row is the reason for the next two pages. Finite-field DH faces special attacks such as the number field sieve; no comparable classical shortcut is known for well-chosen curves. At about 128-bit security, ffdhe3072 sends a 384-byte public value, ECDH on P-256 sends 65 bytes (33 compressed), and X25519 sends 32 bytes.

step 1/4

CPE 645 / CS 685

Diffie–Hellman Key Exchange

Mine a SHA3-256 Digest

Adding Points on an Elliptic Curve