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.
- Am I correct?
- 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.