1
$\begingroup$

Trying to implement ElGamal. I have a 1024-bit prime p and now need to find a primitive root g for it. How do you find such a g in an acceptable time? It takes so long, my sage server actually interrupts the calculation.

$\endgroup$
3
$\begingroup$

Here's one easy approach: Pick a large safe prime $p = 2q + 1$ for prime $q$. If you pick $p$ congruent to 1 or 7 modulo 8, then 2 is a quadratic residue modulo $p$, and thus generates a subgroup of large prime order $q$. If you pick $p$ congruent to 3 or 5 modulo 8, then 2 is not a quadratic residue modulo $p$, and thus generates the entire group $(\mathbb Z/p\mathbb Z)^\times$. There are, of course, other choices of generator, which you can use the law of quadratic reciprocity to figure out.

For more general primes $p$, if you know the factorization of $p - 1$, then you can compute generators of all the subgroups independently and combine them with the Chinese remainder theorem. If you look up Schnorr groups, e.g. in DSA parameter generation, you'll find a special case of this for primes $p = kq + 1$ where $q$ is the prime subgroup order of interest: simply pick $h \in (\mathbb Z/p\mathbb Z)^\times$ uniformly at random until you find one with $h^k \not\equiv 1 \pmod p$, and you've found a generator of an order-$q$ subgroup. You can get this by picking a prime $q$ first and varying $k$ until you find a prime $p$ in the desired range.

If you don't know the prime factorization of $p - 1$, then Sage is probably computing it for you! That might take a while if $p - 1$ is 1024 bits long.

(Caveat: I don't know whether you mean Elgamal encryption or Elgamal signature, nor whether either one has any requirements other than the decisional DH assumption, because approximately nobody ever uses Elgamal encryption or signature these days.)

$\endgroup$
  • $\begingroup$ GnuPG supports ElGamal encryption, and keys, people and guidance dating back to the 'RSA patent is eevil' era use it. (But I can see how you in particular might derogate this cause :} ) $\endgroup$ – dave_thompson_085 Dec 27 '17 at 4:13
  • $\begingroup$ GnuPG, as it turns out, uses exactly the algorithm I described for picking $q$, then $k$ and $p$, then $g = h^k \bmod p$! $\endgroup$ – Squeamish Ossifrage Dec 27 '17 at 4:16

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.