[pycrypto] getStrongPrime() implementation

[don at amberfisharts.com]

Hi Dwayne,

On Sun, 25 Oct 2009 22:52:52 -0400, "Dwayne C. Litzenberger" <dlitz at dlitz.net> wrote:
> - 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.

Yes, I understand and agree. I think I could do this. I just wanted to wait for some feedback to see if I'm going in the right direction before I invest more time. 

> - It looks like you're generating your random numbers using GMP's
>    implementation of the Mersenne Twister algorithm, seeded by rand().
Yes that is true

>    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).
OK, I'm not sure I see the problem. Is it that one can guess a timerange in which the program has been started and thus determine a small set of possible seeds which then can be brute-forced? Or is it something else?

>    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).
I'm confused. It sounds like this paragraph is in part referring to the next point.
I don't see what the primality testing has to do with the PRNG problem.
The second point (supporting a "randfunc" parameter) however I could implement. 

> - 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?
That won't do any good. The primality testing in getStrongPrime is also deterministic. It uses a sieve (the base is the first 10000 primes) and then some rounds (currently 25 as suggested in the paper) of mpz_probab_prime_p(). 
So I guess what you are suggesting is that we implement our own non-deterministic Rabin-Miller test (again we would need a C and python version). That might not be a bad idea because right now we have some redundancy in that mpz_probab_prime_p also uses a sieve (with a smaller base) before doing the Rabin-Miller tests. We could then avoid that overhead. 
Maybe one could then later replace/extend it to a Baillie–PSW primality test which has no pseudo-prime numbers up to at least 10^15.

> - We'll need some unit tests to do some basic sanity checks on the output
>    of this new function?
I agree. but what do you have in mind exactly? do you want to do an *exact* primality test? 

> 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.

The python implementation of getStrongPrime() should be straight forward so I can do that. 
Also taking the additional randfunc parameter shouldn't be to hard.
I'm not so sure about implementing a Rabin-Miller test. I don't know exactly how it works and would need to make some research first. but from what I read so far it shouldn't be to hard to implement. But you said that for RSA the current deterministic approach is fine so this is for a future version which includes a Diffie-Hellman keyexchange.
Concerning the Unittests. I guess I could moc up some initial tests but I don't know what exactly you have in mind. 

further more I would like a comment on whether I got the thing with the public exponent e right.

sincerely yours
//Lorenz


P.S.: I'm not a national, citizen nor a resident of the USA. I gladly put my current, past and future contributions to PyCrypto into the public domain and I agree to the terms listed under the "PyCrypto Code Submission Requirements - Rev. C".  The code I write is not of USA origin.
I think the paper the code was based on might be of USA origin but I don't think that is a legal problem.
I hope that takes care of the legal stuff.