1
$\begingroup$

As far as I understand, there isn't an easy algorithm to find the generator of a cyclic group used in DH Key exchange. Is it true? Given a large prime number like, e.g. 0x614423aaf0d10001f7d7, how can a generator of its group be computed (and checked that's true)?

$\endgroup$
4
$\begingroup$

As far as I understand, there isn't an easy algorithm to find the generator of a cyclic group used in DH Key exchange. Is it true?

No, it is easy, as long as you know the factorization of $p-1$.

A value $1 < g < p$ will be a generator to a prime $p$ iff for every prime factor $q$ of $p-1$, we have $g^{(p-1)/q} \not\equiv 1 \pmod p$

And, there will be enough generators (specifically, $\phi(p-1)$ of them) that just randomly selecting $g$ randomly, and then testing them by the above process is quite doable.

So, isn't factoring $p-1$ a hard problem? Well, it wouldn't be for the 79 bit value you picked, but that's far too small to be used in a Diffie-Hellman exchange, it is generally accepted that you need at least a 2048 bit prime. So, for a value $p-1$ that size, how do we factor it?

Well, what we don't do is select a large random prime $p$ and try to factor it; instead, we build a value $p-1$ with a known factorization, and check that $p$ happens to be prime. One common way of doing this is to search for $p$ such that $(p-1)/2$ is also prime (this is known as a "Sophie Germain prime") and hence $p-1$ has a known factorization.

That said, you said you were doing this for Diffie-Hellman; generally, for DH, you don't want $g$ to be a true generator (as that'll leak, at the very least, the lsbit of your private exponent); instead, we more usually select $g$ such that the order $q$ is a large prime factor of $p-1$; if we know the size of the subgroup we want, we can stir that into the factorization of $p-1$ when we build it; either by:

  • Using a Sophie Germain prime (and so $p-1 = 2q$), if $p \equiv 7 \bmod 8$, then $g=2$ will generate the size $q$ subgroup.

  • Or by picking a prime $q$ perhaps 256 bits long, and then searching for a (possibly composite) value $r$ such that $p = 2rq + 1$ is also prime; we can find our generator by selecting an arbitrary $h$ and setting $g = h^{2r} \bmod p$; if $g \ne 1$, then that's our generator.

All that said, I expect that you don't know enough number theory to go through that yourself. For decent DH parameters, I send people to this document for precomputed groups; I would recommend the "2048-bit MODP Group" settings.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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