some rsa keys only produce 255 bytes when encrypting spaces

[Roman Tetelman]

i was writing some tests to help get rid of stray strip()s where they shouldn't be, and ran into this:

 def testSpaces(self):
  keys = [RSA.generate(2048),
   #roughly one in 20 randomly generated keys seem to always return 255 bytes instead of
   #256 when encrypting strings consisting only of the space character
   #this is one of them cherry picked to make the issue reproducible
   RSA.importKey("""-----BEGIN RSA PRIVATE KEY-----
MIIEpQIBAAKCAQEAtqFtstUW6zXYMiZnnwDLzRuxCbHGS0J5g0/KlhIbfb1JsssN
b8j8K/9AFjvAdnXaF1GyHlrlEUfNqf1n1GK5hulYluHHdh371v8kq6YYYz5QBDdd
A3iZjW+MN8j+G3BpRSV+o0e9vKLoubz3TKx7WZDtcnR+Oc+35PaiLC2EDGIGLmrk
HcKmOED3I+rzcdd6FEcBQx4IRVwXAj2MTfP4yd8w4hT0kEPD7HSm6UKI+jmjgb/y
LhPqGIsM8oSQ9/zGhCX2C6G8sTydEHiYj5lmWYN5LCWIcjcQnHFXA/KkmDe8cIz+
0XcicTi/PRcrRQHlX2h4MXuGvQQfc5wuKDT1KQIDAQABAoIBAQCNM3ZLI/GaXYEQ
FR1clBL+PAC/DBHSMk0ct15cdReIOgd3EwMKgIxnv+vexMfjTu8VxHZAfepJWAis
+12BmerzYgq6bUn4CuqhqZbCl6KXaKAZAm0Jt/6QmcQBhYbh1CGv8nNc7qTF6fah
VHanc1vTPfg329WUAQOfJQjxuyczInA4OuwKGBxT+BLaxQ70iB+Y99oBm91JP54/
Xru5PHS718bxgzWY7R0M9XOFseMMMli5LUtUfIziVPgi/KI1vmA68F1+mfpkS6hW
hYethCFWSlFf6IuOP/mFabHJbFKRV1E030u+z9RLj3LYQ/0I5NesksKCZOg6XfUm
jc3n+TW5AoGBANFBknYUzGQNiCOCaTLupVb51dmwnB/irgtnBRpJTGblk0tppD1t
g7tCnAbC9eIgxwolgRWs8ClnOv9e0VK0B8/+HZZVl7Tn8F0ILf08VFL7kx717G8l
sB46SaYBdKoZ+LEGLdP09kZv79mUcVx872XNfv1s445qbGc8Orc4ZbMLAoGBAN9t
Qk3wCxJhv+VPRqv7ZQsem56JVUgFFiU8mJhgGavRlIY1OUaj+/6hFT2akN/PAKer
vQPDDXR9SO1LAPjLYDFv1HRKDdMhP36zQHXxbY96x3X1OHcGcartQkfbCw8WiIMq
BeulfGhkK24XrtMXfCOXPCZg7MEqUJXtyLs0XRkbAoGAYiknYlr5UkoCvd2UKb9H
Mli6V4cAhfiY+mJWQ3F09KPnB65DzEkOTY6+kHFuVKhZlknnltpsQo/ZXigFe41W
SNyE1pvKMaPH3mxS3oMpb0/yQMjOI4mDZ3qiR8xRBOZwAeLLJq23xW0HD4MR9nfo
+VF/q7Qjvw/vUDIxvPcoxecCgYEAwv9qtPbh0uM5RftQpN0+LNxD2bPmmHrH/yvJ
yoNlJE5AIHnnST3puyv/i8qQ0qSp36zFxLjBz39g3KlvabSmeb8uX2gadMA52Gy9
v7I8etMfrlWdOFSJdDKqfGgyWLLD5iYREL9Xuwxh0y4cSOPgVnex6ZUCTPyPZKsp
XCmxby0CgYEAm1Nu2wtwMSTw3eDkDl3oWSHnFss3hcU40pJpkfRDROIKQBykBEuB
X8xkZ2VdQ+O++8cML8rPxMr4AFIHQuyERL1+5GNbqiXt9nGASe8+SplhwqhjLJOk
9kJ6RPcK6eMQ/3XFJ+BSaCsr1e6ojbPRMXGOzuJm3GyOjkzCF5IC9V0=
-----END RSA PRIVATE KEY-----"""),
   ]
  for key in keys:
   clear = ' ' * 10

   ciphertext = key.encrypt(clear, os.urandom)
   self.assertEqual(clear, key.decrypt(ciphertext))
   self.assertEqual(len(ciphertext[0]), 256, "%d != %d\nkey:\n%s" % (len(ciphertext[0]), 256, key.exportKey()))

[Roman Tetelman (kevlarman)]

turns out it happens with any string, when converting from a python long to bytes any leading null bytes end up missing.
(encrypting any given string with 256 newly generated keys will reliably produce at least one that demonstrates this issue)

[Darsey Litzenberger (dlitz)]

Why do you expect it to do anything different? The Crypto.PublicKey.RSA module is just the RSA primitive, so it returns the bare result of m**e (mod n). If you pass it a string, it runs long_to_bytes on the result before returning it.

Many values return even fewer bytes:

    >>> k = RSA.generate(2048, e=5)
    >>> k.encrypt("\x00", "")
    ('\x00',)
    >>> k.encrypt("\x01", "")
    ('\x01',)
    >>> k.encrypt("\x02", "")
    (' ',)
    >>> k.encrypt("\x02", "")
    (' ',)
    >>> k.encrypt("\x03", "")
    ('\xf3',)
    >>> k.encrypt("\x04", "")
    ('\x04\x00',)
    >>> k.encrypt("\xff", "")
    ('\xfb\t\xf6\x04\xff',)

and it works with longs, too:

    >>> k.encrypt(2L, '')
    (32L,)
    >>> k.encrypt(255L, '')
    (1078203909375L,)

You really shouldn't be using the RSA module directly. That's called "Textbook RSA", and is insecure. You at least want to be using PKCS#1 padding, which is provided in the Crypto.Cipher.PKCS1_OAEP module. That will at least give you IND-CCA2 security, however, your messages will still be length-limited to less than the size of the modulus. What you really want to do is to use a higher-level encryption standard like OpenPGP or Keyczar (http://www.keyczar.org/), rather than trying to invent your own cryptographic message format.

[Roman Tetelman (kevlarman)]

because openssl rsa produces the leading zero(s) with the same key. as far as padding, in my application there are much faster ways to verify a plaintext than running rsa on it (and the plaintext is a sufficiently long string from /dev/urandom to be unguessable anyway)

[Darsey Litzenberger (dlitz)]

Hm. Ok, I agree in principle; I wonder if this will break for some users, but probably not.