encryption - 为什么在 RSA/加密中使用“大素数”？

Question

我已经学习了公钥加密的理论，但我错过了与物理世界的联系。例如

有人告诉我，良好的 RSA 加密应该依赖于 300 个十进制数字的素数，但为什么呢？这个数字是谁想出来的？破解这种加密需要多长时间（关于不同机器的统计数据）。

我试过谷歌，但找不到我想要的。任何人？

谢谢

Answer 1

非对称密码学的关键是具有非对称功能，允许解密由非对称密钥加密的消息，而不允许找到另一个密钥。在 RSA 中，使用的函数基于素数的因式分解，但它不是唯一的选择（例如，椭圆曲线是另一种选择）。

所以，基本上你需要两个素数来生成一个 RSA 密钥对。如果您能够分解公钥并找到这些质数，那么您将能够找到私钥。RSA 的整体安全性是基于不容易分解大合数这一事实，这就是为什么密钥的长度会极大地改变 RSA 算法的鲁棒性的原因。

每年都有比赛用计算器分解大素数，而且价格不错。分解 RSA 密钥的最后一步是在2009 年通过分解 768 位密钥完成的。这就是为什么现在至少应该使用 2048 位密钥的原因。

像往常一样，维基百科是 RSA 的一个很好的参考。

Answer 2

所有公钥算法都基于陷门函数，即以一种方式“容易”计算但“难以”反转的数学结构，除非您还有一些额外的信息（用作私钥），此时也反向变得“容易”。

“简单”和“困难”只是定性形容词，它们总是根据计算复杂性进行更正式的定义。“难”通常是指对于某些固定x并且其中n是输入数据的多项式时间O(n ^x )无法解决的计算。

在 RSA 的情况下，“简单”函数是模幂C = M ^e mod N ，其中N的因子是保密的。“困难”问题是找到C 的第e个根（即M）。当然，“难”并不意味着它总是很难，而是（直观地）将N的大小增加某个因子会使复杂度增加一个更大的因子。

推荐的模数大小（2048 位或 617 个十进制数字）与当前计算能力的可用性有关，因此如果您坚持使用它们，您可以放心，攻击者破解它的代价将非常高. 有关更多详细信息，我应该向您推荐关于 cryptography.SE 的精彩答案（去投票:-)）。

最后，为了有一个活板门，N被构建为一个合数。从理论上讲，为了提高性能，N 可能有超过 2 个因素，但一般的安全规则是所有因素必须平衡并且具有大致相同的大小。这意味着如果您有K个因子，并且N是B位长，则每个因子大约是B/K位长。

这个要解决的问题与整数分解问题不同。两者是相关的，如果您设法将N分解，您可以通过重新执行生成密钥的一方所做的事情来计算私钥。通常，使用的指数e非常小 (3)；不能排除有一天有人设计了一种算法来计算e -th 而不考虑N。

编辑：更正了 2048 位 RSA 密钥模数的十进制位数。

Answer 3

RSA 使用单向数学函数的思想，因此如果您有密钥，则很容易加密和解密，但如果您没有密钥，则很难（因为它需要大量的 CPU 周期）解密。甚至在他们考虑使用素数之前，数学家就已经确定了对单向函数的需求。

他们想到的第一个方法是，如果您的“密钥”是质数，而您的消息是另一个数字，那么您可以通过将两者相乘来加密。有钥匙的人可以很容易地划分出质数并得到消息，但对于没有质数的人来说，找出质数的钥匙很难。