[pycrypto] PyCrypto ElGamal code questions/comments

[Yaron Sheffer]

Hi,

I've been going over the code and I have a few questions. I realize that 
only few people are using this code, but hey, if it's good enough for a 
recent CVE :-)

  * The documentation of "generate" says that randfunc returns X random
    bytes. I think this should be bits.
  * 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.
  * 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.
  * An important check is missing: the message M needs to be less than
    p, both when signing and certainly when encrypting it.

Thanks,

     Yaron