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.

As generator $g$ is use in DH how to find combination of prime $p$ and $g$? eg: if we choose $p=23$ its generator is $7$ (given in book) how to find it?

share|improve this question

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 it's 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.

share|improve this answer

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.

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.