## Section5.2Diffie-Hellman Key Exchange

The ideas from Exploration 5.1.1 are the basis for a way to securely exchange a key without having to meet privately. That is, all the communication between volunteer 1 and volunteer 2 can be done over a public, insecure channel but yet they will agree on a secure, secret key. (Ok, actually, its not so secure in the given example with mod 11, but we can make it secure with an appropriate choice of the mod and base.) This is the idea for the Diffie-Hellman key exchange. This key exchange method was first published in 1976 in the previously mentioned “New Directions in Cryptography” paper by Diffie and Hellman with credits to Ralph Merkle for important ideas.

###### Definition5.2.1.

For the Diffie-Hellman key exchange, select a mod, $p\text{,}$ and a base, $b\text{,}$ and make them public. Alice picks a secret number $x\text{,}$ and computes a public number $A \equiv b^x$ mod $p\text{.}$ Alice sends $A$ to Bob. Bob picks a secret number $y\text{,}$ and computes his public number $B \equiv b^y$ mod $p\text{.}$ Bob sends $B$ to Alice. Alice obtains the secret key by computing $K\equiv B^x$ mod $p\text{.}$ Bob obtains the secret key by computing $K\equiv A^y$ mod $p\text{.}$

###### Question5.2.2.

Why does Diffie-Hellman work? That is, why do both Bob and Alice get the same key?

You should have explained why both Bob and Alice get the same key in Exploration 5.1.1. If not, explore that now!

Hint
Think about properties of exponents and modular arithmetic.
###### Question5.2.3.

Why is Diffie-Hellman secure? That is, if $b\text{,}$ $p\text{,}$ $A$ and $B$ are public, why can't everyone compute $K \equiv A^y \mod p\text{?}$

In this case, we would need to know $y$ to find $K\text{.}$ From the public information we would need to be able to solve $b^y\equiv B \mod p$ for $y$ given that $b\text{,}$ $B\text{,}$ and $p$ are public. Can we?

For example, suppose we want to solve

\begin{equation*} 3^y \equiv 25 \pmod{91}. \end{equation*}

At this point, you might be tempted to use logarithms because this is how we would solve

\begin{equation*} 3^y=25 \end{equation*}

in the real number system. However, if we try this mod $p\text{,}$ what happens? Does $y = \frac{ln(25)}{ln(3)}$ make sense mod $p\text{?}$ Certainly not!

Indeed, this problem of solving for $y$ in $b^y\equiv B \mod p$ is called the discrete log problem as solving this equation mod $p$ is a discrete version of the problem that is so easy to solve in a continuous setting. Generally, there is no easy way to solve this for $y$ without just trying all the possible values mod $p$ and seeing if they work. If $p$ is large enough (hundreds of digits!), then this will take much too long to be computationally feasible.

###### Example5.2.4.

Solve the equation $6^y \equiv 5 \pmod{13}$ for $y\text{.}$ To try all possible values for $y$ in a brute force attack, we will use Sage.

From this we see that the smallest positive solution is $y = 9\text{.}$

###### Question5.2.5.

Which values of mod $p$ and base $b$ work well for Diffie-Hellman key exchange?