[pycrypto] Bug in Crypto.PublicKey.RSA?

[Dwayne C. Litzenberger]

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.

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.

This program should demonstrate:

# ==== BEGIN ====
>>> from Crypto.PublicKey import RSA
>>> from binascii import a2b_hex, b2a_hex
>>>
>>> # Generate a random RSA key (see my note below about RandomPool)
>>> rsaobj = RSA.generate(368, open("/dev/urandom", "rb").read)
>>>
>>> # Generate two messages
>>> M0 = a2b_hex("%02X" % rsaobj.key.n)      # M0 = n
>>> M1 = a2b_hex("%02X" % (rsaobj.key.n-1))  # M1 = n-1
>>>
>>> # Try to encrypt n
>>> rsaobj.encrypt(M0, 0)
Traceback (most recent call last):
   File "<stdin>", line 2, in ?
   File "/usr/lib/python2.4/site-packages/Crypto/PublicKey/pubkey.py", line 50, in encrypt
     ciphertext=self._encrypt(plaintext, K)
   File "/usr/lib/python2.4/site-packages/Crypto/PublicKey/RSA.py", line 181, in _encrypt
     return (self.key._encrypt(plain),)
_fastmath.error: Plaintext too large
>>>
>>> # Try to encrypt n-1
>>> rsaobj.encrypt(M1, 0)
('\x82\x9cp4\x0c@\xcd\t\x1f\x10\xed\x06Z*\x00^\xcf\xf1\xb2\xc0h\'%M+\x92\x91\xf8\xc3TD\xf5\xd4\xa3\r\xf7\x11\xa2\xf9\xec\x01"\x05\xd3\x89@',)
>>> # Success
>>>
# ==== END ====

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

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

     import os
     privkeyA = RSA.generate(keysize, os.urandom)

Or this:

     privkeyA = RSA.generate(keysize, open("/dev/urandom", "rb").read)

Cheers,
 - Dwayne

-- 
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/20080908/e906c0ce/attachment.pgp