2
$\begingroup$

If the input text is divided into a fixed block size for encryption and decryption, what could be the typical block size for RSA algorithm for different size of input like 8 MB, 16 MB, 126 MB and 256 MB?

$\endgroup$
  • 1
    $\begingroup$ What is the size of the key used ? :) $\endgroup$ – Biv Feb 12 '16 at 21:00
1
$\begingroup$

Well this depends on your key size.

But, in general:

  • A 1024-bit RSA key using OAEP padding can encrypt up to (1024/8) – 42 = 128 – 42 = 86 bytes.
  • A 2048-bit key can encrypt up to (2048/8) – 42 = 256 – 42 = 214 bytes.

And so on. It is highly recommended you use at least a 2048-bit key. If you need to encrypt more data just break it down into blocks of these sizes and send them independently (with different keys).

This however can be rather cumbersome (your server will need to have a few sets of keys) and it is best to simply send a 256-bit key (or any other size) for an authenticated encryption scheme and then use that scheme to transfer the rest of your data.

$\endgroup$
  • 2
    $\begingroup$ Actually, you don't really need to use distinct RSA keys; instead, you use a few of the 86 or 214 bytes you have in include a tag that declares that these blocks are the part of the same message, and a 'fragment number' to give the order. However, we'll all agree that encrypting a symmetric key is far cheaper... $\endgroup$ – poncho Feb 12 '16 at 21:15
  • $\begingroup$ But what if someone then encrypts some message saying it's the second message of some message. You would need to add a hash of the message inside (but then, let's say we use SHA-256, we will get an output of 32 bytes), otherwise the server could never be sure that message 2 is actually the second part from that person. So, the space for sending data keeps shrinking. This is just bad on too many levels. $\endgroup$ – Shalev Keren Feb 12 '16 at 21:19
  • $\begingroup$ You mean that this is the second block of some message (that someone else has encrypted)? This can be covered by making the tag (that identifies the message that this block is a member of) be a 16 byte random number that the encryptor picks. No one else (other than the holder of the decryption key) can know what that is, so no one else can generate such a block. $\endgroup$ – poncho Feb 12 '16 at 21:23
  • $\begingroup$ Yes, that would be pretty much the same as using a smaller hash. I was just pointing out that more and more of the space left for the data in each encryption will be even smaller in order to make that work. This would just add an insane amount redundancy it's ridiculous. $\endgroup$ – Shalev Keren Feb 12 '16 at 21:29
  • 1
    $\begingroup$ Or you could of course generate a signature over the data if you have your own trusted key pair available. Using just RSA for encryption is similar to using e.g. CBC, which can be protected using a MAC. $\endgroup$ – Maarten Bodewes Feb 12 '16 at 21:31
2
$\begingroup$

Typically, what we do when we encrypt a large piece of text with RSA is:

  • We select a random symmetric key (perhaps, an AES key)

  • We encrypt that symmetric key with RSA

  • We then use that symmetric key to encrypt the actual message.

So, as far as the RSA algorithm is concerned, it doesn't matter how long the message is. This is called a hybrid cryptosystem.

I suppose one could instead divide the message into segments, and RSA encrypt each segment separately. However, that can't be called 'typical', in fact, I've never heard of anyone foolish enough to actually do that in practice.

$\endgroup$
  • $\begingroup$ "I've never heard of anyone foolish enough to actually do that in practice." Look at what typical CS students (and the same ones let diving on their own into the industry) do when given a Java or Android API! $\endgroup$ – fgrieu Jan 10 at 8:46
0
$\begingroup$

It is seldom a good idea to encipher more than one block with RSA alone, thus the question is moot. One should use hybrid encryption, where the bulk of the data is symmetrically enciphered with a random key which confidentiality is obtained using RSA with a single block.

When indeed enciphering with with multiple RSA blocks, there are several practices as to what the block size (or maximum block size) $m$ in byte relates to the bit size of the public modulus (called the key size, e.g. $n=2048$ bit). The most common ones, from most to least acceptable, are:

  • When using RSAES-OAEP with a hash of $h$ bytes, $m=\left\lceil\dfrac n8\right\rceil-2h-2$. For example, RSA-2048 with SHA-256 (RSA/ECB/OAEPWithSHA256AndMGF1Padding) allows $m=2048/8-2\,(256/8)-2=190$ bytes.
  • When using RSAES-PKCS1-v1_5 (RSA/ECB/PKCS1Padding), $m=\left\lceil\dfrac n8\right\rceil-11$.
    It is recommendable to not use RSAES-PKCS1-v1_5, as it lacks a mathematical security argument of reducibility to the RSA problem, and tends to be more susceptible than RSAES-OAEP is to padding oracle attacks, where a device using decryption is remotely abused into deciphering or signing anything.
  • When using no padding (textbook RSA, RSA/ECB/NoPadding), $m=\left\lceil\dfrac n8\right\rceil-1$ or $m=\left\lceil\dfrac n8\right\rceil$ depending on implementation. In the later case, there are a some values of the plaintext block that can't be enciphered and deciphered back to their original value (including a block with all bytes 0xFF).
    In both cases, the practice is unsafe unless message blocks include significant randomness: in particular, any guess of a plaintext block is trivially verified, and it is common that a device using decryption can be remotely abused into deciphering or signing anything.

RSAES-OAEP and RSAES-PKCS1-v1_5 are described in e.g. RFC 8017.

$\endgroup$
0
$\begingroup$

It depends on the key size and the selected padding. The max block size is (in bytes): key_size_in_bytes - padding_margin

The padding margin is as follows:

  • RSA/ECB/PKCS1Padding, 11
  • RSA/ECB/NoPadding, 0
  • RSA/ECB/OAEPPadding, 42 // Actually it's OAEPWithSHA1AndMGF1Padding
  • RSA/ECB/OAEPWithMD5AndMGF1Padding, 34
  • RSA/ECB/OAEPWithSHA1AndMGF1Padding, 42
  • RSA/ECB/OAEPWithSHA224AndMGF1Padding, 58
  • RSA/ECB/OAEPWithSHA256AndMGF1Padding, 66
  • RSA/ECB/OAEPWithSHA384AndMGF1Padding, 98
  • RSA/ECB/OAEPWithSHA512AndMGF1Padding, 130
  • RSA/ECB/OAEPWithSHA3-224AndMGF1Padding, 58
  • RSA/ECB/OAEPWithSHA3-256AndMGF1Padding, 66
  • RSA/ECB/OAEPWithSHA3-384AndMGF1Padding, 98
  • RSA/ECB/OAEPWithSHA3-512AndMGF1Padding, 130

However, as Shalev Keren answered, for performance reason, usually RSA is not used for encryption of data but for encryption of keys.

$\endgroup$
  • $\begingroup$ Depending on library, what the answer calls the padding margin is 1 or 0 for RSA/ECB/NoPadding. In the later case, not all messages can be deciphered. $\endgroup$ – fgrieu Jan 10 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.