Diffie Hellman key exchange algorithm

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 XA<q$X_A<q$ and computes
   YA=αXAmod q$Y_A={\alpha }^{XA}modq$
7. User B independently selects a random integer XB<q$X_B<q$ and compute
   YB=αXBmod q$Y_B={\alpha }^{XB}modq$
8. Each side keeps X value private and makes Y value available publicly to the other side user A computes the key as:
   k=(YB)XAmod q$k=(Y_B{)}^{XA}modq$
   User B computes the key as :
   k=(YA)XBmod q$k=(Y_A{)}^{XB}modq$
   The calculations produce identical results :
   k=(YB)XAmod q−>calculated by user A=(αXBmod q)XAmod q=(αXB)XA(mod q)−>By rules of modular arithmetic=αXB XAmod q=(αXA)XBmod q$$\begin{gathered} k=(Y_B{)}^{XA}modq->\text{calculated by user A} \\ =({\alpha }^{XB}modq{)}^{XA}modq \\ =({\alpha }^{XB}{)}^{XA}(modq)->\text{By rules of modular arithmetic} \\ ={\alpha }^{XBXA}modq \\ =({\alpha }^{XA}{)}^{XB}modq \end{gathered}$$
   k=(αXAmod q)XBmod q$k=({\alpha }^{XA}modq{)}^{XB}modq$
9. Diffie Hellman key Exchange Algorithm
   1. k=(YA)XBmodq$k=(Y_A{)}^{XB}modq$ -> 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 XAXA<q$X_A{X}_A<q$
      Calculation of Public key YAYA=αXAmod q$Y_A{Y}_A={\alpha }^{XA}modq$
   4. USER B KEY GENERATION
      Select Private key XBXB<q$X_B{X}_B<q$
      Calculation of Public key YBYB=αXBmod q$Y_B{Y}_B={\alpha }^{XB}modq$
   5. Calculation of Secret Key by A
      k=(YB)XAmod q$k=(Y_B{)}^{XA}modq$
   6. Calculation of Secret Key by B
      k=(YA)XBmod q$k=(Y_A{)}^{XB}modq$
10. The result is that two sides have exchanged a secret value.
11. Since XA$X_A$ and XB$X_B$ are private the other party can work only following ingredients:
    q,α,XA,XB$q,\alpha ,X_A,X_B$
    Note: YB=αXB$Y_B={\alpha }_{XB}$ mod a
    XB=dlogα,q(YB)$XB=d\log \alpha ,q(YB)$

↑$\uparrow$

$$ 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.

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=97andXB=223$X{/}_A=97and{X}_B=223$
Each computes its public key
A computes YA=397$Y_A=3^{97}$ mod 353 =40
B computes YB=3233$Y_B=3^{233}$ mod 353 = 248
After exchange of public keys, each can compute the common secret key
A computes K =(YB)XAmod 353=(248)97mod 353=160$$\begin{gathered} =(Y_B{)}^{XA}mod353 \\ =(248{)}^{97}mod353 \\ =160 \end{gathered}$$
B computes K =(YA)XBmod 353=(40)253mod 353=160