The Diffie Hellman Key Exchange (1976)

Whitfield Diffie and Martin Hellman discovered a method of encryption that allows communication on open airways using a key that is not known by all parties. The vital part is the mathematics which allows the end users to create a common key using a procedure that is conducted without encryption.

The Setup

Ana, Bob, and Eve are our three actors. Ana and Bob want to communicate and Eve would like to listen in. (These are three common names chosen for encryption scenarios, possibly because of their simplicity and similarity to A, B, and E for eavesdropper.) Click on the box to the right to see an animation.

What people know

Everyone knows the public base, a, and the public prime, p. The public base is the number used as the base of the exponent. The public prime is the number used in the modulo operation (which gives the remainder after division by that particular number).

However, only Ana knows what number, x, she is going to raise the base by, and only Bob knows what number, y, he is going to raise the base by.

Creating the Common Key

In this example we will use the number 2 as the public base, or number we will raise to various powers. We will use 11 as the public prime, or number that we will use as our modulo.

Ana chooses a prime number which only she knows, and which will act as the number she raises the public base to. Bob also chooses a prime number which only he will know.

The Common Key Part II

Now Ana and Bob each take the public base and raise it to the prime numbers they each chose. They send the remainder to each other after taking the modulo.

The Common Key Part III

Ana and Bob each raise the number they received from each other--big X and big Y--by their own private primes they chose initially. Here is the beautiful result: they each have a copy of the common key which only they know. Everything was passed publicly except for the primes they each chose. Now they are able to communicate privately.

This page is based on a lecture by Oliver Knill, Harvard University, on 16 April, 2012.

References:     Lecture Handout     Lecture Worksheet