RSA in C# does not produce same encrypted string for specific keys?

Question

I have a requirement, where I need to encrypt my connection string in one application and decrypt it in another. With this in mind, I save the public key and private keys in App.Config of the application respectively.

Now, shouldn't RSA should give me same encrypted string with same keys which I use?

I get different encrypted strings all the time, with same keys used.!! Please help me to clear the confusion. I am not understanding how I can solve this problem, that I get BAD Data exception if I use the saved encrypted string, as every time the encryption gives me different encrypted strings.

Here is my code:

private string connecString;
private RSACryptoServiceProvider rsaEncryptDecrypt;

public EncryptAndDecrypt(string connecString)
{
    this.connecString = connecString;
    this.rsaEncryptDecrypt = new RSACryptoServiceProvider(4096);
}

public string EncryptTheConnecString(string publicKeyValue)
{
    byte[] encryptedData;
    rsaEncryptDecrypt.FromXmlString(publicKeyValue);

    byte[] message = Encoding.UTF8.GetBytes(connecString);
    encryptedData = rsaEncryptDecrypt.Encrypt(message, false);

    return Convert.ToBase64String(encryptedData);
}

public string DecryptTheConnecString(string privateKeyValue, string encrystr)
{
    byte[] decryptedData;
    rsaEncryptDecrypt.FromXmlString(privateKeyValue);

    byte[] message = Convert.FromBase64String(encrystr);
    decryptedData = rsaEncryptDecrypt.Decrypt(message, false);

    return Encoding.UTF8.GetString((decryptedData));
}

Thank you in advance.

Update 1: I used

UnicodeEncoding ByteConverter = new UnicodeEncoding();
ByteConverter.GetBytes("data to encrypt");
//Which is not Connection string but a small test str

Still I see that the encrypted data is changing everytime. But the Bad Data error is no more seen. Yet I cannot use UTF16(UnicodeEncoding) over Encoding.UTF8 because it cannot encrypt the huge string like connection string and throws an exception:

 CryptographicException: Key not valid for use in specified state.

Update 2:

I could solve the problem of bad data by using UTF8Encoding ByteConverter = new UTF8Encoding(); and then doing ByteConverter .GetString("HUGE STRING");

Answer 1

It can happen because of Random Padding.