As generator $g$ is used in DH how do you find a combination of prime $p$ and $g$? eg: if we choose $p=23$ and its generator is $7$ (given in the book) how do we find the generator?


2 Answers 2


Mike gave you the answer for the specific question you asked. I'll try to give you an answer to the question you should have asked:

For Diffie-Hellman, what criteria should I use to select a secure $p$ and $g$?

This question is important, because not every large cyclic group is actually secure. It turns out that, for the group $\mathbb{Z}_p^*$, the factorization of $p-1$ is critical.

If $p-1$ has a factor $q$, and $g^{(p-1)/q} \ne 1$, then given $g$ and $g^x \bmod p$, we can determine $x \bmod q$ in $O(\sqrt{q})$ time.

What does this mean? Well, if we pick a $p$ where $p-1$ has a bunch of small factors $q_1, q_2, q_3$, and we give $g$ to be a primitive element (so $g^{(p-1)/q} \ne 1$ for any $q > 1$), then we transmit $g^x \bmod p$ as a part of the DH exchange, the attacker can efficiently derive $x \bmod q_1q_2q_3$; we're effectively giving him $\log_2 q_1q_2q_3$ bits of our secret exponent. This means that, with a random prime $p$ and either a random $g$, or a primitive $g$, we have a good possibility of leaking quite a bit of information.

So, what do we do? Well, first of all, we make sure that $p-1$ has a large prime factor $q$ that we know. There are two common practices:

  • Select a prime $p$ with $(p-1)/2$ prime as well (often called a safe prime). If we do that, then $q = (p-1)/2$ is certainly large enough (assuming $p$ is large enough).

  • Select a prime value $q$ (perhaps 256 to 512 bits), and then search for a large prime $p = kq + 1$ (perhaps 1024 to 2048 bits). This is called a Schnorr prime

Once we have our values $p$ and $q$, we then select a generator $g$ that is within the subgroup of size $q$. Members of this subgroup have the property that $g^{(p-1)/r} = 1$ for any factors $r$ of $p-1$ other than $q$ (and $p-1$ itself), hence the above observation does not apply.

One easy way of selecting a random generator is to select a random value $h$ between 2 and $p-1$, and compute $h^{(p-1)/q} \bmod p$; if that value is not 1 (and with high probability, it won't be), then $h^{(p-1)/q} \bmod p$ is your random generator.

An alternative method of finding a generator $g$: if you selected a safe prime, and if your safe prime also satisfied the condition $p = 7 \bmod 8$, then the value $g=2$ will always be a generator for the group of size $q$. It won't obviously be a random generator, however, we can also show that, with a safe prime, if you can solve the computational Diffie-Hellman problem with $g=2$, you can solve it with any $g$ (with a polynomial number of queries), hence $g=2$ cannot be weak.

  • 1
    $\begingroup$ There's something that seems confusing in your answer and I hope you can clarify it. If we select a safe prime $p=2q+1$ and we now want to select a generator $g$ within the subgroup of size $q$, you suggest to take a random value $h$ between $2$ and $p-1$ and then compute $h^{(p-1)/q} \mod p$, which would be the same as computing $h^2 \mod p$. If the result of this is not $1$ this definitely means that $h$ is not a generator of the subgroup of order $2$, but this doesn't necessarily mean that it's a generator of the one of order $q$, we still would have to check that $h^q=1 \mod p$, don't we? $\endgroup$
    – LRM
    Feb 20, 2015 at 9:58
  • 1
    $\begingroup$ @LRM: you misunderstood the pronoun (and I fixed the answer to be clearer); compute $h^2$, and if this is not 1, then $h^2$ is your generator (not $h$ -- I used "it's", and it wasn't clear which that referred to). Then, we needn't bother to check if $(h^2)^q = 1$, as that's $h^{2q} = h^{p-1}$, and Fermat's Little Theorem says that'll be 1. $\endgroup$
    – poncho
    Feb 20, 2015 at 14:23
  • 1
    $\begingroup$ @omnomnom; no, they're not the same; if $g^{(p-1)/r} \ne 1$, then the size of the subgroup that $g$ generates has $r$ as a factor (assuming $r$ is a divisor of $p-1$). In contrast, if $g^q \bmod p = -1$, then the size of the subgroup that $g$ generates is either $2$ or $2q$ (assuming $q$ is prime) $\endgroup$
    – poncho
    Feb 28, 2019 at 22:29
  • 1
    $\begingroup$ @omnomnom: the context is that $g$ is an element of order $q$; that is, $g^q = 1$. $q$ is a prime divisor of $p-1$, hence for any other prime divisor $r$ of $p-1$, $(p-1)/r$ is a multiple of $q$, that is, $(p-1)/r = kq$ for some integer $k$. So, $g^{(p-1)/r} = g^{kq} = (g^q)^k = 1^k = 1$ $\endgroup$
    – poncho
    Mar 3, 2019 at 17:29
  • 1
    $\begingroup$ @pacman: telling you the value $x \bmod r$ gives you $\log_2 r$ bits of information about $x$ $\endgroup$
    – poncho
    Oct 12, 2023 at 12:58

I'm assuming you meant "how to efficiently find generator $g$ in a cyclic group?"

Small groups
For small values $p$, bruteforce is efficient.

Large groups with known factorization of group order
The order of the group $\mathbb{Z}_p^*$ is $p-1$. The order of every element divides the order of the group, so the factorization of $p-1$ reveals the possible orders of elements. Using this information, one can fairly efficiently find the order of any element in the group. See also Algorithm 4.79.

Note: this will also work for small groups as you should be able to factor $p-1$ for small values of $p$.

Large groups with unknown factorization of group order
There is no efficient method for finding the order of group elements. With DH, however, since you get to choose $p$, there are some things you can do to find generators of the full group $\mathbb{Z}_p$ or a generator of a large cyclic subgroup with in $\mathbb{Z}_p$. See 4.6.1 of HAC Ch 4. See also another question here.

  • $\begingroup$ I would like to point that the algorithm mentioned is the 4.80, not the 4.79. $\endgroup$
    – Pleasant94
    Jul 10, 2020 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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