The Magic of Diffie-Hellman: How to securely exchange secrets

The need for secure encryption

When computer networking first came around in the 1960s, researchers quickly realized its massive potential. This technology would allow people located in different geographical locations to exchange real-time information. The world as they saw it, was about to turn on its head.

This idea of being “online” was quickly adapted and advanced by universities in the following years. With the advancement, however, also arose the need for establishing secure communication channels. Money transfers were only one of the growing number of applications that required messages to be encrypted. And as the internet grew to encompass millions across the world, a new problem emerged:

The answer was found in colors!

Yes, you read that right! The idea was simple:

When Whitfield Diffie and Martin Hellman applied this concept to encryption, it led to the development of one of the world’s first public key exchange protocols.

Diffie-Hellman Key Exchange

• First, Alice (sender) and Bob (receiver) agree upon a common public color, say, Yellow🟡

• Then, both of them also choose a secret color that they keep to themselves. Say, Alice: Red 🔴 Bob: Blue 🔵

• Then, they mix their private colors with the public color, to get new colors Alice new: 🔴 + 🟡 = 🟠 (orange) Bob new: 🔵 + 🟡 = 🟢 (green)

• Both Alice and Bob then share these new colors publically with the other person

This is where the magic begins! 

• Alice and Bob now mix the new color they received from each other, with their own private color. This results in an identical final color for both of themAlice: 🔴 + 🟢 = 🟤 (brown) Bob: 🔵 + 🟠 = 🟤 (brown)

Tadaa!

By simply exchanging mixed colors, Alice and Bob are able to get a shared secret color. Any outsider would only be able to see the common color, Yellow(🟡), and the shared mixed colors Orange(🟠) and Green(🟢).

Using just this information, it will be practically impossible for them to get to Brown(🟤)

This is the principle behind the Diffie-Hellman public key exchange. Using the secretly generated key (🟤), users can exchange secret messages over a public network.

The Maths Behind DH Key Exchange, a.k.a, nerd stuff

The Diffie-Hellman algorithm is based on the mathematical properties of modular arithmetic.

A mod B ≡ R

Here’s a quick refresher of mod arithmetic:

1. First, Alice and Bob choose a prime modulus P, say 17

2. Then they find a number g (also called generator) such that different exponential powers of g generate uniform cyclic solutions. For example, if we take g = 3,This equation is equally likely to generate any of the 17 integers. But the reverse of this procedure is extremely hard! That is, given the following statement, it is difficult to find out the value of N. If we use a very large prime modulus (P) instead of 17, it could take years even for supercomputers to find the right solution.Now, this is how the trick works: 

3. Both Alice and Bob choose their private keys, say 15 and 13, and calculate their mods as shown below. Then, they share the results, 6 and 12, publically with each other.Alice:Bob:

4. Now, both of them take the result received from the other person and raise it to the power of their secret number:Alice: Bob:

And they magically get the same secret number! How did this happen?

Both Alice and Bob basically did the same calculation. For Alice, the key received was:

So her final calculation was:

Similarly for Bob, the key he received was:

So his final calculation was:

Flipping the powers doesn't make any difference. So Bob and Alice did the same exact calculation to find their secret key.

Diffie-Hellman is a fundamental building block of many cryptographic protocols, such as the Transport Layer Security (TLS) protocol used to secure HTTPS connections. It's a relatively simple algorithm that is easy to implement and understand, but it is also very secure.