# [cryptography] ElGamal Encryption and Signature: Key Generation Requirements?

Tue Dec 18 17:17:19 EST 2012

```On Tue, Dec 18, 2012 at 5:52 AM, Adam Back <adam at cypherspace.org> wrote:
> The reference to Lim Lee is in section 4 of this paper on discrete og
> attacks (and how to generate primes immune to them):
>
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5296
>
> They recommend that the p_i values are bigger than q.  Ie in a 1024 bit p,
> 160 bit q, then all of the p_i values making up n should be > 160-bits,
> where p = 2qn+1 where n = p_1 * ... * p_k and in this case you need
> (1024-160)/k > 160 so k = 5 and |p_i| = 172.
>
> For sub-group based crypto systems q is distinct from and not a p_i because
> the crypto system uses the subgroup q (eg DSA etc), and there q has to be of
> a specific size ie relating to a hash output size for security reasons,
> where q < 2^out where out size of the hash output in bits.
I'm still reading through the paper (my theoretical math skills are
too old and mostly forgotten), but it seems subgroup order should
still be observed due to Schnorr and subgroup/confinement attacks.
That is, we can't pick and choose the instance problem. Discrete Logs
have two problems (logs in Z_p and logs in cyclic subgroup q).

Jeff

> On Tue, Dec 18, 2012 at 01:15:05AM +0100, Adam Back wrote:
>>
>> Those are Lim-Lee primes where p=2n+1 where a B-smooth composite (meaning
>> n
>> = p0*p1*...*pk where each p0 is f size < B bits.
>>
>>
>> http://www.gnupg.org/documentation/manuals/gcrypt/Prime_002dNumber_002dGenerator-Subsystem-Architecture.html
>>
>> So if Crypto++ is testing if the q from p=2q+1 is prime, its right -- its
>> not!  But its not broken so long as B is large enough.  If B is too small
>> its very broken.
>>
>>
>> On Mon, Dec 17, 2012 at 06:43:15PM -0500, Jeffrey Walton wrote:
>>>
>>> Hi All,
>>>
>>> This has been bugging me for some time....
>>>
>>> When Crypto++ and GnuPG interop using ElGamal, Crypto++ often throws a
>>> bad element exception when validating the GnuPG keys. It appears GnuPG
>>> does not choose a q such that q - 1 is prime (in the general form of p
>>> = qr + 1). That causes a failure in Crypto++'s Jakobi test.
>>>
>>> I could not find a paper stating q - 1 non-prime was OK (on Google and
>>> Google Scholar). I would think that q - 1 prime would be a
>>> requirement, since some algorithms run in time proportional to q - 1
>>> (for example, Pollard's Rho).
>>>
>>> What are the key generation requirements for ElGamal Encryption and
>>> Signature schemes?

```