In early 70’s to send a secret message, both parties (sender and receiver) have to exchange the key to encrypt and decrypt the message. Exchange secret key may lead to compromising the security, as while exchange this key if someone intercepted secret key then the interceptor can decrypt all messages. This problem is called the key exchange problem in computer science 

The key exchange problem is not just limited to communication but also arises in network communication. To solved key exchange problems Whitfield Diffie and Martin Hellman presented Diffie Hellman Key Exchange algorithm in 1976. 

Diffie Hellman Key Exchange provides a way of generating a shared key between two users in a way that communication does not reveal the secret key over a public network and some time the shared key also used for encrypting and decrypting the communication.

The Diffie Hellman key exchange works like mixing color by exchanging key colors.

Let’s assume we have a color, we can create a new color by adding another color to it. Now when a new color is ready it is not possible to identify the original color i.e. reverse operation is not possible.

A similar example is taken to visualize Diffie Hellman Key Exchange algorithm

Let’s say we have two users Alice and Bob, 

• They both agree to use random color which is known to everyone (e.g. yellow).
• They both have selected a private (secret for them) color for themselves (red and sea-green)
• Before sharing a color, both mixed their private color with public color. i.e. Alice mixed yellow color in red and Bob mixed sea green color in yellow.
• Both exchange new colors with each other.
• To make sure exchange identity, both mixed their private color in the new color which they received.
• After mixing private color both will have identical color as final color, which identifies the exchange of color is successful (securely exchange the keys).
•  If a third person have intercepted the color exchange, it would be difficult to determine the secret color

Diffie Hellman Key Exchange is based on a similar concept, it uses mathematics instead of color mixing

The math behind the Diffie Hellman Key Exchange.

Diffie Hellman uses modular exponentiation is also known as repeated sequence algorithm.

So, why we need modular exponentiation? 

Typically to perform large number modulus calculation, uses modular exponentiation for more information like how it works? refer to this link.

Modern crypto algorithms work with at least 128-bit long keys to perform such large operation we need modular exponentiation.

Diffie Hellman uses two number’s 

1. Prime number 

2. The primitive root of the prime number

Let’s consider that there is a huge prime number, known to all participants, it’s public information. We call it “p” or modulus.

There is also another public number called “g” or base, which is less than p which is the primitive root of “p” prime number.

For example, let’s say p = 13, g 6

The second step is both participants (Alice and Bob) will pick a secret number. Let’s say sender secret key “a” and receiver secret key “b:

Let say a=3, b=10

Similar to color mixing Alice & Bob uses the below equation to mix their secret keys into public numbers:

After exchange the A and B will verify using below equation

B^a mod p   = A^b mod p

4³ mod 13 = 8¹⁰ mod 13

            12 = 12

If we have A = ga mod p and B = gb mod p, we can calculate gab mod p, without revealing a or b (which are called secret exponents).

This is how it works:

• Alice and Bob agree to use two public integers: modulus p and base g (where p is prime, and g is a primitive root modulo p).
• Alice chooses a secret integer a, then calculates and sends to Bob the number A = g^a mod p.
• Bob chooses a secret integer b, then calculates and sends to Alice the number B = g^b mod p.
• Alice computes s = B^a mod p  
• Bob computes s = Ab mod p
• Alice and Bob now share a secret number without reveling it.

Diffie Hellman Key Exchange algorithm is unaffected by sniffing attacks (data interception) but it is vulnerable to man-in-the-middle attacks (attacker secretly relays and possibly alters the communication between two parties).

Implementation C# Source Code of Diffie Hellman Key Exchange:

using System;
using System.Numerics; 

namespace SymmetricCryptography
{
    static class DiffieHellmanKeyExchange
    {
        static void Main()
        {
 Console.WriteLine("***********************************************************");            
           Console.WriteLine("Diffie Hellman Key Exchange Protocol Implementation in C# |"); 
           Console.WriteLine("***********************************************************"); 
           Console.WriteLine(""); 

            var primeNumber = 13;
            var gBase = 6;
            var aliceSecretKey = 3;
            var bobSecretKey = 10;          
            //Calculate Alice public key
            var A =BigInteger.ModPow(gBase, aliceSecretKey, primeNumber);
            Console.WriteLine($"Alice public key: {A}"); 

            var B = BigInteger.ModPow(gBase, bobSecretKey, primeNumber);
            Console.WriteLine($"Bob public key: {B}");

            //Find Alice secret key
            var aliceSecretKeyExchanged = BigInteger.ModPow(B, aliceSecretKey, primeNumber);
            Console.WriteLine($"Alice Secret Exchanged Key: {aliceSecretKeyExchanged}");

            //Find Alice secret key
            var bobSecretKeyExchanged = BigInteger.ModPow(A, bobSecretKey, primeNumber);            

           Console.WriteLine($"Bob Secret Exchanged Key: {bobSecretKeyExchanged}");
            Console.ReadLine();
        }
    }
}

Output: