[pycrypto] Bug in Crypto.PublicKey.RSA?

[Dwayne C. Litzenberger]

On Tue, Sep 09, 2008 at 08:24:05AM -0400, Dwayne C. Litzenberger wrote:
>> >>> keysize=368
>> >>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
>> [ finishes in close to zero time ]
>> >>> keysize=369
>> >>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
>> Hangs forever.... well at least 10's of minutes.
>
> I filed a bug report:
>
>     https://bugs.launchpad.net/pycrypto/+bug/268101

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.

-- 
Dwayne C. Litzenberger <dlitz at dlitz.net>
  Key-signing key   - 19E1 1FE8 B3CF F273 ED17  4A24 928C EC13 39C2 5CF7
  Annual key (2008) - 4B2A FD82 FC7D 9E38 38D9  179F 1C11 B877 E780 4B45
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
Url : http://lists.dlitz.net/pipermail/pycrypto/attachments/20080917/f5055788/attachment.pgp