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?

$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That is a great suggestion, wnoise! Surely will use that when AES is implemented in my library. $\endgroup$
    – wh1t3cat1k
    Apr 22, 2011 at 20:40
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – wh1t3cat1k
    Apr 22, 2011 at 14:54
  • $\begingroup$ 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? $\endgroup$
    – Phira
    Apr 22, 2011 at 15:45
  • 1
    $\begingroup$ 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). $\endgroup$
    – hmakholm left over Monica
    Nov 7, 2015 at 18:00
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, I was aware of that, but still, thank you! $\endgroup$
    – wh1t3cat1k
    Apr 22, 2011 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .