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?


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.

| improve this answer | |
  • $\begingroup$ "$n=p$ a large prime: if $n$ has nontrivial factors" - do you mean "if $n-1$ has nontrivial factors"? $p, q$ prime and $q=(p-1)/2$, $p$ is a safe prime, not a strong prime. generator of order $(p-1)$ or order $q$ makes no big difference in this case, in your answer you may want to explain why. $\endgroup$ – Steve Peltz May 30 '15 at 1:33
  • $\begingroup$ @Bristol: Can you explain why generator of order $(p-1)$ or order $q$ doesn't make a difference? $\endgroup$ – kub0x Jun 1 '15 at 11:12
  • $\begingroup$ @Bristol: Also, if you choose a primitve root mod $n$ that generates the entire group, then an attacker could compute the discrete log over a subgroup of order $r$ where $r$ is a factor of $p$. Is this right? Thanks for your answer and time. $\endgroup$ – kub0x Jun 1 '15 at 11:17
  • $\begingroup$ If p is a prime then there are no factors of p to worry about! There's something else I didn't mention above, which motivates the choice of q rather than p-1: picking a generator of prime order means that the cyclic group thus generated has no nontrivial subgroups, so you don't have to deal with the possibility of small-subgroup attacks on some schemes. Admittedly this isn't such a problem when the only other factor is 2, but it's still nicer to work in a prime order group. $\endgroup$ – Bristol Jun 2 '15 at 9:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.