HOME | WRITEUPS | TOOLS | RESOURCES | TUTORIALS | ABOUT |
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:
Let's do this with some numbers.
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 (g^{a} mod p)^{b} mod p = g^{ab} mod p.
Bob calculated (g^{b} mod p)^{a} mod p = g^{ab} 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: 13^{a} modulus 37 = 24 or 13^{b} 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.
import math
for i in range(2,int(math.ceil(math.sqrt(137))):
if 137.0/i == math.floor(137.0/i):
print ('not prime')
exit
print ('prime')
count=0
z=0
while z != 1:
count += 1
z = pow (19, count, 137)
print (count)
A = pow (31, 9301, 137) # 55
B = pow (31, 7523, 137) # 6
key = pow ( 6, 9301, 137) # 51
key = pow (55, 7523, 137) # 51