The Diffie-Hellman Key Exchange

As night darkens Nikita's cell, she reflects on what has happened. Upon realizing that she mis-remembered how the system works, she phones Michael and they do the following:

1. Together Michael and Nikita choose a 200-digit integer $p$ that is likely to be prime (see Section 2.4), and choose a number $g$ with $1<g<p$ .
2. Nikita secretly chooses an integer $n$ .
3. Michael secretly chooses an integer $m$ .
4. Nikita computes $g^n\pmod{p}$ on her handheld computer and tells Michael the resulting number over the phone.
5. Michael tells Nikita $g^m\pmod{p}$ .
6. The shared secret key is then
   $$s\equiv (g^n)^m \equiv (g^m)^n \equiv g^{nm}\pmod{p},$$
   which both Nikita and Michael can compute.

Here is a simplified example that illustrates what they did, that involves only relatively simple arithmetic.

1. $p=97$ , $g=5$
2. $n=31$
3. $m=95$
4. $g^n \equiv 7 \pmod{p}$
5. $g^m\equiv 39\pmod{p}$
6. $s \equiv (g^n)^m \equiv 14\pmod{p}$