Brute force attack on RSA - success criteria?

Question

In a hypothetical discussion we ended up with a concrete question I'd like to find the answer to:

If you try to brute force an RSA encryption, but the original vale which was encrypted was just random binary data, can you ever be sure you found the correct key? In other words: What are the success criteria for RSA brute forcing?

Do "you" say "This is neither a text encoding I know nor a file format I recognize, so this isn't the correct key" and try the next? Or can you tell by metadata or something that you've found the correct key? Or is it safe to say that completely random data encrypted with RSA is unbreakable by brute force?

Answer 1

Well, typically for RSA, we have the public key. That makes the verification process easy:

• If you're trying to guess the private key (factoring or equivilent), that's easy; you just verify the factorization; "does the two primes we get, multiplied together, give us the modulus in the public key?"

• If you're trying to guess the padded plaintext that corresponds to a ciphertext, that's easy; you encrypt the padded plaintext with the public key, and if it results in the ciphertext, you guessed it correctly. Note that, for nondetermanistic padding methods (which is what ought to be used for RSA encryption), you have to guess the nondetermanistic padding bytes as well as the message bytes.

• If you're trying to forge an RSA signature, that's easy; you just verify the forgery with the public key.