Introduction to Diffie Hellman Key Exchange Algorithm

by Himanshu Arora on January 31, 2013

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.


Linux Sysadmin Course Linux provides several powerful administrative tools and utilities which will help you to manage your systems effectively. If you don’t know what these tools are and how to use them, you could be spending lot of time trying to perform even the basic administrative tasks. The focus of this course is to help you understand system administration tools, which will help you to become an effective Linux system administrator.
Get the Linux Sysadmin Course Now!

If you enjoyed this article, you might also like..

  1. 50 Linux Sysadmin Tutorials
  2. 50 Most Frequently Used Linux Commands (With Examples)
  3. Top 25 Best Linux Performance Monitoring and Debugging Tools
  4. Mommy, I found it! – 15 Practical Linux Find Command Examples
  5. Linux 101 Hacks 2nd Edition eBook Linux 101 Hacks Book

Bash 101 Hacks Book Sed and Awk 101 Hacks Book Nagios Core 3 Book Vim 101 Hacks Book

{ 9 comments… read them below or add one }

1 Bert vd Horst January 31, 2013 at 2:22 am

Now I understand, thanks.
Can you also tell how large (scope) are the random numbers g and x approximately?

2 Rob January 31, 2013 at 10:16 am

Correction – Diffie-Hellman Key Exchange is used for Symmetric Encryption, not Asymmetric. Asymmetric uses private/public keys that are generated by each user.

3 Jalal Hajigholamali January 31, 2013 at 2:12 pm

Hi,
useful article…
thanks

4 Sashika February 1, 2013 at 4:12 am

Excellent explanation..
thank you

5 Mustapha Oldache February 10, 2013 at 11:57 am

Hi,

Very interesting..

thanks

6 kevin giacobbe March 17, 2013 at 1:38 pm

i have always been curious about how secure
rest. until the next mystery. ok cool. thx..
rest. until the next mystery. ok cool. thx..

7 kevin giacobbe March 17, 2013 at 1:42 pm

i have always been curious about how secure information exchange is initiated.
now i can let my imagination rest. until the next mystery.
ok cool. thx.

8 Greg G May 8, 2013 at 1:58 pm

Bert,

The scope of p and g are very different. “g” is a very small prime, usually 2 or 5. If I remember correctly, “p” is typically a massive prime number, at least 768 bits in length.

9 saranya September 25, 2013 at 4:28 am

i want diffie hellman key exchange algorithm in immediatly in this time

Leave a Comment

Previous post:

Next post: