Diffie-Hellman Key Exchange 🔑 ↔ 🔑

4 min readAug 11, 2020

The Problem

Alice and Bob want to encrypt their messages using symmetric key encryption. This is where Alice and Bob use the same cryptographic key to encrypt the messages they send and decrypt the messages they receive.

There’s just one small problem — how do they determine what key to use in a secure way?

The Big Picture

Diffie-Hellman key exchange is a way that two or more people can arrive at the same cryptographic key in a secure way. It may help to think of it as a negotiation rather than an exchange — the parties involved never exchange the shared cryptographic key itself, but instead follow a certain protocol in order to arrive at it (note that the protocol does involve exchanging other information).

The general idea behind Diffie-Hellman is that Alice and Bob each start with a publicly known common color and a secret color. They can then arrive at a shared secret color by exchanging mixed colors.

Let’s go over the steps in more detail. First, Alice mixes the common color with her secret color and sends the resulting mixed color to Bob. Bob does the same. This means that an attacker has access to the common color and both mixed colors. However, since we assume colors are hard to unmix, attackers cannot deduce the secret colors or the shared secret color.

Finally, Alice mixes the mixed color she receives from Bob with her own secret color. Bob does the same. This results in the same shared secret color. If we replace the colors with numbers, this method can be used to securely arrive at a shared cryptographic key.

Some Maths Background

The colors explanation is not how Diffie-Hellman key exchange actually works. We need to replace the colors with numbers and the color mixing with formulas. But before we do that, let’s review some maths that will make understanding that part easier.

Primitive root modulo nA number g is a primitive root modulo n if, for every integer a coprime with n, there is an integer k such that gᴷ ≡ a mod n. For example, 2 is a primitive root modulo 3.
2² = 4 ≡ 1 mod 3
2¹ = 2 ≡ 2 mod 3
Note: if n is prime, then there must be such a k for each a in the range 1 ≤ a < n (since all those numbers are coprime with n)

The modulo operation is distributive
This means that
ab mod n = [(a mod n)(b mod n)] mod nand

(a mod n)ᵇ mod n = 
[(a mod n)…(a mod n)] mod n = 
aᵇ mod n

Note: here’s a proof.

The Real Thing

Note: public values are blue, secret values are red.

Why Does This Work?

The are three main things you need to understand.

First, you need to understand why
Bᵃ mod p = Aᵇ mod p
This is why Alice and Bob arrive at the same number, the same shared secret. So, let’s break it down.
(gᵇ mod p)ᵃ mod p = (gᵃ mod p)ᵇ mod p
Since the modulo operation is distributive, this becomes:
gᵇᵃ mod p = gᵃᵇ mod p
Since gᵇᵃ = gᵃᵇ, it’s clear these are equal.

Second, you need to understand why it’s important that p is prime, and that g is a primitive root modulo p. Notice that the shared secret is of the form gᵃᵇ mod p. If you recall the definition of a primitive root modulo p, this means the shared secret can be any number between 1 and p-1. In other words, this gives us a large range of potential values for the shared secret (as long as p is large), which is good for security.

Lastly, you need to understand that in reality, p would be much larger (i.e. hundreds of digits long). In our silly example, where p = 23, there are only 22 possible shared secret values, so it would be easy to brute force the solution. If p is large, it would take forever to randomly guess the shared secret (since there are so many possibilities), and it is also very hard to solve for a given only g, p, and gᵃ mod p (this is called the discrete logarithm problem).

How to Choose Good Numbers

Above, I mentioned that p should be large to make Diffie-Hellman secure. In practice, how is p chosen? For that matter, how are g, a, and b chosen?

p and g are usually chosen by taking some values from this RFC. These values have been vetted for security. If you choose the wrong values, then you may have security vulnerabilities, or efficiency problems, or both. This post talks a bit more about this.

The original paper says this about choosing a and b: