The Magic of Diffie-Hellman: How to securely exchange secrets
The first-ever public key encryption algorithm was based on the simple concept of mixing two colors
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:
At the time, digital encryption worked on a simple logic - The sender could lock the message with a key, and share that key with the receiver. But how could two people in different parts of the world agree on a secret shared key?
The answer was found in colors!
Yes, you read that right! The idea was simple:
It is very easy to mix 2 colors to produce a new color. But given a mixed color, it is tough to reverse it to get the original colors
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 them
Alice: 🔴 + 🟢 = 🟤 (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:
First, Alice and Bob choose a prime modulus P, say 17
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,
\(3ᴺ mod 17 = {0, 1, 2, 3, ..., 16} \)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.
\(3ᴺ mod 17 = 12\)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:
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:
\(3¹⁵mod 17 = 6 \)Bob:
\(3¹³ mod 17 = 12 \)Now, both of them take the result received from the other person and raise it to the power of their secret number:
Alice:
\(12¹⁵ mod 17 = 10 \)Bob:
\(6¹³ mod 17 = 10 \)
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.
Without access to the private numbers 13 and 15, any observing outsider will not be able to find out the shared key. And this is the magic behind the Diffie-Hellman public key exchange algorithm!
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.
Dear friend, Your site is awesome but I found a small mistake. I think that 3^n (3 raised to the power of n) can never be 0 (mod 17).