Algorithms Explained: Diffie-Hellman

By arriving here you’ve taken part in a Diffie-Hellman key exchange! (Or at least a variant). Diffie-Hellman is a way of establishing a shared secret between two endpoints (parties).

The mathematics behind this algorithm is actually quite simple. I’m going to explain what we’re trying to do first, then I’ll explain how we achieve it.

Let’s say Alice and Bob want to communicate with each other without John knowing what they’re saying or sending. Anything Alice sends to Bob, John will receive, likewise, anything Bob sends to Alice, John will also receive. So how do Alice and Bob send anything to each other without John understanding? Well that’s where Diffie-Hellman comes in.

I’m going to dive straight into the mathematics of it but this can be explained quite visually and you can test this out yourself with some paints at home.

To start, Alice and Bob decide publicly (John will also get a copy) on two prime numbers, g and n. Generally g is a small prime number and n is quite large, usually 2000 or more commonly 4000 bits long. So now Alice, Bob and John all know these numbers.

Now Alice decides secretly on another number, a. and Bob decides secretly on a number, b. Neither Alice nor Bob send these numbers, they are kept to themselves. Alice performs a calculation, g^a mod n, we’ll call this A, since it comes from a. Bob then performs g^b mod n which we’ll call B.

Alice sends Bob, A, and Bob sends Alice, B. Note John now has 4 numbers, A, B, g and n but not a or b. Finally, for the heart of the trick. Alice takes Bob’s B and performs B^a mod n. Similarly, Bob takes Alice’s A and performs A^b mod n. This results in the same number i.e. B^a mod n = A^b mod n. They now have a shared number. Notice how John can’t figure out what these numbers are from the numbers he’s got.

Actually he can and its given a name called solving the discrete log problem. If we make n very large this becomes an extremely computationally heavy problem to solve and simply isn’t worth the time to figure out. John would have to figure out a or b from A or B which is simply far too time consuming.

So what can Alice and Bob do with this key they’ve just created together? Well they can use it to start encrypting messages they send to each other. A very simple example that should not be used anywhere as it’s extremely insecure is in encrypting their messages with a shift cipher (Caesar cipher) where the shift value is determined by the newly generated key. Both Alice and Bob can encrypt and decrypt the messages as they know the shift value but John can’t as he doesn’t have the key.

Oh and if you do with to try this with paints, use a single colour instead of two for g and n and where ever calculations are performed just mix the paints.

If you were interested in this, check out www.pyler.io where we offer great online Python courses to take you from beginner in no time!

‘Slither into Python’ — Coming next month on Pyler.io