Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 11 down vote accepted

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).

share|improve this answer
    
I fixed the issue with the group notation. Thanks –  mikeazo Sep 28 '11 at 12:33
1  
Implied in all of the above is "according to current cryptanalysis". The parameters above are a function of (1) our current computing model and (2) our current state of knowledge. –  Fixee Sep 28 '11 at 15:47
1  
@Fixee: yes -- a quantum computer, if it exists one day, totally kills Diffie-Hellman (including the elliptic curve variants). –  Thomas Pornin Sep 28 '11 at 15:49
    
@Thomas: Improved attacks could also kill DH (or require parameter adjustments). I guess I'm trying to advocate that authors of cryptographic content stop saying (for example) "factoring large integers is impossible" and instead say "there is no publicly-known efficient factoring algorithm on conventional computers". Although I suppose it can get tiresome after a while. Nonetheless, I'm very careful to say the latter when teaching. –  Fixee Sep 28 '11 at 15:58

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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