Why RSA can't handle numbers above 76?

Question

I'm going to encrypt the characters Zhu, and decrypt them using RSA. I'm using the public key $\{e, n\}$ and private key $\{d, n\}$. The values of $e$, $d$ and $p$ I get from my textbook: $e = 17$, $d = 53$, $n = 77$.

It works fine when the number is smaller than 76, but in my example below, it doesn't work:

z = 90 
h = 104 
u = 107 
e = 17
d = 53
n = 77

print z,h,u

c_z = z ** e % n
c_h = h ** e % n
c_u = u ** e % n

print c_z, c_h, c_u

p_z = c_z ** d % n
p_h = c_h ** d % n
p_u = c_u ** d % n

print p_z, p_h, p_u

The outputs are:

90 104 107
62 69 46
13 27 30  

Do you have any idea what's going wrong?

Answer 1

By definition you cannot encrypt values greater than the modulus in RSA, because the plaintext is immediately reduced modulo $n$ which loses information. This is because textbook RSA works in the $\mathbb{Z}/n\mathbb{Z}$ congruence ring, so from RSA's point of view, as long as two values have the same remainder modulo $n$, they are effectively equivalent. So with your $n = 77$ example, RSA will not distinguish plaintexts of $10$ and $87$ since they both leave a remainder of $10$ when divided by $77$, i.e. they are equal in $\mathbb{Z}/n\mathbb{Z}$. They will produce the same ciphertext, and hence decrypt to the same value ($10$).

Put differently, RSA does not care what your plaintext is, all it cares about is its remainder when divided by your modulus. Anything else is irrelevant, all that matters is the remainder (hence everything being done modulo $n$).

You will notice "z" (90) decrypts to 13 which just so happens to be the remainder of 90 when divided by 77, as $90 = 1 \times 77 + 13$. Similarly, "h" (104) decrypts to 27, and sure enough, $104 = 1 \times 77 + 27$. And again, "u" (107) decrypts to 30... you guessed it, $107 = 1 \times 77 + 30$. Coincidence? Not at all, it is a direct consequence of the first paragraph.

Another way to think of it is that since RSA can only output values between $0$ and $n - 1$ (because the ciphertext is taken modulo $n$), then there can only be $n$ possible plaintext inputs (pigeonhole principle). It then becomes clear encrypting values above $n - 1$ is not useful.

You'll need to use a bigger modulus, or work with a different charset e.g. a = 0, b = 1, etc... instead of using the ASCII one, since in ASCII most small values are unfortunately taken up by control characters. If you want all basic characters to work properly, try this keypair:

$\left ( ~ p = 13, ~ q = 29, ~ n = 377, ~ e = 17, ~ d = 257 ~ \right )$

This should work - but do remember this is only for learning purposes.

---

Fun fact: this small RSA keypair is very interesting in that its encryption and decryption exponents are both prime fermat numbers, this is amazingly rare and quite surprising. Just thought I'd mention it.

Answer 2

Your plaintext messages (you actually have three different plaintext messages - $z$, $h$ and $u$) are all greater than the modulus $n$, which simply doesn't work with RSA. You will notice that the $p_x$ values are just the original $x$ value modulus $n=77$ in this case ($13 = 90 \bmod 77$ etc).

For RSA to work (that is, the plaintext to be recovered after encryption then decryption) the message being raised by the exponent must be smaller than the modulus (for this to happen securely, a secure padding scheme must also be used, but that's another matter).