2
$\begingroup$

I have often read that using RSA for encrypting bigger size plaintext is not good solution.

What I understand is that using RSA encrytion is best for small plaintext and most effective if it is smaller than 'bit size' of RSA. For instance, if I use RSA with a 2048 bit size then the plaintext that I can encrypt must be smaller than 256 bytes.

Is this true? What happens if the plaintext is bigger than 256 bytes? Why is there a problem with larger plaintext when performing RSA encryption?

$\endgroup$
5
$\begingroup$

Raw RSA operates on unsigned numbers. So any plaintext will have to be converted to an unsigned number first. If you would use raw / textbook RSA then the plaintext of $l$ bits will interpreted as a number $p$ with the same size, usually using big endian interpretation (most significant bit to the left).

Now if you would then perform modular exponentiation using modulus $N$ then the plaintext number will be converted to $p' = p \bmod N$ during the first calculations. When you would decrypt the result then you would get $p'$ back. If the original $p$ was just one or a few bits smaller then you could add $N$ to it until you get the original value (assuming that you can distinguish it from the other possible $p$ values of course).


However, usually raw RSA isn't performed because it is insecure. In that case often PKCS#1 is being used. Now that standard simply says the following,

for OAEP:

If mLen > k - 2hLen - 2, output "message too long" and stop.

and for PKCS#1 v1.5 compatible padding:

If mLen > k - 11, output "message too long" and stop.

So in that sense the common modes for RSA cannot encrypt any message larger than the modulus; actually you also will have to deal with some overhead. And to have CPA security you actually need 8 bytes of randomness or more; otherwise identical plaintext may result in the same ciphertext.

Most libraries will therefore simply return an error or exception if you try to encrypt a large message using RSA.


You can split the message and encrypt the separate parts. This is often expected during study of RSA with very small moduli. But mainly because this is very inefficient this is not the best road to take. You would be better off using hybrid cryptography where a randomly generated symmetric data key is encrypted and used then to encrypt / decrypt the message.

$\endgroup$
  • $\begingroup$ Thx Maarten. Can I also solve this problem if I use for big planetext PGP encryption which use also RSA? Or it is not same and I am not thinking correctly? $\endgroup$ – daniel Jul 19 '17 at 8:43
  • $\begingroup$ PGP RSA encryption uses hybrid encryption. It does actually use a symmetric key as explained at the end of the answer. PGP is a high level protocol / data container format. $\endgroup$ – Maarten Bodewes Jul 19 '17 at 10:11
3
$\begingroup$

If you have an RSA public key $(e, N)$ (in the case of RSA2048 $N$ will be 2048 bits) and private key $d$ then you can only encrypt messages $m$ whose integer representation is less than $N$.

Recall that in RSA encryption is defined as $c = m^e \text{ mod } N$ where $c$ is the resulting ciphertext, and decryption is defined as $m = c^d \text{ mod } N$. The key insight is that decryption cannot produce an $m \ge N$ because of the modulo $N$ operation (the remainder of division by $N$ must be less than $N$). Thus if we encrypt an $m \ge N$ decryption will not produce the correct value.

To get around this it is possible to break $m$ up into chunks that are smaller than $N$, encrypt the chunks, and then recombine the chunks after decrypting to form $m$. For example ($||$ denotes concatenation):

$$m = m_1 || m_2$$ $$c1, c2 = Enc(m_1), Enc(m2)$$ $$m = Dec(c_1) || Dec(c_2)$$

More things to consider beyond this are space that padding will take (unpadded RSA is not secure), and whether you should be using a symmetric cipher like AES which is more suited for encrypting large amounts of data (RSA is much slower than symmetric ciphers and was not designed to encrypt large amounts of data).

Edit: If we do encrypt a message $m \ge N$ the ciphertext $c$ resulting from encrypting $m$ will not decrypt back to $m$. Example using some small parameters:

$$p =17, q = 19, N = p*q = 323, e = 5, d = 173$$ $$m = 400$$ $$Enc(m) = c = 400^5 \text{ mod } 323 = 229$$ $$Dec(c) = m' = 229^{173} \text{ mod } 323 = 77$$

Note that $m \ne m'$ and thus for values $m \ge N$ RSA does not decrypt properly. In fact, for any value $m \ge N$ encrypted via RSA the ensuing decryption will produce $m \text{ mod }N$ instead of $m$ (as is the case in the example: $77 = 400 \text{ mod } 323$).

$\endgroup$
  • 1
    $\begingroup$ Encrypting a value of 0 or 1 value is a brilliantly bad idea of course (and slightly larger values isn't much better). $\endgroup$ – Maarten Bodewes Jul 11 '17 at 16:48
  • $\begingroup$ Ok. But my question was What will happened if I use RSA encrytion for bigger plaintext than RSA bit size... RSA will not encrypt rest of the plain text which is bogger than 2048bits? Or what will happened. I know now what size of plaintext is good for using RSA encryption. But can anybody explain what will happen if I use RSA encrytion for text that is several times bigger than 2048bits? Thx $\endgroup$ – daniel Jul 16 '17 at 17:59
  • $\begingroup$ If you encrypt data bigger than the modulus encryption will still produce output data, but that encrypted data will not decrypt to the correct initial data. I'll edit the answer with an example. $\endgroup$ – puzzlepalace Jul 17 '17 at 3:46

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.