Diffie-Hellman Key Exchange

The question of key exchange was one of the first problems addressed by a cryptographic protocol. This was prior to the invention of public key cryptography.

The Diffie-Hellman key agreement protocol (1976) was the first practical method for establishing a shared secret over an unsecured communication channel. The point is to agree on a key that two parties can use for a symmetric encryption, in such a way that an eavesdropper cannot obtain the key.

Diffie-Hellman Algorithm

Steps in the algorithm:

Diffie-Hellman Algorithm

Alice and Bob agree on a prime number p and a base g.
Alice chooses a secret number a, and sends Bob (ga mod p).
Bob chooses a secret number b, and sends Alice (gb mod p).


Alice computes ((gb mod p)a mod p).
Bob computes ((ga mod p)b mod p).
Both Alice and Bob can use this number as their key. Notice that
p and g need not be protected.

Diffie-Hellman Example

Alice and Bob agree on p = 23 and g = 5.
2 Alice chooses a = 6 and sends 56 mod 23 = 8.
3 Bob chooses b = 15 and sends 515 mod 23 = 19.
4 Alice computes 196 mod 23 = 2.
5 Bob computes 815 mod 23 = 2.
Then 2 is the shared secret.
Clearly, much larger values of a, b, and p are required. An
eavesdropper cannot discover this value even if she knows p and g
and can obtain each of the messages.

Diffie-Hellman Security

Suppose p is a prime of around 300 digits, and a and b at least
100 digits each. Discovering the shared secret given g, p, ga mod p and gb mod p would take longer than the lifetime of the universe, using the best known algorithm. This is called the discrete logarithm problem.