2
$\begingroup$

Good morning!

This may be a stupid one, but still, I couldn't google the answer, so please consider answering it in 5 seconds and gaining a piece of rep :-)

I'm not doing well with mathematics, and there is a task for me to implement the RSA algorithm. In every paper I've seen, authors assume that the message $X$ encrypted is less than the module $N$, so that $X^e\quad mod\quad N$ allows to fully restore $X$ in the process of decryption.

However, I'm really keen to know what if my message is BIGGER than the module? What's the right way to encrypt such a message?

3 Answers 3

1

To answer your question about what will happen. If you encrypt an $m > N$, what you are actually encrypting is m' = m \bmod N. So you will decrypt to the wrong message.

As to how to solve it, do what wnoise suggests: use RSA to establish a symmetric key and use e.g. AES to encrypt your message.

  • 0
    Yes, I was aware of that, but still, than$k$ you!2011-04-22
6

The typical use of the RSA algorithm encrypts a symmetric key that is used to encrypt the actual message, and decrypt it on the receiving end. Thus, only the symmetric key need be smaller than the log of the modulus.

  • 0
    That is a great suggestion, **wnoise**! Surely will use that when AES is implemented in my library.2011-04-22
3

Another possibility is to simply break up your message into bite-size pieces.

  • 1
    Note that this corresponds to using RSA as a block cipher _in ECB mode_, which is generally considered not to be secure for general use. Depending on exactly how you do the breaking-apart, an eavesdropper will be able to tell if two messages you send start or end with the same several bytes, which can be a significant information leak. If you _must_ use RSA as your only primitive, you should still use it in a mode that prevents this, such as CBC with a random IV (and modular addition/subtraction in place of the XORs).2015-11-07