[pycrypto] getStrongPrime() implementation
Dwayne C. Litzenberger
dlitz at dlitz.net
Mon Oct 26 20:56:21 CST 2009
On Mon, Oct 26, 2009 at 10:21:36AM +0100, don at amberfisharts.com wrote:
>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
>> 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.
Yes, that makes sense.
>> If I applied the patch as it stands, it would introduce a security
>> 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?
>> 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
Ok, ignore what I wrote there. I can't think of a good way of explaining
what I mean right now. There are a few concepts that are intertwined.
>> - 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
>> 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
Yes, I agree. This would only be useful once getStrongPrime() is modified
to use a proper random number source.
[I should correct the terminology I used in my previous email:
mpz_probab_prime_p doesn't implement a deterministic test (as I suggested);
it implements the probabilistic Rabin-Miller test deterministically. As a
result, the theoretical guarantee normally provided by the Rabin-Miller
probabilistic test (at most a 25% false positive probability per iteration)
>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
>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.
Yes. Of course, for crypto, we really only need to worry about primes
larger than 2^2047 (10^616). Does Baillie-PSW offer a theoretical maximum
probability of error like Rabin-Miller does?
>> - 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?
Basically, I just want to test for obvious coding errors. For example, we
could check for "primes" that are even, or wrong sized primes (e.g if you
ask for a 2048-bit prime and get a 2047-bit number instead). We could also
test a new isPrime() by including some pseudoprimes that currently fool
isPrime (Thomas R. Nicely has generated some).
>> 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.
Yes, that sounds good.
>Concerning the Unittests. I guess I could moc up some initial tests but I
>don't know what exactly you have in mind.
Again, I'm not looking for a lot here. Just something that exercises all
of the code and does some basic checks.
>further more I would like a comment on whether I got the thing with the
>public exponent e right.
That's the part I don't understand, and why I asked for help with this in
the first place. I unfortunately don't know very much about the math
behind RSA. :-/
I'll look at it again this weekend if I have time and I remember.
Also, thanks for posting your earlier test results.
>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.
Thanks for mentioning that. It helps me keep things straight.
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