An Interactive Applet powered by Sage and MathJax.
(By Alyssa Vorpahl and Prof. Gregory V. Bard)
This page is intended to showcase the Diffie-Hellman Key Exchange protocol.
Suppose Alice and Bob wish to be able to send messages to each other securely, but they know there is a possibility that their communication will be monitored. (For example, perhaps one of them is traveling in a country that monitors all international internet traffic.) One option is to use public-key cryptography. That's too mathematically intensive (and therefore very slow) for exchanging large, or even medium-sized, amounts of data. As you might know, public-key cryptography is often used to exchange a secret key (a shared secret) that can be used with a block cipher for bulk encryption. A competing idea is to use the Diffie-Hellman Key Exchange algorithm to exchange a shared secret, such as a secret key for use with a block cipher. The Diffie-Hellman Key Exchange is much simpler and faster, and is widely used on the internet.
To use Diffie-Hellman, they will select a large prime number p, and a number g that generates the integers modulo p (Zp). Note, they can discuss the g and p values openly without loss of security. There is also a version of the Diffie-Hellman Key Exchange protocol that uses elliptic curves as the group instead of the integers mod p. Nonetheless, it is best to learn the algorithm using the integers mod p first, before moving on to more esoteric groups.
Once they agreed upon shared g and p values, they can follow these steps to create a shared secret key:
| Alice | Bob |
|---|---|
| Chooses random x, 1<x<p-1 | Chooses random y, 1<y<p-1 |
| Computes gx mod p | Computes gy mod p |
| Sends gx to Bob | Sends gy to Alice |
| Receives gy | Receives gx |
| Computes (gy)x = k mod p | Computes (gx)y = k mod p |
If all has been done correctly, then they should both have the same number gxy at the end. Sometimes this will serve as the shared secret, or sometimes it will be put into a hash function and the digest will become their shared secret key. The latter is somewhat more secure, but it requires additional computations (and therefore time). They can then use this key to encrypt any further communication using a block cipher. Anyone monitoring their communication will not be able to decrypt it without solving a discrete logarithm problem, which is something we will discuss later.
When you load the applet, there will be four sliders: one to control the generator 'g', one to control the modulus 'p', and two for Alice and Bob to choose their random values 'x' and 'y' respectively.
Once it verifies that all of the initial conditions are met (i.e. p is prime, g generates Zp), it calculates the steps of the Diffie-Hellman key exchange and displays each of those steps.