Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm having trouble understanding why encrypting a number $m$, which is larger than $n=p\cdot q$. I've looked into the following threads: Why RSA can't handle numbers above 76? Why does plain RSA not work with big messages ($m>n$)?

Can somebody point me to a simpler source, that explains this?

share|improve this question

2 Answers 2

DrLecter's answer explains the real problem, but let me give an easy to understand example:

Imagine RSA encryption/decryption with the following parameters:

  • $n$ remains unchanged
  • $e=1$
  • $d=1$

If you are asking yourself if this works, yes it does:$e$ is coprime to $\phi(n)$ and $ed=1$ mod $\phi(n)$ holds. The funcionality is there, just no security obviously. For encryption and decryption we have:

  • $E(m) = m^1$ mod $n = m$ mod $n$
  • $D(c) = c^1$ mod $n = c$ mod $n$

So when does this become a problem? Obviously if you have messages larger than $n$. Calculating things modulo $n$ can never have a result larger than $n$ (even if your input was larger).

share|improve this answer

I'm assuming that you mean "encrypt with a single encryption operation" (and not to split it up into consecutive blocks such that each fits into $Z_n$).

RSA with modulus $n$ works in the ring $Z_n$, i.e., the set of integers $\{0,\ldots,n-1\}$. So you are limited to working with messages in this set. If you want to encrypt a message $m\geq n$, you are essentially encrypting a message $m'$ in the set $\{0,\ldots,n-1\}$ such that $m'\equiv m\pmod n$, i.e, the message $m$ is "implicitly" mapped to another message $m'$ in the set $\{0,\ldots,n-1\}$ which is the remainder of $m$ when divided by $n$ (the two messages $m$ and $m'$ can be considered identical when working modulo $n$ , i.e., in the residue class ring $Z_n$).

Now, the problem is that after encryption of $m\geq n$ with RSA and decryption thereof you get back $m'$ and you cannot figure out what your initial message $m$ was, since $m'$ is in the set $\{0,\ldots,n-1\}$ and every message that has the same remainder modulo $n$ as $m'$ will be a potential candidate for $m$ (and that are infinitely many ones). So you would be lost. Consequently, to make encryption and decryption of a message $m$ unambiguously, you need to limit the messages you encrypt to the set $\{0,\ldots,n-1\}$.

You may also look at this question and its answers for a more detailed discussion (on the residue class ring $Z_n$).

share|improve this answer

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.