[pycrypto] getStrongPrime() implementation

[Dwayne C. Litzenberger]

On Wed, Oct 21, 2009 at 12:48:01AM +0200, Lorenz Quack wrote:
> Hi,
>
> as promised here is the implementation of a getStrongPrime() function which 
> generates strong primes as described in
> the paper [1].
> Let me know if such a thing is of interest and if so what could be 
> improved.
> Really any comments are welcome.

Hi Lorenz,

This looks like a great start.  Basing the implementation on the published 
work of academic cryptologists is exactly the right approach.

I do have some comments:

- PyCrypto needs to work with *and* without _fastmath, since the GNU MP 
   library is an *optional* dependency.  We'll need a Python implementation 
   for _slowmath.py before I can apply this patch.

- It looks like you're generating your random numbers using GMP's 
   implementation of the Mersenne Twister algorithm, seeded by rand().  If I 
   applied the patch as it stands, it would introduce a security hole 
   similar to CVE-2008-0166 (the Debian-specific openssl PRNG bug).

   To fix this, we're going to need Python and C implementations  of the 
   Miller-Rabin probabilistic primality test.  These implementations will 
   need to accept a callable Python "randfunc" parameter (like 
   Crypto.Util.number.getRandomNumber does) so they can get random numbers 
   from a cryptographically strong PRNG (i.e. Crypto.Random).

- PyCrypto's *current* isPrime() function needs improvement.  It uses 
   mpz_probab_prime_p, which is a *deterministic* variant of Miller-Rabin 
   (see http://www.trnicely.net/misc/mpzspsp.html).  That's fine for RSA key 
   generation, but totally insecure if you want to validate negotiated 
   Diffie-Hellman parameters, for example.  Do you think you could make 
   isPrime() take advantage of getStrongPrime()'s primality testing code?

- We'll need some unit tests to do some basic sanity checks on the output 
   of this new function?

How much of the above are you comfortable with?  I can probably pick up a 
lot of it if necessary, though in that case it's going to have to wait 
until after PyCrypto 2.1.0 is released.

Cheers,
- Dwayne


-- 
Dwayne C. Litzenberger <dlitz at dlitz.net>
  Key-signing key   - 19E1 1FE8 B3CF F273 ED17  4A24 928C EC13 39C2 5CF7
  Annual key (2009) - C805 1746 397B 0202 2758  2821 58E0 894B 81D2 582E