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

Question

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.

Prevost

FWIW, rsautil is depreciated in favor of pkeyutil – Sandbox

Answer 1

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 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.

Dogcatcher

Answer 2

Ok, I got it. RSA by itself is deterministic. However, to get a better security and prevent attackers from guessing the encrypted information, the encryption is done not on the pure "data" but on "data"+"some-random-pattern" (I should have read wikipedia more carefully)

Prevost

It's not just about guessing the encrypted information. Even if the information is unguessable(say a 128 bit key) not using a proper padding scheme leads to severe weaknesses. Even the still popular PKCS#1 v1.5 scheme is weak. – Barr