Message length restriction in RSA

Question

In RSA the message length should not exceed the (keysize/8) bytes. Why is there such a restriction? What is the input(say "abcde") converted into before feeding it into the RSA algorithm and where doest it take into account the size of the the input string "abcde"?

Answer 1

The RSA algorithm is essentially:

Ciphertext = (Plaintext e) mod n

and to decrypt:

Plaintext = (Ciphertext d) mod n

e and n together make up your public key, and d and n make up your private key. e is usually one of a few common values, e.g. 65537, n is the product of two large prime numbers p and q which should be unique to you, and defines the key length (e.g. 1024 bits). The value of d used to decrypt the ciphertext is calculated using e, p and q. Wikipedia has more detail if you're interested: http://en.wikipedia.org/wiki/RSA_(algorithm). Your plaintext is basically treated as a large integer when used in the RSA algorithm.

In case you're not familiar with the modulo operator, it is basically the remainder when the left side is divided by the right side. E.g. 17 mod 5 = 2 as 5 exactly divides 17 three times (3 * 5 = 15), leaving a remainder of: 17 - 15 = 2).

As a result of the definition of the modulo operator, the result of a mod b is always less than b. Given this, and the fact that the decrypted value is the result of performing a mod n operation means that when decrypted, the resulting plaintext value will always be less than n. Hence, for this to be the actual plaintext you originally encrypted, the input must be less than n.

To guarantee this, the message is restricted to having fewer bits ("digits") than n. Since the number of bits in n is the key size, it must must have fewer than keysize bits, or keysize / 8 bytes (since there are 8 bits in a byte).