RSA key generation may need improvement

Bug #408660 reported by Dwayne Litzenberger on 2009-08-04
8
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Python-Crypto
Medium
Unassigned

Bug Description

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.

Dwayne Litzenberger (dlitz) wrote :

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) wrote :

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.

Dwayne Litzenberger (dlitz) wrote :

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

Dwayne Litzenberger (dlitz) wrote :

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

Changed in pycrypto:
status: New → Triaged
status: Triaged → Confirmed
status: Confirmed → Fix Committed
importance: Undecided → Medium
Dwayne Litzenberger (dlitz) wrote :

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

Changed in pycrypto:
status: Fix Committed → Fix Released
Changed in pycrypto:
milestone: none → 2.1.0
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers