How to cipher bocks with RSA in ECB mode?

Question

I'm trying to implement a very basic RSA with functions that should generate RSA keys and cipher some text. GenKey function returns a tuple (p,q,n,e,d) like the following.

p,q large prime numbers with 1024bits each
n = p*q
phi(n)=(p-1)(q-1)
e as gcd(phi(n),e)=1 and 1 < e < phi(n)
d = e⁻1 (mod phi(n))

At the end I'll get a public key like kp={e,n} and a private one ks={d,n}. So far everything is working as expected.

Now suppose that cipher function receives a string of binary data as the plaintext to cipher and outputs a ciphered text in ECB mode(a binary string aswell). I Know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer. If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary. Please correct me If I'm wrong at this point.Am I thinking it right?

So my question is, when calculating C is it possible that returned value is too bigger for representing (as binary) on my block size decision (those 32bit). How block size should be picked?

Answer 1

Securely enciphering text with RSA is typically done in one of three ways:

1. The most usual one is with the help of a symmetric cipher: RSA is used to establish a symmetric key, and the text itself is enciphered with the symmetric cipher. That's a hybrid cryptosystem. One way is that the sender generates a uniformly random $x$ in range $[0..N)$, enciphers it with the textbook RSA public-key function $x\to x^e\bmod N$ and sends the results (of 256 octets) which the receiver can decipher; then both extract the (say) 192 low-order bits of $x$ and use it as key for AES-CTR, which enciphers the text.
2. RSA-ECB with random padding: the text is broken into pieces significantly smaller than the public modulus (e.g. 190 octets pieces for 2048-bit RSA); each block associated with some randomness and redundancy (e.g. 32+34 octets) into a padded block, by some algorithm (e.g. RSA(ES)-OAEP) typically involving a hash (e.g. SHA-256); each result $x_i$ is enciphered with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated. Decryption undoes that and discards the randomness. This option has huge drawbacks when more than one block is involved: slow decryption, sizable ciphertext expansion (e.g. +15% for large text). In practice, it is thus used only for small amount of data (e.g. the secret PIN number of a credit card).
3. RSA is used (possibly multiple times) to establish a shared secret random keystream as long as the plaintext, then used to encipher the plaintext with XOR (or other equivalent information-thoretically perfect cipher). E.g the sender generates uniformly random $x_i$ in range $[0..2^{2040})$ (enough that the 255-octet $x_i$ concatenated are at least as long as the plaintext), enciphers them with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated and sent, as well as the plaintext XORed with the keystream. This is nearly as slow as 2 (there are almost as many RSA decryption to perform), has significantly worse ciphertext expansion (ciphertext is over twice as large as plaintext), but requires no keyed cipher (as 1 does) or padding function (as 2 does).

In 2, cutting corners on randomness would allow an adversary to check a guess of a plaintext (that's a disaster for a PIN number, or the name of someone on the public class roll). Cutting corners on the padding function leads to other, more subtle security issues. Some introductory material uses 2, cuts corners on both randomness and padding, and uses very small $p$ and $q$. That's justifiable only for teaching purposes and with ample warnings (sadly often skipped or/and forgotten).

For large $p$ and $q$, the only recommendable options are 1; 2 exclusively limited to short plaintext and with decent randomness and padding function; or 3 for something which for some reason (e.g. pedagogical, conceptual simplicity, code size..) must use neither a keyed cipher nor a hash.

Note: none of these options provide message integrity of any kind. Since the public key is known to attackers, they can generate messages with any deciphered content they will. Upgrading option 1 with authenticated symmetric encryption does not satisfactory solve that issue (it only ensures that an adversary can not alter part of a message while leaving some unknown portion unchanged).

---

I know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer.

That's textbook RSA, is cutting on both randomness and padding, and thus is unsafe. For a start, any guess of M can be checked, and that's an unwanted property in encryption.

As an aside, I read C = M^e (mod n) as $C\equiv M^e\pmod N$ which means that $N$ divides $M^e-C$, and that is not satisfactory (in particular it allows $C=M^e$ which allows recovery of $M$ from $C$ as $M=\sqrt[e]C$ ). The proper equation is $C=M^e\bmod N$ , additionally meaning that $0\le C<N$ ; notice there is no opening parenthesis before $\bmod$ , making it an operator similar to the % operator of C, Java, Go, rather than implying that the previous equality is modulo $N$ (which is the case with an opening parenthesis before $\bmod$ ).

If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary.

The general idea of cutting in blocks is right if choosing option 2, but doing so in the manner stated is very unsafe due to the lack of added randomness, allowing to find each 32-bit integer by trial and error. Further, if $e<{2048/32}=64$, there is an attack without trial and error due to lack of padding (computing $\sqrt[e]C$ will always reveal $M$ ). Further, the ciphertext expansion is by a factor of ${2048/32}=64$, which is wasteful; and decryption will be dead slow. Larger blocks somewhat improve things, but what's really needed is randomness and proper padding; or better, getting rid of option 2 / RSA-ECB altogether.

How should block size be picked?

If using RSA-ECB (which again is reasonable only for short messages, needing a single block), the choice is dictated by the padding algorithm used. In all such algorithms, that can be at most $\lfloor\log_2N\rfloor-r$ bits, where $r$ is the number of random bits added, which determines the security level against confirming a guess of $M$; $r\ge128$ is recommandable. For $N$ of $8b$ bits, a hash of $8h$ bits, RSAES-OAEP allows block size up to $b-2h-2$ octets. For $8b=2048$ and $8h=256$, that's $190$ octets. It is a tad wasteful, but RSAES-OAEP (also known as PKCS#1v2 encryption padding) is the only RSA encryption padding with both a security proof and good support in common crypto libraries.

Answer 2

For RSA there is usually a difference between input size and output size.

1. for the textbook RSA the maximum value is identical to the modulus, the input size if taken as integral bits is $n - 1$, where $n$ is the size of the modulus in bits;

2. for RSA in PKCS#1 mode it is 11 bytes smaller than the modulus size in bytes;

3. for RSA in OAEP mode it is at least 42 bytes smaller, depending on the hash function used for the internal MGF1 function.

The output maxes out on the modulus size of course, so the size is $n$ bits. Usually this is already on a byte boundary.

Of course 2048 is pretty far from the 32 bit block size that you've indicated. You can not create a 32 bit block cipher out of RSA as the output size cannot be compressed to 32 bit.

---

Hence the use of hybrid cryptography where RSA is paired with a symmetric cipher. For symmetric ciphers the size of the ciphertext is linear with the size of the message, usually plus a certain overhead of 16-32 bytes for IV and authentication tag + of course the size of the RSA operation: the key size in bytes (in this case 256 bytes for a 2048 bit key).