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

Tue Dec 18 20:16:01 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.
>
> Crypto++ is expecting a strong-prime where p=2q+1, p & q primes.  btw for
> some attacks it is also necessary for q' = (p-1)/2 to be prime.
So, I've got to read through most of Section 4.

I'm not sure what to think of the shortcut of p = 2 q p_1 p_2 p_3 ... p_n.

With p = 2q + 1, we could verify the the [other party's] parameters
and stop processing. I believe the same is true for p = 2 p_1 q + 1
(which is basically p = q r + 1), but I could be wrong.

With p = 2 q p_1 p_2 p_3 ... p_n, we don't have a witness to the
fitness of the key's generated by GnuPG. So we can't easily decide to
stop processing. Maybe I'm being to harsh and I should do the unique
factorization. But in that case, wouldn't be easier to use p = 2q + 1
since I am validating parameters?

Finally, an open question for me (which seems to be the motivation for
the change): how many folks are using, for example, ElGamal shared
decryption and ElGamal shared verification? Was the loss of
independent verification a good tradeoff *if* the feature is almost
never used?

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?
>>>
>>> Jeff

```