20

I'm trying to learn exactly how RSA works. Currently I have a very, very simplictic overview that goes like this.

  • Having the public key allows you to encrypt things. Encrypting the same message "Hello" on two different computers using the same public key will produce the same resulting encrypted message.
  • Having the private key allows you to decrypt the message.

However, if you have access to the public key, could you not simply do a dictionary attack, encrypt all 5 letter words with the key until you find a matching encrypted message and then you know that it was "Hello" that was stored.

In a sense, is it not as easy to brute force RSA encryption of passwords as it is to brute force hashing of passwords?

I know that RSA is usually used for longer messages making it unfeasible to enumerate them all, but is there any advantage to using RSA encryption over hashing if you don't actually want to decrypt the password?

Improve this question
2
  • 3
    Take a look at Thomas Pornin's response at stackoverflow.com/a/7568183/1616145
    – David Wachtfogel
    Oct 15, 2012 at 15:42
  • 4
    Thomas nails it as usual, but you also seem have the misconception that RSA can be used for long messages. The message cannot be longer than the modulus of the public key, meaning that in practice in most cryptosystem RSA is used to encrypt the secret key of a symmetrical cipher.
    – Bruno Rohée
    Oct 15, 2012 at 15:59

1 Answer 1

Reset to default
28

RSA encryption, as per the standard, mandates the use of a padding method which includes random bytes, precisely to avoid the problem you describe. This makes RSA encryption non-deterministic (encrypt the same message twice with the same key, and you won't get the same output; but decryption removes the padding and recovers the message, of course).

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .