Why is RSACryptoServiceProvider.Encrypt() output not stable?

Question

Until today I was living under the impression that RSA encryption using RSA is deterministic. After all, how should signature verification work if it wasn't?

To my big suprise, .NETs RSACryptoServiceProvider does not have a stable output when encrypting the same set of bytes with the same keys:

[Fact]
public void Learning()
{
    const int keySize = 1024;

    System.Security.Cryptography.RSACryptoServiceProvider rsa = new System.Security.Cryptography.RSACryptoServiceProvider(keySize);

    var bytes = GenerateRandomDataWithLength( 36 );

    for (int i = 0; i < 4; i++)
        Assert.Equal( rsa.Encrypt( bytes, false ), rsa.Encrypt( bytes, false ) );
}

byte[] GenerateRandomDataWithLength( int length )
{
    Random r = new Random();

    byte[] data = new byte[length];
    r.NextBytes( data );

    return data;
}

I have skimmed through the PKCS Specification and I do understand the math behind RSA, so I really wonder why I am observing the output to be unstable.

Mono's RSA implementation has a stable output. The unstable output of Encrypt does not affect decryption, which is well possible and yields the expected data.

Treatment

Answer 1

RSA encryption is pure mathematic so it will give you the same result everytime. However calling Encrypt in .NET is not simply doing RSA encryption.

Why ? The PKCS#1 padding (default when you use false in Encrypt) will make every encrypted result different because it includes random data (for padding purpose).

Mono has the same behavior (at least on my system, see note). However if you are using EncryptValue, which Mono supports but .NET does not (CryptoAPI limitation), then no padding will be done and the encrypted result will be identical each time.

Note: If you have different results please fill a bug report on http://bugzilla.xamarin.com and include the version number you are using.

Risley

Alright, I did completely forget padding included random data. You are clearly right here. Thanks for your answer! (The mono version I was refering to was very old, it was just the sources for Monos RSA actually). – Treatment

@Johannes Note that some random padding is needed to make RSA encryption secure against chosen-plaintext attacks (i.e. encrypting a guessed plaintext again to see if the output matches the one intercepted before). – Cerebroside

For clarity I would add that using true in Encrypt results in random padding as well, I believe (OAEP). – Harrietteharrigan