encryption - 为什么 RSA/加密中使用 "large prime numbers"？

Question

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

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

我尝试过 Google，但找不到我想要的内容。有人吗？

谢谢

Answer 1

非对称密码学的关键是拥有一个非对称函数，该函数允许解密由非对称 key 加密的消息，而无需找到另一个 key 。在 RSA 中，使用的函数基于素数分解，但它不是唯一的选项(例如 Elliptic curve 是另一个选项)。

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

每年都会举办用计算器分解大质数的竞赛，价格也很优惠。分解 RSA key 的最后一步已完成 in 2009 by factorizing 768 bits 键。这就是为什么现在至少应该使用 2048 位 key 的原因。

像往常一样，Wikipedia是关于 RSA 的一个很好的引用。