Realistic Diffie-Hellman Example

In this section we present an example that uses bigger numbers. First we prove a proposition that we can use to choose a prime $p$ in such a way that it is easy to find a $g\in(\mathbb{Z}/p\mathbb{Z}{})^*$ with order $p-1$ . We have already seen in Section 2.5 that for every prime $p$ there exists an element $g$ of order $p-1$ , and we gave Algorithm 2.5.16 for finding a primitive root for any prime. The significance of the proposition below is that it suggests an algorithm for finding a primitive root that is easier to use in practice when $p$ is large, because it does not require factoring $p-1$ . Of course, one could also just use a random $g$ for Diffie-Hellman; it is not essential that $g$ generates $(\mathbb{Z}/p\mathbb{Z}{})^*$ .

Proposition 3.1   Suppose $p$ is a prime such that $(p-1)/2$ is also prime. Then the elements of $(\mathbb{Z}/p\mathbb{Z}{})^*$ have order either $1$ , $2$ , $(p-1)/2$ , or $p-1$ .

Proof. Since $p$ is prime, the group $(\mathbb{Z}/p\mathbb{Z}{})^*$ has order $p-1$ . By assumption, the prime factorization of $p-1$ is $2\cdot ((p-1)/2)$ . Let $a\in (\mathbb{Z}/p\mathbb{Z}{})^*$ . Then by Theorem 2.1.19, $a^{p-1}=1$ , so the order of $a$ is a divisor of $p-1$ , which proves the proposition. $\qedsymbol$

Given a prime $p$ with $(p-1)/2$ prime, find an element of order $p-1$ as follows. If $2$ has order $p-1$ we are done. If not, $2$ has order $(p-1)/2$ since $2$ doesn't have order either $1$ or $2$ . Then $-2$ has order $p-1$ .

Let $p=93450983094850938450983409611$ . Then $p$ is prime, but $(p-1)/2$ is not. So we keep adding $2$ to $p$ and testing pseudoprimality using algorithms from Section 2.4 until we find that the next pseudoprime after $p$ is

$$q=93450983094850938450983409623.$$

It turns out that $q$ pseudoprime and $(q-1)/2$ is also pseudoprime. We find that $2$ has order $(q-1)/2$ , so $g=-2$ has order $q-1$ modulo $q$ , and is hence a generator of $(\mathbb{Z}/q\mathbb{Z}{})^*$ , at least assuming that $q$ is really prime.

The secret random numbers generated by Nikita and Michael are

$$n = 18319922375531859171613379181$$

and

$$m = 82335836243866695680141440300.$$

Nikita sends

$$g^n = 45416776270485369791375944998 \in (\mathbb{Z}/p\mathbb{Z}{})^*$$

to Michael, and Michael sends

$$g^m = 15048074151770884271824225393\in (\mathbb{Z}/p\mathbb{Z}{})^*$$

to Nikita. They agree on the secret key

$$g^{nm} = 85771409470770521212346739540\in (\mathbb{Z}/p\mathbb{Z}{})^*.$$

SAGE Example 3.1   We illustrate the above computations using SAGE.

sage: q = 93450983094850938450983409623
sage: q.is_prime()
True
sage: is_prime((q-1)//2)
True
sage: g = Mod(-2, q)
sage: g.multiplicative_order()
93450983094850938450983409622
sage: n = 18319922375531859171613379181; m = 82335836243866695680141440300
sage: g^n
45416776270485369791375944998
sage: g^m
15048074151770884271824225393
sage: (g^n)^m
85771409470770521212346739540
sage: (g^m)^n
85771409470770521212346739540