RSA 加密的结果是否保证是随机的

Question

我使用 RSACryptoServiceProvider 来加密一些小数据块。对于我正在研究的解决方案，重要的是如果相同的源数据使用相同的公钥加密两次，结果（加密的数据块）是不同的。

我用一个例子检查了这个，它像我希望的那样工作。我现在的问题是，如果这种行为是设计使然并有保证的，或者我是否必须向源数据添加一些随机部分以保证加密后无法再匹配具有相同数据的数据块。

这是示例：

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)

具体问题是针对 .net 的，但如果是设计使然，也许可以为所有 RSA 实现提供一般性的答案？

Answer 1

教科书 RSA 加密算法是确定性的：

ciphertext = plaintext ^ encryption-exponent  mod  modulus

（这里^是整数求幂，mod余数运算。）

但是正如你所说，这并不能提供很好的安全保证，因为可以猜测明文的攻击者可以通过自己加密并比较结果来简单地验证这个猜测。

出于这个原因，官方的 RSA 规范（以及实践中使用的所有实现）包括一些（部分随机的）填充，所以我们实际上并不加密plaintext，而是pad(plaintext)：

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

解密：

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

只有有了这种填充，RSA 才是真正安全的加密方案。

类似的填充也用于 RSA 签名，以避免容易伪造签名。