RSA key generation may need improvement

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

Bug Description

Anthony Honstain posted this to the mailing list (see

In the generate_py function of lib/Crypto/PublicKey/ , 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:

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:;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

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