Remark 5.5.2.3.
Instead of in \(\ZZ_p^\otimes\) any finite cyclic group can be used. For example the group of points on a elliptic curve.
Subsection 5.5.2 Diffie-Hellman
Let \(\ZZ_p^\otimes=\{1,2,3,\dots,p-1\}\) and let
\begin{equation*}
\otimes: \ZZ_p^\otimes\times\ZZ_p^\otimes\to \ZZ_p^\otimes,\quad a\otimes b=(a\cdot b)\bmod p.
\end{equation*}
We have \(a^{n\otimes}:=a^n\bmod p\text{.}\)
The agreement on \(p\) and \(g\) takes place over an insecure channel. Alice and Bob generate a shared secret \(s\) without sending the secret.
Alice computes
\begin{equation*}
s_A={B}{\otimes a}={\left({g}^{\otimes b}\right)}^{\otimes a}={g}^{\otimes (a\cdot b)}.
\end{equation*}
Bob computes
\begin{equation*}
s_B={A}^{\otimes b}={\left({g}^{\otimes a}\right)}^{\otimes b}={g}^{\otimes(b\cdot a)}.
\end{equation*}
Since \(a\cdot b=b\cdot a\) Alice and Bob share the secret \(s_A=s_B\text{.}\)\\
Assume Eve has eavesdropped on the communication between Alice and Bob and now knows the \(p\text{,}\) \(g\text{,}\) \(A\text{,}\) and \(B\text{.}\) To obtain the shared secret \(s\text{,}\) Eve needs either Alice’s secret \(a\) or Bob’s secret \(b\text{,}\) which can only be obtained by finding
So, the security of the Diffie-Hellman key exchange depends on the difficulty of computing discrete logarithms in \((\ZZ_p^\otimes,\otimes)\text{.}\)
To give an idea how large the prime \(p\) should be for the Diffie-Hellman key exchange to be secure, we present an example for a discrete logarithm that was computed in 2014.
Example 5.5.2.4.
Let \(p\) be the 180 decimal digit (596 digits in base 2) prime
\begin{align*}
p=
\amp 191147927718986609689229466631454649812986246276667354864188\\\\
\amp 503638807260703436799058776201365135161278134258296128109200\\\\
\amp 046702912984568752800330221777752773957404540495707852046983.
\end{align*}
The group \((\ZZ_p^\otimes,\otimes)\) is generated by \(g=5\text{,}\) that is \(\ZZ_p^\otimes=\{5^{n\otimes}\mid n\in\NN\}\text{.}\) In 2014 Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli, and Emmanuel Thom\’e announced that they computed the discrete logarithm to base 5 of
\begin{align*}
a=
\amp \phantom{8}68188080109582330879868861330998506151774854600403700625797\\\\
\amp 299927558995162740321112260973638619757922646242302104885437\\\\
\amp 536745080299248852065080008358309735875192480724496530325927.
\end{align*}
It took them under 130 core years (that is, on a single core computer it would take that long) on a parallel computing cluster to find the solution
\begin{align*}
n=
\amp 138670566126823584879625861326333326312363943825621039220215\\\\
\amp 583346153783336272559955521970357301302912046310782908659450\\\\
\amp 758549108092918331352215751346054755216673005939933186397777
\end{align*}
such that
\begin{equation*}
5^n\bmod p = a.
\end{equation*}
They applied the data computed for finding this discrete logarithm in the computation of further discrete logarithms which only required a few hours each.
The example illustrates that a 180 decimal digits (596 digits in base 2) prime is too small for cryptographic purposes, as the discrete logarithm problem can be solved in a (relatively) short amount of time, provided enough computation power is available. The commonly recommended size of the prime for the Diffie-Hellman key exchange is 3072 base 2 digits.
Example 5.5.2.5.
Let \(p\) be the 240 decimal digit (795 digits in base 2) prime
\begin{align*}
p=
\amp 124620366781718784065835044608106590434820374651678805754818\\\\
\amp 788883289666801188210855036039570272508747509864768438458621\\\\
\amp 054865537970253930571891217684318286362846948405301614416430\\\\
\amp 468066875699415246993185704183030512549594371372159029285303
\end{align*}
In 2020 Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thom\’e, and Paul Zimmermann reported that they had computed the discrete logarithm to base 5 of
\begin{align*}
a=
\amp77435662634397398596662221600608768692670558864995820616631\\\\
\amp7147722421706101723470351970238538755049093424997
\end{align*}
to be
\begin{align*}
n=
\amp926031359281441953630949553317328555029610991914376116167294\\\\
\amp204758987445623653667881005480990720934875482587528029233264\\\\
\amp473672441500961216292648092075981950622133668898591866811269\\\\
\amp28982506005127728321426751244111412371767375547225045851716
\end{align*}
such that
\begin{equation*}
5^n\bmod p = a.
\end{equation*}
https://xkcd.com/1323/) Changing the names would be easier, but if you’re not comfortable lying, try only making friends with people named Alice, Bob, Carol, etc.
