# Solution

Alice and Bob agree to create a secret encryption key for future correspondence according to the Diffie-Hellman Key Exchange Protocol. Over a public communications channel, they agree upon a prime base of $5$ and a modulus of $23$. Alice then sends Bob the value $8$, and Bob sends Alice the value $19$. What is their agreed upon secret encryption key? What could they have done to better protect the secret key they generated? (Hint: You may wish to refer to the table of powers and indexes $\pmod{23}$ provided below.)

$$\begin{array}{rclcrcl|rclrcl} 5^1 &\equiv& 5 && 5^{12} &\equiv& 18 & \text{ind}_5 1 &=& 22 & \text{ind}_5 12 &=&20\\ 5^2 &\equiv& 2 && 5^{13} &\equiv& 21 & \text{ind}_5 2 &=& 2 & \text{ind}_5 13 &=&14\\ 5^3 &\equiv& 10 && 5^{14} &\equiv& 13 & \text{ind}_5 3 &=& 16 & \text{ind}_5 14 &=&21\\ 5^4 &\equiv& 4 && 5^{15} &\equiv& 19 & \text{ind}_5 4 &=& 4 & \text{ind}_5 15 &=&17\\ 5^5 &\equiv& 20 && 5^{16} &\equiv& 3 & \text{ind}_5 5 &=& 1 & \text{ind}_5 16 &=&8\\ 5^6 &\equiv& 8 && 5^{17} &\equiv& 15 & \text{ind}_5 6 &=& 18 & \text{ind}_5 17 &=&7\\ 5^7 &\equiv& 17 && 5^{18} &\equiv& 6 & \text{ind}_5 7 &=& 19 & \text{ind}_5 18 &=&12\\ 5^8 &\equiv& 16 && 5^{19} &\equiv& 7 & \text{ind}_5 8 &=& 6 & \text{ind}_5 19 &=&15\\ 5^9 &\equiv& 11 && 5^{20} &\equiv& 12 & \text{ind}_5 9 &=& 10 & \text{ind}_5 20 &=&5\\ 5^{10} &\equiv& 9 && 5^{21} &\equiv& 14 & \text{ind}_5 10 &=& 3 & \text{ind}_5 21 &=&13\\ 5^{11} &\equiv& 22 && 5^{22} &\equiv& 1 & \text{ind}_5 11 &=& 9 & \text{ind}_5 22 &=&11\\ \end{array}$$

Recall, Alice has secretly chosen an exponent $a$ and sent Bob $5^a$, while Bob has secretly chosen an exponent $b$ and sent Alice $5^b$. Each can then take the other's sent number and raise it to their own secret exponent to obtain $5^{ab}$, the secret agreed-upon key.

However, Alice and Bob did not choose a modulus near large enough to prevent an eavesdropper like us from solving for $a$ and $b$.

We know that $5^a \equiv 8 \pmod{23}$ and $5^b \equiv 19 \pmod{23}$.

Consulting the table given suggests that $a = 6$ and $b = 15$. (Note that we need not be given the table to solve the problem -- we could have easily constructed it from scratch.)

It remains to calculate the value of the secret key...

$$5^{ab} = 5^{6 \cdot 15} = 5^{90} = (5^{22})^4 \cdot 5^2 \equiv 5^2 \equiv 2 \pmod{23}$$