python crypto rsa issue

Question

There seems to be a problem with RSA encryption/decryption in python Crypto package:

from Crypto.PublicKey import RSA
from os import urandom
def test(keylen, datalen, rand_len):
    k = RSA.generate(keylen)
    ok, fail = (0,0)
    for i in range(1000):
        a = urandom(datalen)
        if a == k.decrypt(k.encrypt(a, urandom(rand_len))):
            ok += 1
        else:
            fail += 1
    return ok, fail

No matter what combinations of keylen/datalen/rand_len i do i can't get it to decrypt 100% of times. Is it only my installation of Crypto?

>>> test(1024,128,0)
(853, 147)
>>> test(1024,127,0)
(996, 4)
>>> test(2048,127,0)
(994, 6)

Answer 1

Each decryption failure occurs for input strings beginning with NUL (\x00'). If you compare the original string with the decrypted version you will notice that the original begins with '\x00' and that the recovered version will have the first byte removed, e.g.

>>> a = '\x00\xa4\x8aE\xb5,\x1a\x95)Q'
>>> b = k.decrypt(k.encrypt(a, urandom(rand_len)))
>>> a == b
False
>>> len(a)
10
>>> len(b)
9
>>> a
'\x00\xa4\x8aE\xb5,\x1a\x95)Q'
>>> b
'\xa4\x8aE\xb5,\x1a\x95)Q'

You'll notice that, other than the first byte, a and b are the same.

Obviously NUL is important for C string termination, but I am surprised that it fails in this way rather than simply treating the original string as an empty string. I guess that the library just skips over any leading NUL and encrypts with the remainder of the string.

Answer 2

try this:

from Crypto.PublicKey import RSA
from os import urandom
def test(keylen, datalen, rand_len):
    k = RSA.generate(keylen)
    ok, fail = (0,0)
    for i in range(1000):
        a = urandom(datalen).lstrip(b'\x00')
        if a == k.decrypt(k.encrypt(a, urandom(rand_len))):
            ok += 1
        else:
            fail += 1
    return ok, fail

explanation:

pycrypto operates on numbers, not on bytes internally, that means leading zeroes will not be considered. encrypt and decrypt are very low-level.

for signing you should use the Signature package (pycrypto2.5+), which takes care of correctly padding you message. otherwise you have to pad your message yourself.