1. In Public key encryption schemes are secure only if authenticity of the public key is assured.
2. Diffie-Hellman key exchange is a simple public key algorithm.
3. The protocol enables 2 users to establish a secret key using a public key scheme based on discrete algorithms.
4. The protocol is secure only if the authenticity of the 2 participants can be established.

5. or this scheme, there are 2 publicly known numbers :

   • A prime number q
   • An integer α that is a primitive root of q.

   (Note: Premitive root of a prime number P is one, whose powers module P generate all the images from 1 to P-1)

6. Suppose users A and B wish to exchange the key.

   User A selects a random integer $X_A \lt q$ and computes

   $Y_A = α^{XA} mod \ q$

7. User B independently selects a random integer $X_B \lt q$ and compute

   $Y_B = α^{XB} mod \ q$

8. Each side keeps X value private and makes Y value available publicly to the other side user A computes the key as:

   $k = (Y_B)^{XA} mod \ q$

   User B computes the key as :

   $k = (Y_A)^{XB} mod \ q $

   The calculations produce identical results :

   $k = (Y_B)^{XA} mod \ q -\gt \text{calculated by user A} \\ = (α^{XB} mod \ q )^{XA} mod \ q \\ = (α^{XB} )^{XA} (mod \ q ) -\gt \text{By rules of modular arithmetic} \\ = α^{XB \ XA} mod \ q \\ = ( α^{XA} )^{XB} mod \ q$

   $k = ( α^{XA} mod \ q )^{XB} mod \ q$

9. Diffie Hellman key Exchange Algorithm

   1. $k = (Y_A )^{XB} mod q$ -> same as calculated by B

   2. Global Public Elements

      q ; prime number

      α ; α < q and it is primitive root of q

   3. USER A KEY GENERATION

      Select Private key $X_A \hspace{3.6cm} X_A \lt q$

      Calculation of Public key $Y_A \hspace{3cm} Y_A = α^{XA} mod \ q$

   4. USER B KEY GENERATION

      Select Private key $X_B \hspace{3.6cm} X_B \lt q$

      Calculation of Public key $Y_B Y_B = α^{XB} mod \ q$

   5. Calculation of Secret Key by A

      $k = (Y_B)^{XA} mod \ q$

   6. Calculation of Secret Key by B

      $k = (Y_A)^{XB} mod \ q$

10. The result is that two sides have exchanged a secret value.

11. Since $X_A$ and $X_B$ are private the other party can work only following ingredients:

    $q, α , X_A , X_B$

    Note: $Y_B = α_{XB}$ mod a

    $XB = d \log α, q (YB)$

$\hspace{3cm}\uparrow$

$\hspace{2.5cm}$ Discrete Logarithm

12. The algorithm security lies on the fact that it is easy to calculate exponential modulo a prime, last difficult to calculate to calculate discrete logarithm.

$$\text{Figure 5.6 Diffie-Hellman Exchange Algorithm}$$

Example:

Consider q=353, α= 3 ( 3 is primitive root of 353)

A and B discrete private keys

$X/_A =97 and X_B = 223$

Each computes its public key

A computes $Y_A = 3^{97}$ mod 353 =40

B computes $Y_B = 3^{233}$ mod 353 = 248

After exchange of public keys, each can compute the common secret key

A computes K $= (Y_B)^{XA} mod \ 353 \\ = (248)^{97} mod \ 353 \\ = 160$

B computes K $= (Y_A )^{XB} mod \ 353 \\ = (40)^{253} mod \ 353 = 160$