RSA cipher wrong use

Question

Why is it foolish if you decide to use an RSA cipher to encode some message by first converting each letter of the message to an integer? So for exmaple Space=0, a=1, b=2,...

After the conversion I encrypt the integer $k$ as $k^e \mod N$.

I do not see why is there any difference?

Answer 1

As a first note: No one would use RSA encryption to directly encrypt some (possibly large) plaintext message and RSA must not be used without a secure padding scheme (see below in the "practical advice"). Anyways, lets look at it:

As I interpret it from your question, you suggest that you use RSA to encrypt a message $m$ interpreted as a string of characters? Then, for instance, an encoded message $k=12$ could either be $m=ab$ or $m=\ell$? You need an unambiguous encoding.

Edit

From your comment another interpretation is that you interpret your message $M$ as a string of $n$ characters $M=M_1\|\ldots\|M_n$ and treat every character $M_i$ as a single message and produce $n$ RSA ciphertexts. Issues:

• Bad performance: Modular exponentiation produces non-negligible overhead and thus encrypting the message $M$ with this approach leads to $C=(C_1,\ldots,C_n)$ and costs $n$ RSA encryption operations (in comparison to a single one when encrypting $M$ as a single message - where I assume that $M$ fits into one integer of $Z_N$). Consequently, it also costs $n$ RSA decryption operations. Why should one do that?

• One can efficiently do "trial encryptions" when using textbook RSA, i.e., without a secure padding scheme, to determine the message hidden when given a ciphertext, since textbook RSA is deterministic.

• Apart from that, even if you use RSA-OAEP which provides IND-CCA2 security and thus non-malleability, i.e., modification of ciphertexts can be detected, in this scenario an adversary could simply drop/replace/reorder/insert any ciphertexts from/into $C$ and thus your so obtained construction does no longer provide non-malleability as single block RSA-OAEP does. However, this is a theoretical issue, since, as @fgrieu points out in his answer, public key encryption alone does not provide authenticity.

/Edit

What is done in practice is quite similar to your idea, but one interprets the entire encoded message (which is typically the result of some padding scheme) as an element of the set $Z_N=\{0,\ldots,N-1\}$, and one uses standardized (unambiguous) encoding functions to map strings to elements of $Z_N$ and back. These are denoted as OS2I(octet string to integer) and its inverse is denoted I2OS (integer to octet string).

For an encoding x=OS2I(M), one treats a string $M$ of $\ell$ octets, i.e., $M=M_{\ell-1}\|\ldots\|M_0$ (which you want to encrypt) as an integer $x$ in base 256 (each octet is interpreted as a non-negative integer to the base 256, where the leftmost bit is the most significant one). More precisely, one sets $x_i = M_i$ and thus

$x=x_{\ell-1}\cdot 256^{\ell-1}+\ldots+x_1\cdot 56+x_0$.

The inverse (which you call after decryption) then takes an integer $x$ and a lenght parameter $\ell$ and outputs an octet string $M$.

Practical Advice

Note that if your string $M$ you want to encrypt does not fit into $Z_N$ you need to divide it into blocks that fit into $Z_N$. But in practice no one would do so, since RSA is used to encrypt only a very short key, e.g., 128 bits, that fits in one block (element of $Z_N$) and uses this key with a secure symmetric encryption scheme to encrypt the (larger) message. This is what is caled hybrid encryption.

Furthermore, textbook RSA must never been used in practice for encryption and one should use standardized and secure versions of RSA with appropriate padding schemes such as RSA-OAEP. Look for instance here. The above mentioned encoding is then applied to the padded message.

Answer 2

It is envisioned to break a message into letters, and encrypt the code $k$ representing each letter as $k\mapsto k^e\bmod N$ (the transformation known as textbook or naked RSA). Several issues here:

1. Parameters $e$ and $N$ are public, thus anyone can compute $k^e\bmod N$ for each of the few letters, which allows recognition of each enciphered letters in the ciphertext, thus trivial decryption.
2. Each $k^e\bmod N$ is going to require like 128 to 512 bytes (so that $N$ is hard to factor), meaning the ciphertext is some hundred(s) time bigger than the plaintext. Performance suffers too (unless the attack of 1. is used).
3. The same plaintext will always lead to the same ciphertext, which is very bad in some case, like when the messages are always one of "Y" or "N" (or few messages, irrespective of size). The solution to this (as well 1. above) is probabilistic encryption.
4. The ciphertext size is directly proportional to the plaintext size, and that allows recognition of if the message is "Yes" or "No", even for a single intercepted ciphertext.

None of this will occur if the message is enciphered using one of the RSAES modes proposed by PKCS#1. However there is a size limit (depending on the size of $N$), and for bigger messages we need hybrid encryption (but that reintroduces problem 4.).

Also, be aware that RSA encryption does not authenticate the message.