1

I use RSACryptoServiceProvider to encrypt some small blocks of data. For the solution I'm working on, it's important that if the same piece of source data is encrypted twice with the same public key, the result (the encrypted block of data) is not the same.

I have checked this with an example and it worked like I hoped. My question is now, if this behaviour is by design and guaranteed or if I have to add some random part to the source data for guaranteeing that data blocks with the same data can not be matched anymore after encryption.

Here is the example:

byte[] data=new byte[]{1,7,8,3,4,5};
RSACryptoServiceProvider encrypter = cert.PublicKey.Key as RSACryptoServiceProvider;
byte[] encryptedData = encrypter.Encrypt(data,true);

// encryptedData has always other values in, although the source data is always
// 1,7,8,3,4,5 and the certificate is always the same (loaded from disk)

The concrete question is for .net but maybe the answer can be given in general for all RSA-implementations if it is by design?

HCL
  • 36,053
  • 27
  • 163
  • 213
  • Tangentially, you shouldn't be encrypting your data directly with RSA - instead, encrypt a symmetric key with RSA, and encrypt your data with the symmetric key. Or better, use an existing library that does this for you. – Nick Johnson Nov 01 '11 at 05:27
  • @Nick: Thanks for your comment. I encrypt an SHA1-hash. I don't think that using hybrid encryption is necessary in this case. In contrary, I think it's only useless overhead. Am I right or have I missunderstood something? – HCL Nov 01 '11 at 06:20
  • No, that's fair enough - you're effectively signing rather than encrypting. I'd still suggest using an existing library rather than composing primitives yourself, though. – Nick Johnson Nov 01 '11 at 06:24

1 Answers1

6

The text-book RSA encryption algorithm is deterministic:

ciphertext = plaintext ^ encryption-exponent  mod  modulus

(Here ^ is integer exponentiation, mod the remainder operation.)

But as you remarked, this does not provide a good security guarantee, as an attacker which can guess the plaintext can simply verify this guess by encrypting it himself and comparing the results.

For this reason, the official RSA specifications (and also all implementations used in practice) include some (partly random) padding, so we don't actually encrypt plaintext, but pad(plaintext):

ciphertext = pad(plaintext) ^ encryption-exponent  mod  modulus

Decryption:

plaintext = unpad( ciphertext ^ decryption-exponent mod modulus )

Only with this padding RSA is actually a secure encryption scheme.

A similar padding is also used for RSA signatures, to avoid easy forging of signatures.

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
  • +1 Thanks for your answer. Is the padding algorithm a commonly used algorithm, or implements every platform its own padding and unpadding logic? – HCL Oct 28 '11 at 18:43
  • 1
    As just mentioned in an answer to your other question, there are basically two padding schemes in use: [OAEP](http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding) (which totally mixes the data up) and [PKCS1-v1_5](http://tools.ietf.org/html/rfc3447#section-7.2.1) (which essentially adds some random bytes at the beginning). – Paŭlo Ebermann Oct 28 '11 at 18:53