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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ What is the size of the key used ? :) $\endgroup$– BivFeb 12, 2016 at 21:00
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
11
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.
-
3$\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$– ponchoFeb 12, 2016 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$ Feb 12, 2016 at 21:19
-
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, 2016 at 21:31
-
1$\begingroup$ @ShalevKeren Can you explain the number 42 in your calculations? And can you give us a source reference for this formula? $\endgroup$– LiiApr 25, 2018 at 12:08
-
2$\begingroup$ This answer assumes a 160-bit hash, and is thus dated. When using OAEP, the maximum block size depends on the hash. It is common to use SHA-256 with 2048-bit key, and that gives a message block size of 190 bytes, not 214 bytes as it does with SHA-1. Also, there are other modes in wide use. See my answer. $\endgroup$– fgrieu ♦Jan 10, 2019 at 8:28
$\begingroup$
$\endgroup$
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 a message with RSA that's too large for a single RSA block, there are several practices as to how 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.
$\begingroup$
$\endgroup$
1
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.
-
1$\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, 2019 at 8:46
$\begingroup$
$\endgroup$
1
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.
-
$\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, 2019 at 8:36