Why does plain RSA not work with big messages ($m>n$)?

Question

From what I can remember, RSA is something like this:

• Generate 2 distinct prime numbers $p$ and $q$ that have similar bit length.
• Compute $n=pq$ and $\phi(n)=(p-1)(q-1)$
• Compute $e$ such that $1<e<\phi(n)$ and $\gcd(\phi(n),e)=1$. It is optimal for $e$ to be prime
• Compute $d$ such that $ed\equiv1\pmod{\phi(n)}$
• To encrypt a message $m$ into cipher $c$, compute $c=m^e\pmod{n}$
• To decrypt a cipher $c$ into message $m$, compute $m=c^d\pmod{n}$

But for large $m$ values, this does not necesssarily work.

Let me use an example to demonstrate what I mean:

• Let $p=1999$, $q=2039$, and $e=65537$ (note, all of $p$, $q$ and $e$ are prime)
• Compute $\displaystyle n=pq=1999\times2039=4075961$
• Compute $\displaystyle \phi(n)=(p-1)(q-1)=1998\times2038=4071924$
• Compute $d$ such that $65537d\equiv1\pmod{4071924}$ by solving the Linear Diophantine Equation $\displaystyle 65537x-4071924y=1$

Steps to solve (using a bad implementation of the Extended Euclidean Algorithm)

$\displaystyle 65537\times63-1\times4071924=56907$

$\displaystyle 1\times65537-1\times56907=8630$

$\displaystyle 1\times56907-6\times8630=5127$

$\displaystyle 1\times8630-1\times5127=3503$

$\displaystyle 1\times5127-1\times3503=1624$

$\displaystyle 1\times3503-2\times1624=255$

$\displaystyle 1\times1624-6\times255=94$

$\displaystyle 1\times255-2\times94=67$

$\displaystyle 1\times94-1\times67=27$

$\displaystyle 1\times67-2\times27=13$

$\displaystyle 1\times27-2\times13=1$

Therefore, these things can be substituted:

$\displaystyle 1\times27-2\times(1\times67-2\times27)=5\times27-2\times67=1$

$\displaystyle 5\times(1\times94-1\times67)-2\times67=5\times94-7\times67=1$

$\displaystyle 5\times94-7\times(1\times255-2\times94)=19\times94-7\times255=1$

$\displaystyle 19\times(1\times1624-6\times255)-7\times255=19\times1624-121\times255=1$

$\displaystyle 19\times1624-121\times(1\times3503-2\times1624)=261\times1624-121\times3503=1$

$\displaystyle 261\times(1\times5127-1\times3503)-121\times3503=261\times5127-382\times3503=1$

$\displaystyle 261\times5127-382\times(1\times8630-1\times5127)=643\times5127-382\times8630=1$

$\displaystyle 643\times(1\times56907-6\times8630)-382\times8630=643\times56907-4240\times8630=1$

$\displaystyle 643\times56907-4240\times(1\times65537-1\times56907)=4883\times56907-4240\times65537=1$

$\displaystyle 4883\times(63\times65537-1\times4071924)-4240\times65537=303389\times65537-4883\times4071924=1$

Through calculation, we conclude that $\displaystyle d=303389$ because $\displaystyle 65537\times303389\equiv1\pmod{4071924}$

Example 1

Encryption

Let $m=113$, then, $c\equiv(113^{65537})\pmod{4075961}=3345792$

Decryption

Let $c=3345792$, then, $m\equiv(3345792^{303389})\pmod{4075961}=113$

It works this time! Good!

Example 2:

Encryption

Let $m=33555553$, then, $m\equiv(33555553^{65537})\pmod{4075961}=2621940$

Decryption

Let $c=2621940$, then, $m\equiv(2621940^{303389})\pmod{4075961}=947865$

It does not work this time! What the ----?

Is this message too big to be encrypted? If so, how do we make it smaller?

Answer 1

The issue is that we use modular arithmetic. In modular arithmetic, you may view $m \bmod n$ as the remainder of $m$ when divided by $n$. So, for example, $7 \bmod 2 = 1$, also written as $7 \equiv 1 \pmod 2$, because $2(3) + 1 = 7$.

Now consider what you're guaranteed by $m \equiv c^d \pmod n$, the decryption formula for plain RSA. You're guaranteed that $c^d$ is equivalent to the message modulo $n$. You're not guaranteed that it is precisely equal. Now, if the message is smaller than the modulus — if $m < n$ — then by the way we program modular reduction, where we usually give the smallest positive integer modulo $n$ , you're going to get $m$ exactly when you compute $c^d \bmod n$. But if $m>n$, if the message is bigger, you're going to get a smaller integer that is equivalent modulo $n$.

And indeed this is the case with your example. Note that your example message $m = 33555553$ is larger than your example $n = 4075961$. So when you compute $c^d$, you're going to find an equivalent integer modulo $n$, but not exactly the one you wanted.

In this case, you got back $c^d \bmod n = 947865$. But note what happens if you reduce your original message modulo $n$: you get that your original message is equivalent to $c^d \bmod n$.

In summary: if your message is larger than your modulus, you won't get the exact message back when you decrypt. You'll get an equivalent message instead. To avoid this, you can instead encrypt a key used in a symmetric cryptosystem (or any cryptosystem that can handle messages of the length you're wanting). As Ricky Demer linked in his comment, this is sometimes called a hybrid cryptosystem. Once you've done this, you just use the other cryptosystem's key to do all of your encryption for you.