How does one calculate a primitive root for Diffie-Hellman?

Question

In the Diffie-Hellman key exchange, one of the steps involves calculating a primitive root of a prime number $p$. How would one go about doing so, considering that $p$ could be very large?

Is there some sort of algorithm or equation?

Answer 1

In the general case, for proper security with Diffie-Hellman, we need a value $g$ such that the order of $g$ (the smallest integer $n \geq 1$ such that $g^n = 1 \mod p$) is a multiple of a large enough prime $q$. "Large enough" means "of length at least $2t$ bits if we target $t$-bit security". Since $n$ necessarily divides $p-1$, $q$ divides $p-1$.

We normally want to know $q$, so $q$ is generated first, then $p$. Namely, we create a random prime $q$ of size $2t$ bits, then we produce $p = qr+1$ for random values of $r$ until we hit a prime. This is what is done for generating DSA key parameters, which have the same structure than Diffie-Hellman key parameters (see the DSA standard). Note that producing a random prime $p$ would already yield a "large enough" $q$ with overwhelming probability (but we wound not know the value of $q$, only that it is very improbable that the largest prime factor of $p-1$ is smaller than $2t$ bits).

Then, to get the "generator" $g$, we can just use any random integer modulo $p$: the probability that $q$ is not a divisor of the order of a random non-zero integer modulo $p$ if $1/q$, i.e. so small that you will not hit it in practice (the overall security of Diffie-Hellman relies on the practical impossibility of obtaining events which are billions of times more probable than that). Nevertheless, some people get nervous in the face of probabilities, and will feel safer if we test the generator. The procedure then becomes: create a random integer $u$ modulo $p$ and compute $g = u^{(p-1)/q} \mod p$. If $g = 1$, then try again with a new random $u$ (this is the very improbable event that you will not get in practice); otherwise, it can easily be shown that $g$ has order exactly $q$, and thus is a good generator for Diffie-Hellman.

Another method is to get a very large $q$, i.e. generate $p$ such that $p = 2q+1$ and $q$ is prime. We then call $p$ a "strong prime". It can be seen that the order of a random non-zero integer $g$ modulo $p$ is either $1$, $2$, $q$ or $2q$; order $1$ is possibly only with $g=1$, and order $2$ is possible only with $g=p-1$. Any other integer modulo $p$ will be fine for Diffie-Hellman. In particular, you can use $g=2$ as generator, which can yield a bit of a computational speed-up.

But really, the fastest way to get $p$ and the generator is to abstain from generating them. There is no security issue with Diffie-Hellman (or DSA) if you reuse previously generated $p$, $q$ and $g$; several people can share these values for their respective key pairs and this does not weaken the system in any way. So you can pick up "standard" values, e.g. the ones described in RFC 2409 (section 6.2) or RFC 5114 (sections 2.1 to 2.3).

Answer 2

We choose $p$ to be such that $p = 2k +1$ where $k$ is also a prime. It is relatively fast to find such $p$.

Then any number in $\mathbb{Z}^*_p$ will have an order which is one of ${2, k, 2k, 1}$

We pick a random number $x$ and check if $x, x^2, x^k \not\equiv 1 \pmod{p}$. If so, then $x$ is a primitive root of $p$, otherwise, we start over.

If we pick random numbers, we will very soon find one. The number of primitive roots are $(k-1) \approx p/2$ so that the probability of hitting a primitive root is about 1/2 in each try.

Answer 3

I would second Thomas's suggestion for reusing a standard DH group (either from RFC 2409 or RFC5114).

However, I would also add that, for Diffie-Hellman, you don't need a primitive element of the group. Instead, you want an element that generates a large prime order; my answer in For Diffie-Hellman, must g be a generator? explains why.

The standard DH groups have, in fact, large prime orders.