要说的是，您不认为当前使用的RSA密钥长度是将在十年或十五年内变得安全。
使用说一百万位的RSA密钥长度会遇到哪些技术困难（硬件和/或软件）？
假设您是从头开始设计的，那么您对硬件-软件设计的选择将一清二楚。还要假设您不在乎是否需要24小时左右的时间来加密或解密信息。
#1 楼
密钥长度为$ n $位的RSA的计算成本，公钥操作（加密，签名验证）约为$ O（n ^ 2）$，私钥操作（解密，签名）约为$ O（n ^ 3）$代）。因此，具有一百万位密钥的RSA将比具有1024位密钥的RSA慢大约十亿倍（用于私钥操作）。后者在普通PC上大约需要1毫秒，因此您需要使用百万位密钥进行两周的计算。密钥大小的一些值；一百万位整数是128 kB；您可以在RAM中拥有数千个。但是，您将超过1级缓存（在普通PC上为32或64 kB），因此可以预期会出现一定的速度下降（使用蒙哥马利乘法，数据访问是连续的，因此应限制这种影响）。 />当然，安全性不仅在于抵制攻击，还在于抵御攻击。这也是关于有信心抵御攻击。我对使用带有一百万位密钥的RSA的系统的信心接近于零……因为这没有意义。 RSA是安全的，因为大整数很难分解。具有最佳可用硬件的最著名算法在大约1024位时失败； 2048位绰绰有余。超越就是对尚未发现的算法可能看起来是一个疯狂的，完全没有事实依据的猜测，这是关于传说中关于未来的神秘印象的谣言的猜测。当有人和我谈论拥有超大型RSA密钥（例如8192位密钥，“为了安全”）时，我看到他好像在谈论购买SUV来证明自己的男子气概（在您的情况下，您主张购买一艘航空母舰）。#2 楼
我看到了两个主要的并发症：我们需要找到适当大小的素数。对于您的“百万位”密钥，素数$ p $和$ q $必须具有约500000位。我想以这种大小进行素数测试要比我们通常使用的2048位素数要难得多（尽管我没有
在快速搜索中找到数字）。
另外，您的主要搜索算法需要更多的熵作为输入，
否则可以从随机性的角度进行攻击。 $ n $和指数$ d $，
其中$ d $的位数与$ n $几乎相同。
简单的平方乘运算需要$ \ log_2 n $平方和平均乘数的一半（取决于有多少个位）。每个
平方/乘法本身都使用一个$ \ log_2 n $位数字，即，将自己在这样的$ \ log_2 n $位数字的$ \ log_2 n $个加法周围（如果实现为
/>两次加法）。那将是$（\ log_2 n）^ 3 $个单位操作，
将用于您的百万位（$ 2 ^ {20} $位）数字$（2 ^ {20}）^ 3 = 2 ^ {60} $
位操作（有一些小因素）。现在我们进入与蛮力DES相似的区域（我不确定其中有多少可并行化）。
有一些更快的求幂和乘法算法，但是如果我
理解正确，那么它们只会改变一个常数，而不会改变实际的复杂度。
评论
$ \ begingroup $
谢谢，我当时想对于这么大的素数进行素数测试会很困难。您能推荐一些探索这种研究途径的文献吗？
$ \ endgroup $
–威廉·希尔德
2011年11月14日14:39
$ \ begingroup $
@Paŭlo：模块化乘法是$（\ log n）^ 2 $个运算，其中有$ \ log n $个以幂运算，因此$（\ log n）^ 3 $。我不知道您的$ 4 $指数来自哪里。对于素数测试，基本的Miller-Rabin测验是$ O（（\ log p）^ 3）$，如果您选择$ p $和$ q $的候选者，则平均需要做大约200000小心一点因此大约需要25000个私钥操作。但是至少密钥对的生成可以分布在多个内核/节点上。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011年11月14日15:52
$ \ begingroup $
@Thomas：好像我在我的段落中错误地计算了$ \ log_2 n $因子来达到4的指数。现在纠正。
$ \ endgroup $
–PaŭloEbermann
2011年11月14日15:57
$ \ begingroup $
@jug：Karatsuba，Schönage-Strassen及其同类对象用于纯整数的乘法；对于RSA，我们需要模乘。即使我们使用次二次算法优化“乘法”部分，模数约简仍然是二次的。我不知道任何低于$ O（（\ log n）^ 3）$复杂度的模幂运算算法。编辑：似乎确实存在这种算法，请参阅此演示文稿。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011年11月14日17:30
$ \ begingroup $
@Paŭlo：对于一个50万位素数，您可以安排生成不是2、3、5、7、11 ...的整数倍的候选对象，最多不超过23。这可以除以数字呼叫Miller-Rabin的次数是3或4，因此我估计有100000次测试（总计$ 200和$ p $和$ q $）。 Miller-Rabin排除了概率至少为$ 3/4 $的非素数，因此平均调用次数受$ 4/3 $限制（实际上更接近1，因为$ 3/4 $的概率是最坏的情况） 。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011年11月14日17:34
评论
$ \ begingroup $
感谢您的答复，尽管我没有得到科学询问与男子气概的证明之间的联系:)
$ \ endgroup $
–威廉·希尔德
2011年11月14日14:34
$ \ begingroup $
为了公平地对待RSA，在FFT范围内有100万比特。加密更接近$ O（n \ log n \ log \ log n）$，而解密$ O（n ^ 2 \ log n \ log \ log n）$。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
2011年11月14日18:13
$ \ begingroup $
一个附录，我实际上做了实验。生成3个$ 2 ^ {20} $位数字$ a $，$ b $和$ m $，并执行各种算术运算（使用GMP）：$ a·b \ bmod m $：0.08s； $ a ^ {65537} \ bmod m $：1.16秒； $ a ^ b \ bmod m $：107873.130s（〜29小时）。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
2011年11月16日15:39
$ \ begingroup $
@Samuel：感谢您抽出宝贵的时间来计算数字！
$ \ endgroup $
–威廉·希尔德
11年11月16日在21:55