[pycrypto] PyCrypto ElGamal code questions/comments

[Legrandin]

Hi Yaron,

Some comments inline:


>  * The documentation of "generate" says that randfunc returns X random
>    bytes. I think this should be bits.
>

I am not 100% sure, but a common idiom in pycrypto is:

"
if randfunc is None:
     randfunc = Random.new().read
"

so randfunc(N) returns N bytes of full entropy.

 * The "generate" function is way too conservative. We construct p as
>    2*q+1, where both p and q are prime. This makes p a classic "safe
>    prime". It also makes two of the checks redundant: g cannot divide
>    p-1, because only 2 and q divide it. g cannot be 2, and most likely
>    will not be q during the lifetime of the universe. I believe that
>    similarly, g**-1 cannot divide p-1, but my algebra skills are too
>    rusty to prove it.
>

I contributed to that part with a patch. My intention was actually to list
in the loop
as many criteria as possible that a generator safe for both Elgamal
encryption and Elgamal signatures (because .generate() does not know how
the key will be used) must fulfill.

It's true they are redundant in practice, but I think it's good to leave a
track behind with the general conditions that one must check, regardless of
how the domain parameters are computed.

 * For the same reasons, there is no need for the loop when
>    constructing K (the secret parameter), e.g. on line #342. You just
>    need to ensure that it is an odd number, otherwise its GCD with p-1
>    would be 2. So choose a random t, 2 < t < q-1, and let K=2*t+1. No
>    need for a loop or for the GCD calculation.
>

In the _sign() method I see only a loop to ensure that residues remains in
the range 0..p-1. The loop does not contribute to GDC computation.


>  * An important check is missing: the message M needs to be less than
>    p, both when signing and certainly when encrypting it.
>

True. Note that M must not the message when signing with PyCrypto's
Elgamal. It must be really be the cryptographic hash of the message.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.dlitz.net/pipermail/pycrypto/attachments/20120805/4792d29c/attachment.html>