Diffie-Hellman

Diffie-Hellman is a key exchange algorithm based on public key cryptography written by Diffie and Hellman

Diffie-Hellman Algorithm

First we have to know the concept “Primitive root of a prime number” ,a primitive root x of a prime number p means : \(x \ mod(p), x^{2} mod(p), x^{3} mod(p),…, x^{p-1}mod(p)\) generates numbers from 1 to p-1.
In Diffie-Hellman algorithm there are two numbers
1- Prime number \(q\).
2- Primitive root of \(q = a\).
We have here a scenario to understand Diffie-Hellman algorithm
Two users A,B want to exchange keys by the following steps:
1- User A select a random number \({X}_{a} < q\).
2- User A compute \({Y}_{a} = a^{{X}_{a}}mod(q)\).
3- User B Select a random number \({X}_{b} < q\).
4- User B compute \({Y}_{b} = a^{{X}_{b}}mod(q)\).

Note: The X values are private and Y values are public.

5- User A compute the key \(K={Y}_{b})^{{X}_{a}}mod(q)\).
6- User B compute the key \(K={Y}_{a}^{{X}_{b}}mod(q)\).
7- A and B produce the same K value , if true , then the 2 sides have exchanged the secret keys.
Example:
Diffie-Hellman key exchange use the following:
Prime number q=353
Primitive root of q=353 , then a=3
A’s secret key \({X}_{a}=97\)
B’s secret key \({X}_{b}=233\)
Then calculate public values(Y)
\({Y}_{a} = a^{{X}_{a}}mod(q) = 3^{97} mod(353) = 40\)
\({Y}_{b} = a^{{X}_{b}}mod(q) = 3^{233} mod(353) = 248\)
A calculate \(K={Y}_{b})^{{X}_{a}}mod(q) = 248^{97} mod(353) = 160\)
B calculate \(K={Y}_{a}^{{X}_{b}}mod(q) = 40^{233} mod(353) = 160\)
K values are the same , then A and B

Note 2: Diffie-Hellman is not protected against Man-In-The-Middle attack , look at the following scenario:

User A and B want to exchange keys , if an attacker V want to get in middle
1- Attacker V generate 2 private keys \({X}_{v1}\) and \({X}_{v2}\).
2- Attacker V compute \({Y}_{v1}\) and \({Y}_{v1}\).
3- User A send Ya to user B.
4- Attacker V intercept \({Y}_{a}\) and send \({Y}_{v1}\) to user B , then attacker V calculate \({K}_{2}={Y}_{a})^{{X}_{v2}}mod(q)\).
5- User B receives \({Y}_{v1}\) and calculate \({K}_{1}={Y}_{v1}^{{X}_{b}} mod(q)\).
6- User B send \({Y}_{b}\) to user A.
7- Attacker V intercept \({Y}_{b}\) and send \({Y}_{v2}\) to user A , then attacker V calculate \({K}_{1}={Y}_{b}^{{X}_{v1}}mod(q)\).
8- User A receive \({Y}_{v2}\) and calculate \({K}_{2}={Y}_{v2}^{{X}_{a}} mod(q)\).

User A and B not sharing a secret key, but User A and attacker V share a secret key \({K}_{2}\) and user B and attacker V share a secret key \({K}_{1}\) so when user A send encrypted message to user B, attacker V intercept and decrypt this message by using \({K}_{2}\) and then encrypt it by using \({K}_{1}\) and send it to user B.