# RSA: Encrypting values bigger than the module

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?

-

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

-
Could such an algorithm be used: I keep dividing my number mod N and encrypt the remainders until the number becomes zero. After that, I send all the encrypted messages as a series, and after that, the number is restored on the other side by multiplication. – wh1t3cat1k Apr 22 '11 at 14:54
Well, you could, but why do extra computation when you encrypt modulo $N$ with more than 100 digits (say) and you can just chop your message into junks of 100 digits? – Phira Apr 22 '11 at 15:45
Thank you very much! – wh1t3cat1k Apr 22 '11 at 16:22
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). – Henning Makholm Nov 7 '15 at 18:00

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.

-
That is a great suggestion, wnoise! Surely will use that when AES is implemented in my library. – wh1t3cat1k Apr 22 '11 at 20:40

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.

-
Yes, I was aware of that, but still, thank you! – wh1t3cat1k Apr 22 '11 at 20:38