# 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

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