4.3.1. Diffie-Hellman protocol
Diffie-Hellman protocol is a method of securely exchanging cryptographic keys in public channel. This algorithm was introduced by Whitfield Diffie and Martin Hellman in 1976. In this protocol two parts Alis and Bob going to establish a common secret using public channel, such that if third party eavesdrop communication, can not guess a secret. Security of Diffie-Hellman protocol relies on difficulties of computing discrete logarithm.
If \(G\) is a group then for \( g \in G\) and natural number \(n\) then by \(g^n\) we denote \(n\)-th power of element \(n\). More precisely \(g^1=g\) and \(g^{n+1}=gg^n\). If \( h \in G\) then discrete logarithm of element \(g \in G\) in base \(h\) is natural number \(n\) such that \(h^n= g\).
Difficult logarithm problem
Note that computation complexity of exponential function \( g^x\) is \(log_{2}(x)\)
(for example to compute \( g^8\) we must make three multiplication).
But computation of discrete logarithm \( log_{h}(x)\) is very difficult, for appropriate group \(G\)
there is no better way than checking if \( h^x=g\) for every \( x=1,2,...,|G|\)
In this case we say that group \(G\) have difficult logarithm problem.
Example of group with difficult discrete logarithm we can find among \( Z^{*}_{n}\) and elliptic groups.
At the beginning public parameters: a group \(G\), \( h \in G\) are fixed. To determined a shared secret Alice and Bob execute the following protocol.
- Alice choose randomly \(a\) an element of group \(G\), next compute \(A=h^a\) and send \(A\) to Bob.
- Bob choose randomly \(b\) an element of group \(G\), next compute \(B=h^a\) and send \(B\) to Alice.
- Alice compute \(S=B^a\).
- Bob compute \(S'=A^b\).
First let us see that \(S=S'\) is common secret of Alice and Bob: \[ S=B^a=(h^{b})^{a}=h^{ba} =h^{ab}=(h^{a})^{b}=A^b=S'\] If third party eavesdrop communication, then get a value \(A=h^a\) and \(B=h^a\), and only known way to compute \(h^{ba}\) is extract a value of \(a\) and \(b\), since computing discrete logarithm \(a=log_{h}A\) and \(b=log_{h}B\). If group \(G\) have difficult logarithm then it is hard to guess secret \(S\).