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

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.