Diffie-Hellman Key Exchange
The Diffie-Hellmen Key Exchange is a method of generating a shared secret (for a key) such that the secret can't been seen by someone snooping on the communication. It's good for use on unencrypted channels, to create a key to use for encryption.
This key exchange is extremely secure when used correctly and is an example of perfect forward security. Someone else seeing the key exchange will have no way to break in because the key is never communicated!
On to the algorithm. Let's say Alice and Bob want to create a key to encrypt further communications with. They will use the Diffie-Hellman Key Exchange:
- Alice decides two shared prime numbers, a base, g and a modulus, p. Alice sends these numbers to Bob.
The base, g, must be a primitive root modulo p. Note that since p is prime, this simply means that the first p-1 powers of g modulus p are the numbers 1 to p-1, in any order.
- Alice decides a secret number a. Alice computes A = ga modulus p. Alice sends A to Bob.
- Bob has a secret number b. Bob computes B = gb modulus p. Bob sends B to Alice.
- Alice takes B and finds the key by doing Ba modulus p.
- Bob takes A and finds the key by doing Ab modulus p. This will be the same number Alice found.
- Now both Alice and Bob know the key, and they can use it to encrypt!
Let's do this with some numbers.
- The two shared prime numbers are g=13 and p=37. Note that the base 13 is a primitive root modulus 37, since the first 36 powers of 13, modulus 37 are the numbers 1 to 36 out of order.
- Alice's secret number is 19. Alice computes A = 1319 modulus 37 = 24. Alice sends 24 to Bob.
- Bob's secret number is 93. Bob computes B = 1393 modulus 37 = 23. Bob sends 23 to Alice.
- Alice takes 23 and finds the key by doing 2319 modulus 37 = 14.
- Bob takes 24 and finds the key by doing 2493 modulus 37 = 14.
Why does this work? How can Alice and Bob both get the same number without know the other's secret number? Well, they both calculated the same number in a different order.
Alice calculated (ga mod p)b mod p = gab mod p.
Bob calculated (gb mod p)a mod p = gab mod p.
You might still be wondering how this is secure. The prime numbers g and p, and the calculated numbers A and B are visible to anyone who is watching the unencrypted communications! Even with all these numbers, if large primes and secret numbers are chosen, you will need to know either a or b to get the key.
This is because doing the function of a power then a modulus only goes one way. It's easy enough to calculate A or B, but getting the secret number back is difficult enough to be secure. Even with both g and p, a brute force would be needed to attempt to get the secret number back (so choose a large number!).
Let's look at our previous example.
We have g=13, p=37, A=24, B=93. To find a or b, we would need to solve one of these equations: 13a modulus 37 = 24 or 13b modulus 37 = 23.
In this example, we used very small numbers. We could test each value of a, starting at 1 and incrementing until we get the number. Since a=19 and b=93, you can calculate them both extremely quickly. Additionally, using such a low modulus means there are only 37 possible keys, which can be brute forced as well.
Clearly, with such small numbers, Diffie-Hellman isn't safe from a brute force. That's why it is best practice to choose 2048 bit primes (1400 decimal digits), and unique primes for each exchange.
Let's do a programming example, to see how we could use code to implement this efficiently. In this example, we will be using Python, but there are equivalent functions in other languages.
- First, let's choose a prime for the modulus. Let's keep it small, but big enough to be unrealistic to do by hand: p=137.
To check if this is prime, we can use the following code:
The code shows that 137 is prime by checking if it is divisible by any of the numbers until its square root. Since it isn't we can continue.
for i in range(2,int(math.ceil(math.sqrt(137))):
if 137.0/i == math.floor(137.0/i):
print ('not prime')
Next, we need to choose a prime for the base. It needs to be a primitive root modulo 137.
What we need to do is choose a random prime and loop through its first 137 powers. Let's take a random prime, say g=19, and test it:
What this is doing is going through the powers of 19 modulus 137 until the power is 1. When this happens, the powers will loop (note than the 0th power of anything is 1).
while z != 1:
count += 1
z = pow (19, count, 137)
When the power is 1, the powers will repeat. If the value of count isn't 136 at the end (137-1) then it didn't go through all the numbers, and some are left out.
Note the syntax of the pow() command. It does 19 to the power of count, and additionally modulus 137.
The program outputs 68, meaning it only went through 68 numbers, not all 136. We will need to try a new number, g=31. Running it through the program is successful, and it can be our value for the base. (We would also need to test if it is prime, but since it's so low, we don't have to).
Let's set a = 9301 and b = 7523. These are the secret numbers and aren't transmitted anywhere.
To calculate A and B, we can use that same pow() command as before. The syntax is pow(base, power, modulus):
A = pow (31, 9301, 137) # 55
NOTE: The text after the # is ignored because it is a comment.
B = pow (31, 7523, 137) # 6
- Now that we have A and B, those numbers would be transmitted.
- We now need to do Ba and Ab, both modulus 137.
key = pow ( 6, 9301, 137) # 51
key = pow (55, 7523, 137) # 51
- Now we have the key! Although these numbers were really low, it went through all the necessary precautions, checking if the numbers are prime, and the base is a primitive root, and calculating A, B, and the key easily!