How to encrypt a number larger than N on RSA?

Question

Here is an example:

p = 11, q = 5, N = p*q = 55, choose encryption exponent e = 3, so d = e^-1 mod (p-1)(q-1) = 27.

If I want encrypt x=13, x^e=13^3=52mod55.

I understand how to encrypt a number which is less than N, but how to encrypt a number which is larger than N?

I know if X is larger than N, we should decompose X into several parts and encrypt them respectively, but I don't know how RSA decompose it?

Optional question:

How to encrypt a file with RSA on IOS or python?

Answer 1

You don't use RSA to encrypt long messages.

The correct approach is using hybrid encryption instead:

• Generate a random AES key, encrypt the actual data with AES. Preferably using an authenticated mode like AES-GCM.
• Encrypt the AES key with RSA. This key (126 to 256 bits) is small enough to fit within one RSA block. For example using small and thus weak 1024 bit RSA keys you have 500-700 bits for the actual data (the rest is consumed by the padding).

• The ciphertext consists of both the RSA encrypted AES key and the AES encrypted file.

  It's essential for security to apply padding here, namely OAEP. Most other paddings, including the popular PKCS#1v1.5 padding are not secure.

Don't try to split the file into blocks which you encrypt with RSA. There are no standard ways for doing this, because it's a bad idea.

Answer 2

The RSA algorithm does not handle decomposition of the message at all. It just encrypts fixed-size integers. This kind of encryption algorithms is called a block cipher, because it encrypts messages in fixed-size "blocks".

How the blocks are obtained is generally not specified by the block-cipher itself. So, you have to decide how to split the message. One of the possible ways to decompose an integer into fixed-size blocks is to convert it to base N, and encrypt each digit separately.

Note that you should not encrypt each digit independently from the others, because that wouldn't be safe. In fact doing so is equivalent to using a monoalphabetic cipher. . There are different mode of operations for block ciphers that you can use to safely encrypt multiple blocks. You should read the wikipedia page to learn about them.