[pycrypto] getStrongPrime() implementation

[Dwayne C. Litzenberger]

On Tue, Oct 27, 2009 at 12:28:11PM +0100, don at amberfisharts.com wrote:
>Yes. I realized this yesturday when I looked at the gmp code. Do you have 
>any idea why they did go for the non-deterministic version (and not seed 
>the PRNG)?  I think the PRNG bug you mentioned earlier can't have anything 
>to do with it because a potential attacker would have no influence on when 
>the test is performed and thus when (and with what seed) the PRNG is 
>seeded.

In the getStrongPrime() case, there are two steps that cound use a CSPRNG:

     1. Generate a candidate number

     2. Test if the number is composite using Rabin-Miller.  If so, go to 
        step 1.

In the Diffie-Hellman parameter negotiation case, there are similar steps:

     1. Alice: Generate a candidate number

     2a. Alice: Test if the number is composite using Rabin-Miller. If so, 
     go to step 1.

     2b. Bob: Test if the numeber is composite using Rabin-Miller.  If so, 
     abort the protocol.

You lose security if an attacker can guess the random numbers used in steps 
1 or 2b.  As you pointed out, guessing does not help the attacker in steps 
2 or 2a.

Given the difficulty we're having in communicating exactly what we're 
talking about, we can't expect *users* of PyCrypto to get this right.  
Thus, we will simplify things immensely if all steps use an unpredictable 
random source, i.e. Crypto.Random.

>Baillie-PSW is just a combination of (as I understand it) a single 
>Rabin-Miller-Tests followed by a strong Lucas-Selfridge test.
>
>There seems to be no pseudoprimes below 2^64 (not yet confirmed) [1] and 
>others seem to estimate that there are non below 10000 [2].
>
>As that may be I couldn't find a mathamatical proof of any boundary so if 
>we are worried about that we could still do n Rabin-Miller test to get the 
>mathamaticly proven probability of 4^{-n} and then do a Lucas test for 
>better *assumed* probability.
>
>There are some concerns that the Lucas test might not be computationally 
>feasable for large numbers [1].
>
>So for now this is just an option one can take a look at once the other 
>parts are in place because it wouldn't replace anything but rather extend 
>it.

Ok, sounds good.

>BTW, is there a certain Python version you want to support?
>I ask because yesturday I caught myself writing "x = x if y else z". I'll 
>replace that particular line with the equivalent "if ... else ..." 
>construct, but it made me wonder if there are any further constraints.

Yes.  Right now, PyCrypto supports Python 2.1 through 2.6.

>OK, so I'll work on these (supporting randfunc, probabilistic 
>Rabin-Miller-Test, python versions and unit tests) and send in a patch 
>when I think it's review worthy.
>I might even get it done until the weekend. let's see about that.

Awesome.  Thank you very much for this.

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