About Primitive roots mod n in Diffie-Hellman [duplicate]

Question

I'm on the study of Diffie-Hellman and its related math (multiplicative group of integers $\mod n$).

In some crypto papers and documents I've read that $g$ needs to be a primitive root mod $n$ ($g$ order in $G = \phi(p)$), but we actually use $g$ as a generator of a large subgroup of order $q$, where $q$ is a large prime extracted from $(n-1)/2$ ($p$ is a safe prime). So $g$ isn't a primitive root modulo $n$, because $g$ doesn't generate the entire group of $n-1$ but generates a subgroup of length $q$.

I understand that if a prime number (say 'x') divides the group's order then a generator exists whose order in G is 'x'. This is the current schema in the implementations of Diffie-Hellman (like I said before).

Example: $q = 1349363$; $p=2q+1=2698727$. So $\phi(p) = p-1$, $q|p-1$ so a generator $g$ exists whose order in $G$ is $q$.

And here's my opinion: I think this is used because doing modular exponentiation on big generators is slow, so we can use $2$ as a generator. It will generate a lower subgroup of elements, but if $q$ is big enough, it will increase the math performance without being insecure. Correct me if I'm wrong.

But I wish to clear the following doubts:

Why is not recommended to use a primitive root mod $n$ in Diffie-Hellman? Why do some crypto papers say that a primitive root modulo $n$ is needed?

---

According to For Diffie-Hellman, must g be a generator? So a primitive root modulo $n$ (or a true generator) isn't chosen because its order in $G$ is composite. Thus it reveals information about the private exponent. Instead, a generator of a subgroup of order $q$ (factor of |G|) is used, where $q$ is prime and large enough. Is this correct?

Answer 1

The problem you want to make hard in Diffie-Hellman type groups is taking discrete logarithms, whereas you want exponentiation to be easy. Now when you pick a subgroup $G$ of $\mathbb Z^*_n$, the cost of exponentiation will be roughly proportional to $n$ whereas the cost of taking discrete logs will be proportional to $\sqrt{k}$ where $k$ is the order of the largest subgroup in a decomposition of $G$. (Actually, for the number field sieve the formula is more complicated and less than $\sqrt{k}$, but it is still an expression in $k$.) So you want to have $k$ big to get your security up and once you've decided on $k$ you want $n$ to be as small as possible to make the whole thing efficient. In other words, you want to minimise the computation cost to security level ratio $n/k$.

The best possible choice is to let $n = p$ a large prime: if $n$ were not a prime and had nontrivial factors, then $k$ couldn't be larger than the largest of these factors, and all other factors are just slowing things down without adding any security. Since $\mathbb Z^*_p$ has $p-1$ elements which will be an even number, there's always a subgroup of order $2$ and the best possible choice of group order is $q = (p-1)/2$ again a prime (in which case $p$ is a "strong prime"). For such a choice, $k = q$ as it doesn't have any nontrivial factors, so the computation cost/security level ratio is $n/k = p/q$ is approximately $2$, the smallest possible. And in this case any generator is automatically a primitive root.