≡ Menu

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.

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

{ 11 comments… add one }

  • Bert vd Horst January 31, 2013, 2:22 am

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

  • Rob January 31, 2013, 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.

  • Jalal Hajigholamali January 31, 2013, 2:12 pm

    Hi,
    useful article…
    thanks

  • Sashika February 1, 2013, 4:12 am

    Excellent explanation..
    thank you

  • Mustapha Oldache February 10, 2013, 11:57 am

    Hi,

    Very interesting..

    thanks

  • kevin giacobbe March 17, 2013, 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..

  • kevin giacobbe March 17, 2013, 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.

  • Greg G May 8, 2013, 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.

  • saranya September 25, 2013, 4:28 am

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

  • malathi.k October 30, 2014, 12:30 am

    i want immediatly about the diffe hellman key algorithm for vanet

  • Rajiv Kumar July 16, 2015, 8:21 am

    Can anyone tell how both firewall peers agree upon a prime number and another number that has no factor in common. Do they send it to each other or how? if they will send then eve can grab it. How does it happen in DH key exchange?

Leave a Comment