How is RSA able to prevent brute forcing using the public key?

Question

• 1. Bob calculates a private and public key.
• 2. Bob sends his public key to John.
• 3. Jeff is a third party unwanted member and manages to snatch the public key mid-transfer.
• 4. John encrypts his message and sends it to Bob.
• 5. Jeff again is able to steal this encrypted message for himself.
• 6. Bob can decrypt the message with his private key.

But what about Jeff? So he can't decrypt using the one-way key. But what if he brutes it? So for example John's original value was 2 and the encrypted value is now let's say 200. Jeff can now just count upwards from 1 and encrypt all values with the public key until it matches the value of 200. He finds 2 matches that. So now he has the original value.

I know it's not that simple and easy and it might not even work at all on a real RSA standard but I want to know what the procedure is for stopping this sort of attack.

Answer 1

If Jeff has the public key and an encrypted message, why can't he guess the message, encrypt it with the public key, and see if he gets the encrypted message.

Well, that particular attack is foiled by the RSA padding method. All RSA encryption padding methods include randomness in the padding (specifically to foil this attack). Whenever John encrypts a message, he (actually, his crypto library) selects a number of random bits, and pads the message (that is, prepares the message for the core RSA operation) using those random bits. Hence the encrypted message is a function of both the plaintext message and those random bits.

Jeff can certainly take the public key, and encrypt a guess of the message with it; however unless he happens to pick the same random bits that John used, his encrypted message will look different, and so comparing the actual ciphertext to his test one (with high probability) tells him nothing. And, we use enough random bits so that Jeff can't brute force those.