Why does RSA encrypted text give me different results for the same text

psibar picture psibar · May 1, 2013 · Viewed 19.1k times · Source

I am encrypting data with openSSL using RSA encryption, which works fine. My understanding of RSA is, that encrypting the same data with the same public key will always give you the same result (as stated here or here).

However, using openssl I get different results every time I repeat the encryption. For example:

➜  ~  echo '30' | openssl rsautl -encrypt -inkey pub.pem -pubin  | shasum
      11b6e058273df1ebe0be5e0596e07a6c51724ca0  -

➜  ~  echo '30' | openssl rsautl -encrypt -inkey pub.pem -pubin  | shasum
      05cb82595f7429ef196189f4e781088597d90eee  -

So why is the output not unique? Is it because I got the RSA encryption wrong or because openssl does some additional magic?

Actually I am trying to design a database which stores only RSA encrypted data. I would like to do searches on the hashsums of the encrypted information, which is impossible if the encryption procedure by itself is not unique.

Answer

Chiara Hsieh picture Chiara Hsieh · May 2, 2013

A secure RSA encryption is implemented with an appropriate padding scheme, which includes some randomness. See PKCS#1 or OAEP for more details.

The RSA encryption encrypts message padded with '0's and and a string of random bit. In the process, the random string is "hidden" in the ciphertext by cryptographic hashing and XORing. On decryption, the RSA decryption recovers the random string from the ciphertext and use it to recover message. This is why you get different result with openssl rsautl for the same text message.