[pycrypto] Bug in Crypto.PublicKey.RSA?

[Bill Broadley]

Dwayne C. Litzenberger wrote:
> On Sun, Sep 07, 2008 at 10:48:49PM -0700, Bill Broadley wrote:
>> Shouldn't RSA.generate(keysize, rpool.get_bytes) generate a key that is
>> keysize bits and that can encrypt that many bits?
> 
> No.  RSA with an N-bit modulus can only guarantee encryption of up to 
> N-1 bits.

Ah.  Strange.  Are there restrictions on the size of the modulus?  For instance:
 >>> 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.

> When you generate an RSA key, you get three values:
> 
>     - n: the modulus (when you talk about a 368-bit key, you are 
> actually       talking about a 368-bit modulus)
> 
>     - e: the public exponent (PyCrypto defaults to 65537)
> 
>     - d: the private exponent
> 
> The public key is the pair (n, e), and the private key is the pair (n, 
> d).  To encrypt, you perform the following operation:
> 
>     C = M**e (mod n)
>       = M**e % n        # Python notation
>       = pow(M, e, n)    # Fast Python notation
> 
> To decrypt, you perform the following operation:
> 
>     M = C**d (mod n)
>       = C**d % n        # Python notation
>       = pow(C, d, n)    # Fast Python notation
> 
> Notice how in the decryption, we do a "% n" operation.  This means that 
> whatever the value we decrypt, we will only ever get a value between 0 
> and n-1.  Thus, PyCrypto only lets you encrypt a value between 0 and n-1.

Ah, thanks for the clarification.

>> Then used this piece of code:
>>
>> from Crypto.PublicKey import RSA
>> from Crypto.Util.randpool import RandomPool
>>
>> rpool = RandomPool()
>> keysize=368
>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
> 
> As an aside, don't use RandomPool to generate random numbers.  It 
> doesn't do what you think it does.  See this thread:

Indeed, I'm a big fan of /dev/random and /dev/urandom, linux seems like it was 
one of the first to provide a pretty good /dev/random implementation that uses 
non-visible (at least not trivially visible) sources of entropy.  In any case 
I figured I'd get the example I found working like I expected before I 
improved it.

>     http://lists.dlitz.net/pipermail/pycrypto/2008q3/000000.html
> 
> The next release of PyCrypto will provide an API that does what you 
> want.  Until then, I would do something like this (Python 2.5 only):

Sounds good, I'm actually using the 2.6 beta for development since I want to 
use the new multiprocessing extensions.

>     import os
>     privkeyA = RSA.generate(keysize, os.urandom)
> 
> Or this:
> 
>     privkeyA = RSA.generate(keysize, open("/dev/urandom", "rb").read)

Perfect, thanks.