Big-O表示法:加密算法

Question

我目前正在完成一篇关于通过各种加密算法加密数据的论文.

我花了很多时间阅读期刊和论文,但目前还没有找到任何关于其表现复杂性的记录.

有人会想到以下算法的Big-O复杂性吗？

• RSA
• DES
• 三重DES(我期望它与DES的顺序相同)
• AES
• 河豚

先感谢您; 如果你能提供一个信誉良好和可信的来源的链接,如果非常感谢.

Answer 1

部分答案:RSA实验室提供此分析http://www.rsa.com/rsalabs/node.asp?id=2215比较RSA操作与DES

无论是加密,解密,签名还是验证,"RSA操作"本质上都是模幂运算.该计算由一系列模乘法执行.

在实际应用中,通常为公钥选择一个小的公共指数.实际上,整个用户组可以使用相同的公共指数,每个指数具有不同的模数.(当公共指数固定时,模数的素因子有一些限制.)这使得加密比解密和验证更快,比签名更快.使用用于实现RSA算法的典型模幂运算,公钥操作采用O(k2)步,私钥操作采用O(k3)步,密钥生成采用O(k4)步,其中k是比特数在模数."快速乘法"技术,例如基于快速傅立叶变换(FFT)的方法,需要渐近地减少步骤.然而,在实践中,它们并不常见,因为它们具有更高的软件复杂性以及它们对于典型的密钥大小实际上可能更慢.

RSA算法的许多商用软件和硬件实现的速度和效率正在迅速增加; 请参阅http://www.rsasecurity.com/获取最新数据.

相比之下,DES(参见第3.2节)和其他分组密码比RSA算法快得多.DES通常至少是软件的100倍,硬件的速度是硬件的1,000至10,000倍,具体取决于实现方式.由于需求量很大,RSA算法的实现可能会在未来几年缩小差距,但分组密码也会更快.