1

I am trying to encode a message using a public key provided to me by an external site using Python M2Crypto's RSA. Essentially, I am doing something like this:

from M2Crypto import RSA
import os
rsa = RSA.load_pub_key(os.path.join(BASE_PATH, 'external_site.pem'))
rsa_result = rsa.public_encrypt(message, 3).encode('base64')

If I don't use padding when encrypting I receive the error:

RSAError: data too small for key size

I understand why there's an upper limit on the message length (the modulus for the RSA encryption), but I don't understand why there would be a lower limit. Could someone explain this or point me in the right direction to figure it out?

Cosmo
  • 203
  • 3
  • 9
  • I guess that you're not using padding. – CodesInChaos Aug 31 '12 at 23:12
  • True, for this issue I'm not using padding. This is also more about an understanding of the RSAError than whether the encryption is secure or not. – Cosmo Aug 31 '12 at 23:14
  • 3
    You probably need to tell your API somehow to use OAEP padding. If you use padding the error will probably just disappear. Without padding the message length probably needs to be equal to the modulus length. But not using padding has severe security issues, so don't do that unless you really know what you're doing. – CodesInChaos Aug 31 '12 at 23:16
  • CodesInChaos, if you post your answer, I'll close this issue. – Cosmo Sep 04 '12 at 18:17
  • I can't post a full answer, since I don't know the language/library in question. Just write a full answer yourself, based on my comment, with the code you used to fix it. – CodesInChaos Sep 04 '12 at 18:27

2 Answers2

1

There has to be a lower limit in the message too, otherwise, the RSA operation would be a regular arithmetic, not a modular arithmetic.

m \equiv c^d mod(n) where, c = m^e mod(n) and n = pq

m^e > n needs to be true, for a given message m, in other words m needs to be large enough to get reduced by n, or an adversary could simply calculate m = c^1/e and recover the message as it has never been reduced by n. Thus,

\sqrt[e]{n} > m > (n - 1)

needs to be true for every message m.

As an example:

let e = 3, p = 5, q = 11 then n = 55 we won't need d for this example, as the failure happens before getting to that point.

and if we pick our m = 3, such that m ≤ n^1/e or roughly m ≤ 3.803 (in order to not satisfy the above equation)

c ≡ 3^3 mod (55)

but also:

c = 3^3 without the mod present there, and that's the point, mod 55 never did anything. Since e = 3 is told to the public, one can simply calculate 27^1/3 = 3 and learn that the message was m = 3.

Nae
  • 14,209
  • 7
  • 52
  • 79
0

(repeating answer from comment, just to "close")

You probably need to tell your API somehow to use OAEP padding. If you use padding the error will probably just disappear. Without padding the message length probably needs to be equal to the modulus length. But not using padding has severe security issues, so don't do that unless you really know what you're doing.

thoku
  • 1,120
  • 9
  • 27