## 3/02/2016

### cryptography13

Cryptography 13

Diffie-Hellman Key Exchange

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
A- Prime number q.
B- 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 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: 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.