# RSA encrypting values bigger than the modulus

I'm suppose to implement RSA algorithm and I saw that everyone assume that the message $m$ is less than the module $n$, so that $m^e \mod{n}$ allows to fully restore $m$ when decrypting the message.

My problem is that my number can be bigger than $n$. Let's say that $e=17$, $n=33$ and $m=134$. How can I encrypt this value (and decrypt it as well) without using solutions like AES encryption?

-

Mostly you don't.

Since public-key algorithms are generally slow compared to the amount of data they can handle per primitive, what people generally do is to use the asymmetric primitive to encrypt a randomly chosen key for a symmmetric cipher such as AES, and then encrypt the actual message with the symmetric cipher.

In you absolutely must avoid that, you could in principle you could use the RSA primitive as a block cipher and chain several invocations of it together to encrypt a long message using a conventional block cipher mode of operation such as CBC. Some minor tweaks will probably be necessary because the "block length" is not an integral number of bits, though.

A worse problem, whether your message fits in a single block or not, is that with a public-key system, we're typically trying to keep secrecy against an adversary who has the encryption key but not the decryption key. This means that if there are a small number of possible (or even likely) messages, the attacker could just try to encrypt some guesses and see if they match the intercepted ciphertext.

Therefore unless what you're encrypting with RSA is something that is known to be completely random (such as a randomly chosen AES session key), you should start by interlacing your plaintext message with random bits in sufficient amount that every RSA block will contain a good amount of guaranteed randomness (say, at least 64 random bits per block, as a rule of thumb). The recipient of the message will then discard those bits after decrypting.

-

In practice: see Henning's answer for an explanation.

In theory: you can write any message (or any integer) in base $n$ and encrypt them one digit at a time. So here you would first write $$m=134=4\cdot33+2$$ to find that your (length two) message is the sequence $(4,2)$, and then encrypt first 4 and then 2. At the decrypting end you similarly pack the decrypted digits and recover $m$.

More generally you would write $$m=\sum_{i=0}^kd_im^k$$ for some integer $k\ge0$ and `digits' $0\le d_i<m, i=0,1,\ldots,k$. Then you get the vector $(d_k,d_{k-1},\ldots,d_1,d_0)$ of integers in the range $[0,n-1]$. Encrypt them individually, and send the resulting sequence of $k+1$ encrypted integers to the receiver.

-
This is unsafe, however, because it makes it every easy for an eavesdropper to learn some facts about your message -- in particular, whether or not it is a multiple of $34$, which happens exactly when the encrypted "digits" are equal. Preventing such information leaks is the job for a "mode of operation", where I suggested CBC or some variant thereof. –  Henning Makholm Dec 18 '12 at 14:37
@HenningMakholm Of course, with reasonable keys, a message being a multiple of $N+1$ is less likely than a randomly guessed number being a factor of $N$. I think another disadvantage is, however, that the leading $N$-ary digit is likely to be small. –  Hagen von Eitzen Dec 18 '12 at 16:09
Agree with both of the comments. If the same key is used several times, there is an increasing risk of some leak (though obviously very low here for reasonable key sizes). Hagen, I think that practical implementations will do something like padding the message to prevent the risk you brought up. –  Jyrki Lahtonen Dec 18 '12 at 16:59