Diffie-Hellman Algorithm: Overview & Implementation in C

The Diffie-Hellman algorithm is used to establish a shared secret between two parties that can be used for secret communication to exchange data over a public network.

Pictorial Explanation:

The process begins by having the two parties, Alice and Bob, agree on an arbitrary starting color that does not need to be kept secret (but should be different every time); in this example, the color is yellow. Each of them selects a secret color–red and aqua, respectively–that they keep to themselves. The crucial part of the process is that Alice and Bob now mix their secret color with their mutually shared color, resulting in orange and blue mixtures, respectively, then publicly exchange the two mixed colors. Finally, each of the two mixes together the color they received from the partner with their own private color. The result is a final color mixture (brown) identical to the partner’s color mixture.

Diffie-Hellman_Key_Exchange

It would be impossible for eavesdropper Eve to determine the common secret color.

Cryptographic Explanation:

The algorithm in itself is very simple. Let’s assume that Alice wants to establish a shared secret with Bob. Here’s an example of the protocol with secret values in red.

Alice and Bob agree to use a prime number p = 23 and base g = 5. (These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1).
Alice chooses a secret integer a = 6, then sends Bob A = g^a mod p (A = 5⁶ mod 23 = 8)
Bob chooses a secret integer b = 15, then sends Alice B = g^b mod p (B = 5¹⁵ mod 23 = 19)
Alice computes s = B^a mod p (s = 19⁶ mod 23 = 2)
Bob computes s = A^b mod p (s = 8¹⁵ mod 23 = 2)
Alice and Bob now share a secret (the number 2).

The number Alice get at step 4 is the same as Bob got in step 5 as

Bob computes

A^b mod p = (g^a mod p)^b mod p = g^ab mod p

Alice computes

B^a mod p = (g^b mod p)^a mod p = g^ba mod p

The Diffie-Hellman algorithm is primarily used to exchange cryptography keys for use in symmetric encryption algorithms like AES. Please note that information is not shared during the key exchange. Here the two parties are creating a key together.

Implementation:

C

#include <stdio.h>

// Function to compute `a^m mod n`

int compute(int a, int m, int n)

{

int r;

int y = 1;

while (m > 0)

{

r = m % 2;

// fast exponention

if (r == 1) {

y = (y*a) % n;

}

a = a*a % n;

m = m / 2;

}

return y;

}

// C program to demonstrate the Diffie-Hellman algorithm

int main()

{

int p = 23; // modulus

int g = 5; // base

int a, b; // `a` – Alice's secret key, `b` – Bob's secret key.

int A, B; // `A` – Alice's public key, `B` – Bob's public key

// choose a secret integer for Alice's private key (only known to Alice)

a = 6; // or, use `rand()`

// Calculate Alice's public key (Alice will send `A` to Bob)

A = compute(g, a, p);

// choose a secret integer for Bob's private key (only known to Bob)

b = 15; // or, use `rand()`

// Calculate Bob's public key (Bob will send `B` to Alice)

B = compute(g, b, p);

// Alice and Bob Exchange their public key `A` and `B` with each other

// Find secret key

int keyA = compute(B, a, p);

int keyB = compute(A, b, p);

printf("Alice's secret key is %d\nBob's secret key is %d", keyA, keyB);

return 0;

}

Download Run Code

Output:

Alice’s secret key is 2
Bob’s secret key is 2

That’s all about the Diffie-Hellman algorithm.

Reference: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange