Confusion about the choice of primitive root/multiplicative generator in Diffie-Hellman Key Exchange.

Question

I was reading "Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography, Second Edition". I understand the basic Diffie-Hellman Key Exchange. Though, I was interested in reading about what is wrong with picking a primitive root/multiplicative generator $g$ with a small order. The book on page 68, second line, says:

For various reasons to be discussed later, it is best if they (Alice and Bob) choose $g$ such that its order in $\mathbb F_p$ is a large prime.

I don't understand this. By definition, a primitive root is an element of $\mathbb F_p$ with order $\varphi(p) = p - 1$. Here $p$ is a large prime and $\varphi$ is the Euler's phi function. So, if the order of $g \mod p$ is $p-1$ how can it ever be a "large prime"?

Answer 1

$ord(g) \mid p-1$ and, as you said, $p-1$ is never prime. Since you want the order of $g$ to be prime, you choose $g$ such that its order is a large prime divisor of $p-1.$ In particular, notice that $g$ can't be a primitive element of $\mathbb{F}_p$.

Answer 2

After doing some reading at other places, I realised that the choice of $g$ does not strictly have to be that of the primitive root. This is also mentioned in @Riccardo's answer though I wanted to discuss more details. Johannes A. Buchmann's Introduction to Cryptography, Second Edition, page 188, tells us how to pick a $g$ even when not a primitive root.

...an integer $g$ with $2 \leq g \leq p - 2$ such that the order of $g \mod p$ is sufficiently high.

So the crucial requirement here is not that $g$ be primitive root in $\mathbb F_p$ but that the order of $g$ must be high. Picking $g$ to be the primitive root is simply a way of fulfilling the high order requirement since we know that the order of a primitive root is $\varphi(p) = p-1$.

I'll show why $order(g)$ has to be large through a toy example. Suppose Alice and Bob decide to use Diffie-Hellman key exchange and pick $p = 101$. In this made up world pretend that a hundred brute force checks are infeasible. They could pick $g = 2 \mod 101$ since that is a primitive root and has an order of 100. Eve will have $A = g^a$ and she'll need to do a 100 checks of $g^x \stackrel{?}{=} A = g^a$ to find something that works like Alice's secret key $a$. Although, we know that since 100 checks are infeasible in our made-up illustration world, Alice is safe.

What if Alice and Bob had picked $g = 10 \mod 101$ which has order 4 and,

\begin{align*} 10^0 &\equiv 1 \mod 101 \\ 10^1 &\equiv 10 \mod 101 \\ 10^2 &\equiv 100 \mod 101 \\ 10^3 &\equiv 91 \mod 101 \\ 10^4 &\equiv 1 \mod 101 \\ \end{align*}

Now Eve only needs to do 4 such $g^x \stackrel{?}{=} A = g^a$ checks! Therefore, to keep the key space large, we keep the order of $g$ high and that can be satisfied either by picking $g$ as the primitive root or any element of $\mathbb F_p^*$ of large order.