TAOCP 4.5.4 Exercise 32
In textbook RSA, a message $M$ is encoded as C \equiv M^3 \pmod N, where $N=pq$ and the public exponent is $3$.
Section 4.5.4: Factoring into Primes
Exercise 32. ▶ [M21] Show how to modify the RSA encoding scheme so that there is no problem with messages $< \sqrt[3]{N}$, in such a way that the length of messages is not substantially increased.
Verified: yes
Solve time: 5m40s
Solution
In textbook RSA, a message $M$ is encoded as
$$ C \equiv M^3 \pmod N, $$
where $N=pq$ and the public exponent is $3$.
The difficulty arises when
$$ 0 \le M < \sqrt[3]{N}. $$
In that case,
$$ M^3 < N, $$
hence the reduction modulo $N$ does nothing and
$$ C=M^3 $$
as an ordinary integer. Anyone can recover the message by taking the integer cube root of $C$, without factoring $N$.
A modification is needed that prevents the transmitted value from being the cube of a small integer.
Let
$$ B=\lfloor \sqrt[3]{N}\rfloor . $$
Represent each message as a pair $(r,m)$, where
$$ 0\le r<B,\qquad 0\le m<B. $$
Form the integer
$$ M=rB+m . $$
Then
$$ 0\le M<B^2<N^{2/3}<N, $$
so $M$ is a valid RSA plaintext block.
The message actually being conveyed is $m$; the quantity $r$ is chosen at random and transmitted only implicitly through the RSA encryption. The ciphertext is
$$ C\equiv M^3 \pmod N. $$
Since $M\ge rB$, choosing $r\ne0$ gives
$$ M\ge B, $$
and therefore
$$ M^3\ge B^3>N-3B^2, $$
while typically $M^3>N$. Thus the ciphertext is no longer an ordinary cube of a small integer, and the cube-root attack is impossible.
To decode, the legitimate receiver computes
$$ M\equiv C^d \pmod N, $$
where $d$ is the RSA decryption exponent. Then
$$ r=\left\lfloor \frac{M}{B}\right\rfloor,\qquad m=M\bmod B. $$
The original message $m$ is recovered.
The message length is not substantially increased. A block of size less than $B\approx N^{1/3}$ contains about
$$ \frac13\log_2 N $$
bits. The modified plaintext $M=rB+m$ contains two such quantities, hence about
$$ \frac23\log_2 N $$
bits, still well below the available $\log_2 N$ bits of an RSA plaintext block. Thus only a constant-factor increase occurs, while every encrypted block is protected against the vulnerability of messages less than $\sqrt[3]{N}$.
Therefore RSA can be modified by adjoining a random prefix $r$ and encrypting
$$ M=rB+m,\qquad B=\lfloor\sqrt[3]{N}\rfloor, $$
which eliminates the problem for all messages $<\sqrt[3]{N}$ without substantially increasing message length.
$$ \boxed{\text{Use randomized padding } M=r\lfloor\sqrt[3]{N}\rfloor+m \text{ before RSA encryption.}} $$