Break RSA without padding using a rainbow table attack

Question

We are using RSA without OAEP, with a relatively small input domain.

Lets assume we have John and Bob connected on a line, and we are eavesdropping them. Bob first sends John his public key (e,n), then John encrypts his message m and sends it on the line encrypted. When we eavesdrop the line we get his encrypted message, for example 3211 4431 9938 ... (I'm using a low modulo just for the example)

Me as the attacker can make a rainbow table of encryption of each number from 0 to n, and then decrypt John's message using the table I created.

1. Am I correct?
2. When we use any padding technique, we are preventing this attack (right?), by inserting random bits into the message, but how the decryptor (Bob) can 'remove' those random bits if he doesn't know them.

Answer 1

1. Yes, the attack in the question would work for the low modulo of the example. The term "dictionary" is more appropriate than "rainbow table" (used in the context of making a compact table of precomputed hashes).

   Actual attacks can't work this way though. In RSA as practiced it's impossible to build a large-enough dictionary, as it would take too much time to build (proportional to the modulus $n$, which is typically at least 2048-bit nowadays). However, if Alice encrypted a message known to belong to a small set (such as the names on the class roll) directly with textbook RSA $m\mapsto c:=m^e\bmod n$, then it is possible to decrypt $c$ by encrypting each possible message and testing which matches $c$. A sequential search of the $m$ in the class roll will do: a dictionary of the corresponding $c$ is only useful if there are several messages (and RSA is not practically used by breaking messages into small chunks, as in the question).

2. Random encryption padding solves this problem, by reversibly turning a message $m$ into a sufficiently random-like message representative $\widetilde m\in[0,n)$. Then textbook RSA can be safely applied to $\widetilde m$, per the RSA assumption: for proper public key $(n,e)$ and random $x\in[0,n)$, it's hard to find $x$ from $x^e\bmod n$.

   how can the decryptor (Bob) 'remove' those random bits if he doesn't know them?

   The big picture is there is a convention between Alice and Bob about which bits of $\widetilde m$ are padding (some of which random) added by Alice, that should be removed by Bob. That simplified description is quite close to the deprecated padding technique in RSAES-PKCS1-v1_5. The modern RSAES-OAEP has extra steps so all except (at most) 8 bits of $\widetilde m$ appear random even when $m$ is not (which is obtained by a reversible symmetric cryptographic transformation after applying random padding, which diffuse the randomness), but the idea remains.