CPSC 110-08: Computing on Mobile Phones
Spring 2012
Diffie-Hellman Key Exchange

The Key Exchange Problem

Alice and Bob want to conduct a secure, encrypted bank transaction over the Internet, but it's very likely that Eve will be eavesdropping by sniffing the packets sent between Alice and Bob. How can Alice and Bob create a shared key that will allow them to encrypt their messages without Eve discovering it.

The Diffie Hellman Key Exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared key over an insecure communication channel.

One Way Function

The security of Diffie-Hellman is based on what's known as a one-way function, a function that is simple to compute in one direction but very difficult to compute in the other direction.

A nice analogy of a one-way function would be the process of mixing paints. Mixing two paint colors together is easy. Unmixing them is just about impossible.

Here is a nice video that uses the color mixing analogy to illustrate the concept of a one-way function and then explains the mathematics behind Diffie Hellman: Click to Watch!

The Diffie-Hellman Key Exchange Demo

The Demo follows the method described in the video. Here's how it works:

  1. Choose a random color to serve as the public seed, known to Alice, Bob, and Eve. (The Button labels provide the RGB values.)
  2. Alice and Bob both choose random colors to server as their private keys. Only they know their private keys.
  3. Alice and Bob mix their private keys with the public seed to create their public keys, known to Alice, Bob, and Eve.
  4. To create a shared secret key Alice and Bob mix their respective private keys with the other person's public key.
  5. Test the key by creating a secret message, encrypted by Alice and decrypted by Bob using their shared secret key.
ScreenshotQR Code
qrcode

Android Package: DiffieHellmanColor.apk
App Inventor Source Code: DiffieHellmanColor.zip

Credits

Thanks to the team a Art of the Problem for the terrific Diffie-Hellman video and thanks to Jeff Gray at the University of Alabama for pointing us to it.