Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
That is a great suggestion, wnoise! Surely will use that when AES is implemented in my library. –  wh1t3cat1k Apr 22 '11 at 20:40
add comment

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.

share|improve this answer
    
Yes, I was aware of that, but still, thank you! –  wh1t3cat1k Apr 22 '11 at 20:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.