I need to generate a 1024 bit ElGamal key on Android, and key generation takes forever (~10 minutes on a Galaxy Nexus), I suspect because it take so long to generate a safe prime.

Is it dangerous for me to use the same safe prime p for all devices using my app?

Where can I find a list of 1024 bit and 2048 bit safe prime numbers?

I'm using it for encryption, and I'm wary about hard-coding a P/G because of the this attack. I know it says only for signatures, but I'm still wary of introducing weakness because I am by no means an experienced cryptographer. The IETF has a list of good Ps to use, but they advocate using G=2, as seen here.

  • $\begingroup$ Any reason why you want to use ElGamal over Diffie-Hellman, DSA or Schnorr signatures? Are you talking about ElGamal encryption or ElGamal signatures? $\endgroup$ – CodesInChaos Nov 30 '12 at 12:21
  • $\begingroup$ What's wrong with G=2? If you can decrypt ElGamal encrypted messages with base 2, you can decrypt ElGamal encrypted messages with any base (assuming you use a safe prime; one with (p-1)/2 prime). $\endgroup$ – poncho Dec 3 '12 at 0:49

With most finite field crypto using a standard group is no problem. I think ElGamal encryption doesn't have any specific requirements for group or generator that plain Diffie-Hellman doesn't have.

So you could look into RFC 2409 Internet Key Exchange or RFC 5114 Additional Diffie-Hellman Groups for Use with IETF Standards for groups.

AFAIK ElGamal signatures have some additional requirements for the generator, so the above groups are probably a bad idea. But I wouldn't use ElGamal signatures in the first place, preferring DSA or Schnorr.


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.