RSA.generate hangs with some key sizes

[Darsey Litzenberger]

This is quick:

>>> RSA.generate(368, randfunc)

This hangs forever:

>>> RSA.generate(369, randfunc)

See http://lists.dlitz.net/pipermail/pycrypto/2008q3/000013.html

[Darsey Litzenberger (dlitz)]

Fixed in http://gitweb.pycrypto.org/?p=crypto/pycrypto-2.0.x.git;a=commitdiff;h=23dcc92f8edaf1e0ec76e1a4c31d950546c005fa

The problem is that you're trying to generate odd-length RSA keys. The offending code was:

    while number.size(p*q) < bits:
        p = pubkey.getPrime(bits/2, randfunc)
        q = pubkey.getPrime(bits/2, randfunc)

I replaced it with:

    while number.size(p*q) < bits:
        p = pubkey.getPrime(bits/2, randfunc)
        q = pubkey.getPrime(bits - (bits/2), randfunc)

However, notice that factoring n = p*q (and therefore breaking the RSA key) isn't any harder with a 369-bit key as it is with a 368-bit key, because even though q is now 185 bits long, p is still 184 bits.

So although I fixed this bug to prevent the infinite loop, you don't have any reason to use odd-length RSA keys.

[Darsey Litzenberger (dlitz)]

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