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?
Best Answer
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.