如何根据摩尔定律计算RSA密钥寿命？

Question

如果遵循摩尔定律，怎么能根据技术进步来估算RSA密钥所需的年数呢？

Answer 1

这很难。主要问题是RSA密钥破解依赖于整数因式分解，其中最有效的(已知的)算法使用CPU，但也使用内存，具有并行计算的约束条件。摩尔定律已经是对给定预算的CPU能力随时间变化的粗略近似；它没有考虑内存大小和延迟(两个不同的事情)。

事实上，正如戈登·摩尔所表达的那样，摩尔定律是关于晶体管密度的，它并不等同于性能；摩尔自己偶尔也会改变它。大约12年前流行的版本是：“每隔三年，一个人就可以在一个特定的区域放置四倍数量的晶体管，而时钟的速度要快两倍。”这意味着当使用FPGA或ASIC打破对称算法时，计算能力每年增加1位；但对于通用计算机来说，这更像是每18个月增加一倍的功率，因为寄存器大小没有增长得那么快，即使当寄存器增长时，我们输入的数据元素也不会增加。而且，在过去的十年中，CPU的时钟速率或多或少地稳定了下来，因此摩尔定律只能通过并行-多核来维持。但并不是所有的算法都易于并行，特别是大矩阵约简，这是通用数域筛的最后一步，也是目前打破RSA的最佳算法。这种矩阵缩减似乎是密钥比当前记录(768位)更长的瓶颈。

阅读本报告的第6节，了解关于这个主题的讨论和提示。所有的人都会看到本站中的各种组织计算出来的估计值，甚至还有更多的指针。

Answer 2

从这个公式开始：http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_和_复杂性

或者反演公式或者使用牛顿近似。

至于要进行的抵消：

http://en.wikipedia.org/wiki/RSA_数字

RSA 1024这个数字似乎没有被分解，但是许多公司已经转移到2048年，甚至4096。

Answer 3

此外，从NIST标准对这一主题的讨论是非常有益的。它们彻底地解释了它们建立标准的方法，以及可以以何种方式抽象出更普遍的安全概念，并可靠地比较对称和非对称密码系统的优点。这是链接。