0

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?

Community
  • 1
Gretty
  • 239
  • 1
  • 5
  • 9

2 Answers2

4

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$).

Community
  • 1
DrLecter
  • 12,547
  • 3
  • 43
  • 61
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).

tylo
  • 12,654
  • 24
  • 39