使用BigInteger实现的RSA对于大数无法正常工作

Question

我正在尝试使用 BigInteger 实现简单的RSA加密/解密。对于较小的数字，它可以正常工作，但对于较大的数字无法正常工作：

BigInteger messageToInt = 111098; 
BigInteger enc = BigInteger.ModPow(messageToInt, publicKey, n);
BigInteger dec = BigInteger.ModPow(enc, privateKey, n); // should be same as messageToInt
Console.WriteLine(dec);

这里的密钥来自维基百科示例 - privateKey = 413，publicKey = 17，n = 3233。

• 对于 messageToInt=1500： dec=1500（这是正确的）。
• 对于 messageToInt=15000： dec=2068。（怎么会这样？）

- Liad Sagi

---

RSA不用于加密。即使使用，您也需要一个良好的填充方式，如PKCS#1.5或OAEP。RSA可用于签名，此时您需要RSA-PSS签名方案。此外，您还可以使用RSA进行密钥交换，如RSA-KEM。其中最少使用的是加密。请参见这个不错的答案。 - kelalaka

Answer 1

实际上，这项技术已经完美地发挥了作用：

15000 mod 3233 = 2068.

由于RSA依赖模运算，所以明文必须小于n。无法区分明文是2068、2068 + n、2068 + 2n等。

解决方法是将明文分割成小于n的部分，或增加n直到明文适合其中。

- janw

---

哦，有趣...以前从未见过这个事实被提到。它是如何工作的？为什么超过n长度的消息不起作用？编辑-我明白了，当你只谈论mod时为什么会这样。电源是如何发挥作用的？ - Liad Sagi

模块指数运算（ModPow）执行重复乘法和模数减少（例如_平方和乘法_）。最终结果将被减少到模n的最小可能数字。这意味着您无法获得等于或大于n的数字，因为它会反复减去n直到达到小于n的数字。 - janw

谢谢！我知道 RSA 主要用于加密较小的东西或对称密钥，大多数 RSA 实现都将消息分成块。但是否可以安全地说使用越来越大的密钥的另一个优点是能够加密更大的数据块呢？编辑-出于以上原因 - Liad Sagi

增加块大小的主要目的是使破解密码更加困难（例如通过分解“n”）。虽然从理论上讲，增加密钥大小允许使用更大的块，但在实践中这并不重要，正如您所说：AES密钥具有128到256位，因此剩余的> 1000位主要用于填充（例如OAEP）。还要注意，将密钥大小加倍对性能有巨大影响：https://webmasters.stackexchange.com/a/102372 因此，例如进行两次RSA-2048比进行一次RSA-4096要便宜得多。 - janw

@JanWichelmann：“Massive（巨大的）”可能有点夸张了。做两次RSA-2048可能比做一次RSA-4096略快一些。 - President James K. Polk