5

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

我花了很多时间阅读期刊和论文，但还没有找到任何关于其性能复杂性的记录。

有人知道以下算法的 Big-O 复杂性吗？

  • RSA
  • DES
  • 三重 DES（我希望与 DES 具有相同的顺序）
  • AES
  • 河豚

先感谢您; 如果您能提供一个有信誉且可引用的来源的链接，我们将不胜感激。

4

3 回答 3

8

部分答案：RSA 实验室提供了此分析，从 rsa.com 存档，比较 RSA 操作与 DES。

RSA算法有多快？

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

在实际应用中，通常选择一个小的公共指数作为公钥。事实上，整个用户组都可以使用相同的公共指数，每个指数具有不同的模数。（当公共指数固定时，模数的主要因素有一些限制。）这使得加密比解密更快，验证比签名更快。使用用于实现 RSA 算法的典型模幂算法， 公钥操作需要 O(k^2) 步，私钥操作需要 O(k^3)步，密钥生成需要 O(k^4) 步，其中k 是模数中的位数. “快速乘法”技术，例如基于快速傅里叶变换 (FFT) 的方法，需要渐近较少的步骤。然而，在实践中，它们并不常见，因为它们的软件复杂性更高，而且对于典型的密钥大小，它们实际上可能更慢。

RSA 算法的许多商用软件和硬件实现的速度和效率正在迅速提高；有关最新数据，请参见http://www.rsasecurity.com/。

相比之下，DES（见第 3.2 节）和其他分组密码比 RSA 算法快得多。DES 通常在软件中至少快 100 倍，在硬件中快 1,000 到 10,000 倍，具体取决于实现。由于需求量大，RSA 算法的实现可能会在未来几年稍微缩小差距，但分组密码也会变得更快。

于 2012-04-10T19:14:34.050 回答
4

One thing to note (depending upon if you are coding to your dissertation): most real-world implementations of RSA will actually use RSA to do an AES key exchange. So the O(k^2) and O(k^3) operations for encrypt/decrypt, respectively, are only in terms of encrypting the AES key. AES being 100-10K times faster in software/hardware does the actual block cipher for the data being exchanged--this way, you get to take advantage of PKI (via RSA) w/o having to pay the inordinate computational price.

于 2012-11-26T23:19:30.670 回答
1

一个块的对称密码复杂度为 O(1)。

只留下您列表中的 RSA，并且答案非常依赖于实现，这取决于大整数乘法的实现程度、指数的选择等......

于 2012-04-16T17:03:34.937 回答