# Why RSA can't handle numbers above 76?

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?

-

## migrated from security.stackexchange.comSep 14 '12 at 13:15

This question came from our site for Information security professionals.

Interesting question. I'm guessing the answer is something to do with the number of bits you can encrypt with such low p and q (or e and d in your case) values, but I'm unsure as to how the modulus affects this. This question would be better on Crypto SE though, so I've flagged for a moderator to move it. –  Polynomial Sep 14 '12 at 13:12
@Polynomial thanks for your quick reply,it starts to make sense that in the textbook it says the p,q must be prime 1,024bits or above –  mko Sep 14 '12 at 13:19
@yozloy that's more for security, the larger the primes the harder it is to factorize, technically you could use single digit primes, but it'll be trivial to break the keys, something is still wrong with the math here, this expression must hold true: %n !>= n . The only thing I can think of causing an issue is an order of operations error somewhere possibly due to optimization or something. Which programming language is it (I can think of several which have close enough syntax). –  ewanm89 Sep 14 '12 at 13:26
@ewanm89 it's python, and if I can change the value of z h u to number that equal or smaller than 76, than it works, I just change the number and run the program again, the result is same as expected 16 77 55 25 0 55 16 0 55  –  mko Sep 14 '12 at 13:30

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.

-
To be technically correct, it works fine, except there are multiple possible decryption for each character and it's non-deterministic to know which it is. –  ewanm89 Sep 14 '12 at 20:20

Your plaintext message (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 mod 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).

-