#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    4
    Rep Power
    0

    Question Plaintext max size calculation for RSA.


    Hey everybody!

    I am looking for quite some time how can I tell what is the maximum size of plaintext I can encrypt in a single block of RSA (in 2048bit for example)?

    I thought that because the key is 256 bytes, than I can encrypt in a single block 256bytes, but I read a while ago (I don't remember where) in an article that it is not true.


    Can anyone help me get it ???
    Thanks!
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2008
    Location
    Prague
    Posts
    148
    Rep Power
    23
    When using raw RSA, the plaintext can be, indeed, 256 bytes long. However, in a real-life it is a good idea to use some kind of padding (such as [1]) where you "loose" some bytes.

    1. Optimal Asymmetric Encryption Padding, http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    55
    This seems like a simple question -- but as usual where security is concerned, there are several things to be careful about.

    [1] Mathematically, the plaintext (taken as an integer) must be strictly smaller than the RSA modulus. If you choose an n-bit number at random, about half of all n-bit numbers are will be larger -- so for a 2048-bit modulus, you could safely encrypt any plaintext up to 2047 bits in length.

    But the 2048-bit modulus is typically computed as the product of two 1024-bit primes, and could very well have a leading 0 bit (in other words, it is really a 2047 bit modulus). So the safe limit for plaintexts would then be 2046 bits.

    Because computers usually work with data in bytes, and the modulus is 256 bytes long, one could encrypt any 255-byte plaintext, and successfully decrypt it.

    [2] When security is taken into account, the problem gets a little deeper. For example, suppose that sometimes plaintexts could be only a few bytes in length. If (even only once in a blue moon) the plain text can be as short as 4 bytes, an opponent need only compute the encryption of 4 billion plaintexts (remember, anyone can use the public key to encrypt), and do a look-up to decrypt the message: such an attack is very manageable.

    There are more subtle vulnerabilities, in which plaintext (or perhaps even secret key) bits can be leaked, depending on plaintext construction. In particular, it is better that the least significant bits of plaintext not carry protected information.

    As a practical response to this, security-conscious RSA applications usually pad the plaintext. In practice, the plaintext content is usually quite small (16 to 32 bytes), compared to the more than 100 byte modulus, so "using up" some plaintext bytes for padding is no problem at all.

    A standard padding scheme for RSA is the Optimal Asymmetric Encryption Padding (OAEP), see

    http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding

    [3] Even OAEP may be vulnerable, at least in theory. An idea I got from a book by Bruce Schneier is simply to encrypt the plaintext first using a symmetric cipher.

    At first, it may seem senseless to encrypt and decrypt each message two times. But of course, the symmetric encrypt/decrypt is very fast (the RSA operations take much much longer), and the symmetric cipher key need not be secret: its purpose isn't secrecy, but to destroy any structure in the plaintext. Any good symmetric cipher turns the plaintext into statistically random data, and this lack of pattern will defeat any known attacks against RSA.



    So to sum up, choose your content to be at least one byte shorter than the RSA modulus, and before RSA encryption, pad or encrypt the message content.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    4
    Rep Power
    0
    Thanks a lot for your very in-depth explanation!
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    55
    In my previous answer, I wrote incorrectly that leakage of plaintext bits was a vulnerability that motivated padding.

    But I left out a much more important consideration about short plaintexts: if L is the key length in bits, and the public (encryption) exponent is e, then a plaintext whose length is less than L/e is not encrypted at all, because the plaintext raised to the public exponent is less than the modulus!

    For example, if e=3 (a fairly popular, but not very secure choice), and the modulus is 1024 bits long, a plaintext up to 42 bytes long will not undergo modular reduction during the encryption. An adversary doesn't need the secret key to decrypt the message, just a simple cube root!

    Even with e=17 (another popular choice), a 30-byte plaintext will not be encrypted under a "super-secure" 4096-bit modulus. This is one argument for using e=65537, standard for many RSA applications.

    So for goodness' sake, no matter what you do, make sure that your padding scheme guarantees an expansion well beyond L/e bits in length.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    4
    Rep Power
    0
    Wow, I didn't think about that! COOL!
    I wonder how many vulnerable applications there are out there... ;-)

    Thanks a lot (again!), that was very elaborating!
  12. #7
  13. Contributing User
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Sep 2007
    Location
    outside Washington DC
    Posts
    2,576
    Rep Power
    3704
    For casual programming, just make the plaintext be a few bits shorter than the keys "length". Or rather, pick a key length greater than what you need to encipher.

    But no one does it that way. You generate a session key, encipher it with RSA and transmit that. Use the session key to encipher the plaintext using AES or your favorite algorithm.

    This lets you encipher any length of plaintext, you don't use RSA for the text itself, just the key.

    If you are serious, look up things like OAEP padding for your session key.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    4
    Rep Power
    0
    Yeah, that is what I am doing. Also because Asymmetric encryption is much slower.
    But now, thanks to you guys, I get it why it is so important to use OAEP....!

IMN logo majestic logo threadwatch logo seochat tools logo