[pycrypto] getStrongPrime() implementation
Dwayne C. Litzenberger
dlitz at dlitz.net
Sun Oct 25 20:52:52 CST 2009
On Wed, Oct 21, 2009 at 12:48:01AM +0200, Lorenz Quack wrote:
> as promised here is the implementation of a getStrongPrime() function which
> generates strong primes as described in
> the paper .
> Let me know if such a thing is of interest and if so what could be
> Really any comments are welcome.
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.
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
More information about the pycrypto