ElGamal and Schnorr groups

As I gather, a normal practice for choosing a cyclic group for ElGamal key generation is to find a safe prime $p$ and use a multiplicative cyclic group with modulus $p$ and order $q = (p-1)/2$. However, generating safe primes of a large length can be quite time-consuming. Would it be safe to use a Schnorr group as an alternative?

If there is no safe way, what minimum size can I use for a safe prime so that it would be both secure and not terribly long to choose?

1 Answer

Note the obvious: for Elgamal signature generation you must share parameters between users. If I (re-)read Elgamal encryption then it seems to me that parameter $p$ or $q$ (the safe prime) need to be shared in advance as well. Even though the generation of safe primes may be time consuming, you don't need to do this for each signature generation or decryption - the parameters may be static.

As for the key size, the key size of the prime must be about as large as those for RSA and DH keys. This is because the security is related to the hardness of the Diffie-Hellman problem. This means that you may look up the sizes on sites like keylength.com and look for the sizes required for "Discrete Logarithm" or the sources, for instance of NIST (US) or ECRYPT II (Europe), it references.

So there is no need to use primes that have additional properties over those required for Elgamal signature generation or encryption. Any generation of large primes will take large amounts of time compared to encryption/decryption. If you want efficiency then you can share (named) parameters.

• Thank you very much, this answers all of my questions except for one - are there any real security disadvantages of using a group with a Schnorr subgroup instead of a safe prime (e.g. $p = q*R + 1$ instead of $p = q*2 + 1$)? – Mints97 Jan 24 '15 at 11:20
• @Mints97 You mean apart from breaking the security reduction? I may not create a good enough answer on it, as I'm still in the process of upgrading my math skills. Note that if you are worried about efficiency you could switch to Elliptic Curve primitives and use a named curve (e.g. using ECDSA and ECIES) which deploy schemes with similar properties to El-Gamal. – Maarten Bodewes Jan 24 '15 at 11:30
• Note: my above answer merely shows why it doesn't matter that it takes a long time generating, it doesn't give a mathematical reason why Schnorr groups cannot be used. Mints97 feel free to change the accept if somebody does give a mathematical reason. – Maarten Bodewes Jan 24 '15 at 11:37
• Maybe I will, but your answer has been extremely useful anyway. Thanks again! =) – Mints97 Jan 24 '15 at 11:47