RSA key generation may need improvement

[Darsey Litzenberger]

Anthony Honstain posted this to the mailing list (see http://lists.dlitz.net/pipermail/pycrypto/2009q2/000107.html):

In the generate_py function of lib/Crypto/PublicKey/_RSA.py , it would
appear to be possible that the the primes p and q can be generated such that
the GCD( 65537, (p-1)(q-1)) != 1 which would result in a unusable key. If
anyone can clarify this it would be greatly appreciated.

[Darsey Litzenberger (dlitz)]

Anyone planning to modify the RSA key generation algorithm should (at least) look at the 1997 paper by Robert D. Silverman, "Fast generation of random, strong RSA primes", available here:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2713&rep=rep1&type=pdf

[lorenz quack (lorenz.quack)]

I believe this bug report is valid.
This is addressed in my patch for "getStrongPrime()".
But in case the patch won't get accepted or doesn't make it into 2.1 here is a smaller patch that just solves the problem at hand.

[Darsey Litzenberger (dlitz)]

That patch actually creates an infinite loop, if the condition (number.size(p*q) < bits) is not met on the first iteration, but I'll fix it. :)

[Darsey Litzenberger (dlitz)]

Lorenz, I think we'll push your getStrongPrime() patch to a future release. This will give us time to do it properly.

I've applied a modified version of your smaller patch:

http://gitweb.pycrypto.org/?p=crypto/pycrypto-2.x.git;a=commitdiff;h=05927c01c80fcf21fd103d166d5fce3da4ae2e51

[Darsey Litzenberger (dlitz)]

We believe this bug has been fixed in PyCrypto v2.1.0, which can be obtained from http://www.pycrypto.org/