For Diffie-Hellman, must g be a generator? 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$).


Alice chooses $a$ at random and sends $A \gets g^a \mod{p}$ to Bob.
Bob chooses $b$ at random and sends $B \gets g^b \mod{p}$ to Alice.
Alice computes $S \gets B^a \mod{p}$
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?
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).