For Diffie-Hellman, must g be a generator?

Question

Due to a number of recently asked questions about Diffie-Hellman, I was thinking this morning: must $g$ in Diffie-Hellman be a generator?

Recall the mathematics of Diffie-Hellman:

Given public parameters $p$ (a large prime) and $g$ (always referred to as a generator of $\mathbb{Z}^*_p$).

1. Alice chooses $a$ at random and sends $A \gets g^a \mod{p}$ to Bob.
2. Bob chooses $b$ at random and sends $B \gets g^b \mod{p}$ to Alice.
3. Alice computes $S \gets B^a \mod{p}$
4. Bob computes $S \gets A^b \mod{p}$

From the math above, I don't see anything that would require $g$ to be a generator, so the math should work even if $g$ is not a generator.

As far as security goes, clearly having $g$ be a generator is best as $|g|$ (or the order of $g$) will be greatest when $g$ is indeed a generator. Is that the only reason for choosing $g$ to be a generator?

Answer 1

First, we are talking about multiplications, so we work in $\mathbb{Z}_p^*$, not $\mathbb{Z}_p$.

By definition, any integer $g \in \mathbb{Z}_p^*$ is the generator for... the subgroup generated by $g$, i.e. the set of $g^k \mod p$ for all integer values $k$. The order of $g$ is the smallest $k \geq 1$ such that $g^k = 1 \mod p$.

For soundness (Alice and Bob end up with the same shared key), any $g$ will do.

For security, we need the order of $g$ to be a multiple of a large enough prime value, usually denoted $q$. It is not necessary that $g$ generates the whole of $\mathbb{Z}_p^*$. It is not necessary that the order of $g$ is exactly $q$.

If the targeted security level for Diffie-Hellman is "$t$ bits" (i.e. the system will resist attacks up to at least computational effort $2^t$), then $p$ must be big enough (see this site for estimates, but, roughly speaking, you need a 1024-bit integer for $t = 80$) and the size of $q$ must be at least $2t$ bits. Also, the DH private keys ($a$ and $b$) must be randomly and uniformly generated integers of size at least $2t$ bits. It is not necessary that $a$ and $b$ are generated uniformly among integers modulo $q$, only that they are generated among a large enough range (this differs from DSA, in which we need a random $k$ which MUST be generated uniformly in the $[1, q-1]$ range).

Answer 2

Not only does g not need to be a generator for the entire group, general practice is that it is not.

As Thomas has mentioned, the order of $g$ is the smallest $k \ge 1$ such that $g^k = 1 \mod p$.

Let $q$ be the order of the value $g$ we use. If $g$ is a generator for the entire group, then $q = p-1$, if not, it is some proper divisor of $p-1$.

Now, if $q$ is composite, and has a factor $r$, it turns out someone in the middle can determine the value $a \mod r$ (where $a$ is the private exponent) from the public value $A$ in $O( \sqrt r )$ steps. One way to do this:

• Compute the value $A ^ {q/r}$
• Determine the value $k$ such that $(A^{q/r})^k = g^{q/r} \mod p$, which is a discrete log problem over a subgroup of order $r$

So, if $q$ has small factors, you're essentially giving a few bits of the private exponent to the attacker. And, if $g$ is a generator, then $q$ will always be composite (because it is even). This need not be fatal; if $q$ has only a few small factors, both sides can increase the size of the private exponents to compensate. However, there's little reason to give the attacker that advantage.

Instead, common practice is to pick a value $g$ which has a large prime order; hence the above observation is not a concern.

Answer 3

As far as security goes, clearly having g be a generator is best as $|g|$ (or the order of $g$) will be greatest when $g$ is indeed a generator. Is that the only reason for choosing $g$ to be a generator?

Yes that is the only reason to choose a generator, to keep the group large enough.