Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

migrated from Aug 20 '13 at 22:04

This question came from our site for information security professionals.

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.