# RSA - What to do when message is greater than N [duplicate]

Exmple: $$e=3, n=33$$ and $$d =7$$ and Message is $$64$$.

“Not use (only) RSA.”

While RSA can be used to transport a message smaller than N (well, actually smaller than a different N that fits inside the padding aperture), the usual solution is to send data like

RSA(aesKey) || IV/nonce || AES(aesKey, message)


in the hybrid cryptosystem model.

When dealing with toy implementations of RSA (with 7-bit keys) you could have the message be a 6-bit encryption key, e.g. a Caesar cipher shift index.

You could write $$E_3(64)=64^3\equiv(-2)^3\equiv(31)^3\pmod{33}$$ to get the values on desired range.

But this is a bad habit in terms of message encryption (and decryption). Generally the message space should be smaller than $$\#\mathbb{Z}_{n}$$ ( $$32$$ in this case ). Otherwise the encryption $$E_e(x):\mathcal{P}\rightarrow \mathcal{C}$$ is not bijective: symbols $$64$$ and $$31$$ would produce the same ciphertexts and recovering the plaintext would be difficult (unless some specific protocol is used).

RSA works over $$\mathbb{Z}_n$$, therefore, you cannot encrypt and decrypt more than $$n$$ values.

But you can choose the representatives of $$\mathbb{Z}_n$$ to include other values instead of the classic $$\{0, 1, ..., n-1\}$$.

For example, if you know that you will never encrypt values smaller than $$n/2$$, then you can represent $$\mathbb{Z}_n$$ as $$\{n/2, n/2+1, ..., n+n/2\}$$, so that you can work some values bigger than $$n$$.

If you still want to encrypt values from $$0$$ to $$n-1$$ and encrypt those additional values bigger than $$n$$, then there is little to do.

One option is to write the message in base $$n$$ and encrypt each word, but of course, you get then a vector of ciphertexts instead of a single ciphertext.

For example, $$64$$ is $$(1, 31)$$ in base $$33$$, then you can encrypt $$2$$ and $$1$$, which are in the original range $$\{0, ..., n-1\}$$.

• Thanks for the answer – Doto Deus Jul 16 at 12:33