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

Adam Back adam at cypherspace.org
Wed Dec 19 04:00:25 EST 2012


Yep, I see your track from the start of the thread was to understand why
validation was failing.  And validation is good, many protocols can be
broken unintentionally or plausibly deniably sabotaged due to coding error
on one side of the protocol only.  I think it would be easily possible to
encoe the p_i values in the public key format and so run primality tests on
them.  (Format changes... yuck).  Also as p_i are really small perhaps you
could factor n = p_1 * ... * p_k moderately quickly.  Its been quite a while
since factoring a 384 bit key was a big deal.  

But I imagine most commonly these elgamal keys are 2048 bits or more and q so that
probably is heading towards the computional in feasibility, so the only real
chance is if people would communicate the p_i values (or the seed for
re-generating them, perhaps.)

I presume like key sizes will be (from DSA) (|p|,|q|) = (1024,160),
(2048,224) (2048,256) (3072,256) and factoring a 512-bit number is still
painful.

Adam

On Tue, Dec 18, 2012 at 08:50:11PM -0500, Jeffrey Walton wrote:
>Thanks Adam,
>
>> With Lim-Lee as you maybe saw in the paper you just generate a few extra
>> small p_i values n of them where only k needed, then try permutations C(n,k)
>> untl you find one for which p = 2q*p_1*...p_k is prime.  As the p_i are
>> small they are fast and cheap to generate.
>So, that's the "good case." How about the "bad case(s)"? What happens
>when the bad guy generates or influences the supposed Lim-Lee prime?
>He/she will only be caught if someone performs the unique
>factorization (versus the previous primality test).
>
>I think the paper's conclusions says it all (Section 5): "...
>therefore, our attack can be easily prevented if the relevant protocol
>variables are properly checked." It appears many folks did not
>validate parameters - presumably due to efficiency/speed/laziness -
>and now everyone is penalized (even the folks who were validating
>parameters).
>
>Something easy has been made hard. Folks who specialize in these types
>of analysis are probably pissing their pants because they are laughing
>so hard.
>
>Jeff
>
>On Tue, Dec 18, 2012 at 8:29 PM, Adam Back <adam at cypherspace.org> wrote:
>> Well one reason people like Lim-Lee primes is its much faster to generate
>> them.  That is because of prime density being lower for strong primes, at
>> the sizes of p & q for p=2q+1 and you need to screen both p & q for
>> primeness.
>>
>> With Lim-Lee as you maybe saw in the paper you just generate a few extra
>> small p_i values n of them where only k needed, then try permutations C(n,k)
>> untl you find one for which p = 2q*p_1*...p_k is prime.  As the p_i are
>> small they are fast and cheap to generate.
>>
>> Adam
>>
>>
>> On Tue, Dec 18, 2012 at 08:16:01PM -0500, Jeffrey Walton wrote:
>>>
>>> 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?



More information about the cryptography mailing list