根据Ars Technica的椭圆曲线入门,当复合数字“太大”时,使用二次筛和通用数场筛可以更容易分解。

对此没有详细解释在这个站点上,人们普遍认为RSA加密处于挤压陷阱中,随着分解算法和设备变得越来越强大,RSA模数越来越大,同时又越来越接近某种上限,显然结果模量的安全性下降。

请赐教:为什么无法无限期增加RSA密钥的大小?

#1 楼

我从来没有听说过当模数增加时RSA变得不那么安全。显然,强度的增长速度不及位数,而是仅次于指数增长。

如果持续增长(增长不接近零),那么就没有了。 “陷阱”。例如,在这里检查得出的结论是,时间复杂度(即强度)不是指数增长而是超多项式增长。

如果您仔细查看Ars Technica中的文章,那么您会发现将会看到作者主要声称密钥大小的增长对于低功耗设备而言是不可持续的。 ECC在这些情况下肯定是有益的。

以下说法“随着数字(ed:密钥大小)变大,分解大数与乘大数的难度之间的差距正在缩小”如fgrieu正确识别。它的增长速度并没有最初想象的那么快。密钥强度的计算方法与对称算法的密钥计算方法不同。

评论


$ \ begingroup $
谢谢!那么,RSA的整个概念在未来的可用性/安全性要比ECC低,那么它就没有意义了吗? (低功耗设备除外,这些设备受益于ECC较小的密钥大小)
$ \ endgroup $
–快速反应
16 Dec 14'2:01

$ \ begingroup $
两者都容易受到量子计算攻击,而RSA具有(非常)微小的优势。密钥大小和操作速度(尝试在计算机上创建16Kbit密钥对)可能会妨碍甚至更大的计算机。即使在大型计算机上,而不仅仅是在低功耗设备上,这种密钥大小都难以处理。
$ \ endgroup $
–马腾·博德威斯♦
16/12/14在8:52



$ \ begingroup $
@ fast-reflexes更高安全级别下的RSA性能严重下降。没有人希望Web服务器使用15000位RSA密钥,但是512位ECC密钥非常实惠。 [但这并不是说256位的安全级别有意义。
$ \ endgroup $
– CodesInChaos
16 Dec 14'9:05



$ \ begingroup $
因此,对于“ fun”(如果您的加热器放弃了):time openssl genrsa -f4 -out outkey16384。请注意,这将搜索两个8192位素数,而搜索素数是不确定的(即,可能需要很短的时间,也可能需要很长时间)。当然,解密或签名内容的速度在服务器上更是一个问题。
$ \ endgroup $
–马腾·博德威斯♦
16 Dec 14在15:05



$ \ begingroup $
谢谢大家!您杀死了我不时在不同情况下听到的一个神话!
$ \ endgroup $
–快速反应
16 Dec 15'在13:43

#2 楼

我完全不了解网站上的这种说法。 RSA对于大的$ N $来说变得非常昂贵的说法是正确的,但是要说加密/解密成本与分解之间的差距减小了,那根本没有道理!显然,描述最佳分解算法的运行时间的函数渐近地大于$ n ^ 3 $(解密RSA的时间)。因此,随着密钥大小$ n $变大,差距只会增加。