Introduction to Diffie Hellman Key Exchange Algorithm

Asymmetric Encryption of data requires transfer of cryptographic private key. The most challenging part in this type of encryption is the transfer of the encryption key from sender to receiver without anyone intercepting this key in between. This transfer or rather generation on same cryptographic keys at both sides secretively was made possible by the Diffie-Hellman algorithm.

The Diffie-Hellman algorithm was developed by Whitfield Diffie and Martin Hellman in 1976. This algorithm was devices not to encrypt the data but to generate same private cryptographic key at both ends so that there is no need to transfer this key from one communication end to another. Though this algorithm is a bit slow but it is the sheer power of this algorithm that makes it so popular in encryption key generation.

For more information on cryptography, read our earlier tutorial on cryptography basics.

The Diffie-Hellman algorithm

This algorithm uses arithmetic modulus as the basis of its calculation. Suppose Alice and Bob follow this key exchange procedure with Eve acting as a man in middle interceptor (or the bad guy).

Here are the calculation steps followed in this algorithm that make sure that eve never gets to know the final keys through which actual encryption of data takes place.

• First, both Alice and Bob agree upon a prime number and another number that has no factor in common. Lets call the prime number as p and the other number as g. Note that g is also known as the generator and p is known as prime modulus.
• Now, since eve is sitting in between and listening to this communication so eve also gets to know p and g.
• Now, the modulus arithmetic says that r = (g to the power x) mod p. So r will always produce an integer between 0 and p.

• The first trick here is that given x (with g and p known) , its very easy to find r. But given r (with g and p known) its difficult to deduce x.
• One may argue that this is not that difficult to crack but what if the value of p is a very huge prime number? Well, if this is the case then deducing x (if r is given) becomes almost next to impossible as it would take thousands of years to crack this even with supercomputers.
• This is also called the discrete logarithmic problem.
• Coming back to the communication, all the three Bob, Alice and eve now know g and p.
• Now, Alice selects a random private number xa and calculates (g to the power xa) mod p  = ra.  This resultant ra is sent on the communication channel to Bob. Intercepting in between, eve also comes to know ra.
• Similarly Bob selects his own random private number xb, calculates (g to the power xb) mod p  = rb and sends this rb to Alice through the same communication channel. Obviously eve also comes to know about rb.
• So eve now has information about g, p, ra and rb.
• Now comes the heart of this algorithm. Alice calculates (rb to the power xa) mod p = Final key which is equivalent to (g to the power (xa*xb) ) mod p .
• Similarly Bob calculates (ra to the power xb) mod p  = Final key which is again equivalent to (g to the power(xb * xa)) mod p.
• So both Alice and Bob were able to calculate a common Final key without sharing each others private random number and eve sitting in between will not be able to determine the Final key as the private numbers were never transferred.

As explained above the Diffie-Hellman algorithm works perfectly to generate cryptographic keys which are used to encrypt the data being communicated over a public channel.