Generator G's requirement to be a primitive root modulo p in the Diffie Hellman algorithm

Question

Having searched, I've found myself confused by the use of P and G in the Diffie Hellman algorithm. There is requirementy that P is prime, and G is a primitive root of P.

I understand the security is based on the difficulty of factoring the result of two very large prime numbers, so I have no issue with that. However, there appears to be little available information on the purpose of G being a primitive root of P. Can anyone answer why this requirement exists (with references if possible)? Does it just increase the security? Given that shared keys can be created with apparently any combination of p and g, even ones that are not prime, I find this intriguing. It can surely only be for security? If so, how does it increase it?

Thanks in advance

Daniel

Answer 1

The security of Diffie-Hellman is not based on the difficulty of factoring. It is based on the (assumed) difficulty of calculating general discrete logarithms.

g must be a primitive root of p for the algorithm to be correct and useable. It ensures that for every number 0 <= x < p, there is a distinct value of g^x mod p. That is, it ensures that g can "generate" every value in the finite field.

Answer 2

If g is not a primitive root of p, g will only generate a subgroup of GF_p. This has consequences for the security properties of the system: the security of the system will only be proportional to the order of g in GF_p instead of proportional to the full order of GF_p.

To take a small example: select p=13 and g=3.

The order of 3 in GF_13 is 3 (3^1=3, 3^2=9, 3^3=1).

Following the usual steps of Diffie-Hellman, Alice and Bob should each select integers a, b between 1 and p-1 and calculate resp. A = g^a and B = g^b. To brute force this, an attacker should expect to try all possible values of a (or b) between 1 and p-1 until he finds a value that yields A (or B). But since g was not a primitive root modulo p, he only need to try the values 1, 2 and 3 in order to find a solution a' so that A = g^a'. And the secret is s = g^ab = (g^a)^b =(g^a')^b = g^a'b = (g^b)^a' = B^a', which the attacker can now calculate.

Answer 3

There is no requirement that the generator g used for Diffie-Hellman is a primitive root nor is this even a common choice. Much more popular is to choose g such that it generates a prime order subgroup. I.e. the order of g is a prime q, which is a large prime factor of p-1.

For example the Diffie-Hellman groups proposed for IKE have been chosen such that p is a safe prime and g generates the subgroup of order (p-1)/2.

One motivation for choosing g as a generator of a big prime order subgroup is that this allows to make the decisional Diffie-Hellman assumption. This assumption does not hold if g is a primitive root, and that makes the analysis of the implemented protocols somewhat harder.