Introduction

Diffie-Hellman Key Exchange (DH) is a method to generate a shared secret between two people in such a way that the secret cannot be seen by anyone observing the transfer. DH makes use of a trapdoor function, which is usually seen in public-key cryptography.

The idea is to use this technique to generate a key together and then encrypt your traffic using this key. If someone were to record the traffic and analyze it, they would not be able to figure out what the key is even though the exchanges are done publicly. This is Forward Secrecy in a nutshell - nobody, at a later date, can decrypt the data that they have recorded since the generated key was never saved or transmitted.

Understanding the algorithm (without the math)

Let's take a closer look at the algorithm with the help of an analogy to help visualize it.

We will be referring to the below picture for the explaination.

Consider two people - Alice and Bob.

• Alice and Bob decide on a common color Yellow
• Alice also chooses her secret color - Orange while Bob chooses his secret color - Green
• Now, we'll mix the common color (Yellow) with the individually chosen secret colors. This will lead to Amber in Alice's case and Blue in Bob's case.
• The newly mixed colors (Amber and Blue) will now be exchanged between Alice and Bob.
• When Alice mixes her secret color (Orange) with the color she received from Bob (Blue) she'll get Brown as the result.
• Similarly, when Bob mixes his secret color (Green) with the color he received from Alice (Amber) he'll get Brown as the result as well!

So, did you notice how we started off with a common color, mixed it with secret colors, and still ended up with the same color?

Keep in mind that, if someone tried to mix any other color with Amber OR with Blue, they wouldn't end up with Brown as the result!

That is the beauty of the Diffie-Hellman exchange. The parties communicating are the only ones who are able to generate the common secret using their individual secrets. Of course, there's a lot of math involved behind the scenes, but this algorithm is used widely in many protocols that we use on a daily basis including TLS!

The Algorithm

DH is based on modular arithmetic and is essentially a one-way function. In the sense, it is not computationally expensive to carry out this function, but it is computationally infeasible to perform the reverse of the function to figure the keys out.

Let's take a closer look at the actual algorithm without diving too deep into modular arithmetic concepts.

Consider the same two people - Alice and Bob

Alice wishes to communicate with Bob and she wants their messages to be encrypted using an algorithm such as AES. Unfortunately, since AES is a symmetric encryption algorithm, they need a common secret key to encrypt and decrypt their messages - this is where DH comes to the rescue!

• Alice and Bob mutually agree between them a large prime number p and a generator (base number) g such that g is the primitive root modulo of p

Let's say p = 23 and g = 5 (which is a primitive root modulo of 23 )

• Alice then chooses a secret integer 'a' (her private key) and calculates A = g^a mod p (which gives us her public key)

Let's say a = 2 and A = 5² mod 23 = 2

• Bob does the same and calculates his public key using his secret integer b using g^b mod p (which gives us his public key)

Let's say b = 5 and B = 5⁵ mod 23 = 20

• Alice and Bob exchange their new values A (2) and B (20)

• Now, Alice calculates her shared secret 'S' using S = B^a mod p

So, S = 20² mod 23 = 9

• Bob calculates his shared secret 'S' using S = A^b mod p

So, S = 2⁵ mod 23 = 9

Alice and Bob now share a common secret S = 9

It must be pretty obvious now that the only thing kept secret is 'a' and 'b'. All the other values - p, g, A and B can be made public.

In a real-world scenario, you would have a really large prime number which would make it computationally infeasible to figure the secret 'a' with just p, g, and A.

This basically sums up a discrete logarithm problem - it is easy to compute the functions but very hard to invert them!

Conclusion

Diffie-Hellman Key Exchange is a very fascinating method to share a secret over a public communication medium. While it sounds extremely cool, it does have certain issues such as the fact that it is unauthenticated - there is no way for Alice to know that she is actually communicating with Bob and not with someone, say Joe, who is pretending to be Bob.

This is the gist of something called a man-in-the-middle attack (MITM). I would love to go deeper into MITM someday, so definitely let me know if you'd like to read more about it!