问大O表示法:加密算法

EN

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

RSA算法有多快？ "RSA操作“，无论是加密、解密、签名还是验证，本质上都是一个模幂运算。这种计算是通过一系列模乘来完成的。 在实际应用中，通常为公钥选择一个小的公共指数。事实上，整个用户组可以使用相同的公共指数，每个指数都有一个不同的模数。(当公共指数固定时，对模数的素因子有一些限制。)这使得加密比解密快，验证比签名快。采用典型的模幂算法，公钥运算采用O(k^2)步，私钥运算采用O(k^3)步骤，密钥生成采用O(k^4)步，其中k是模中的位数。快速乘法技术，如基于快速傅立叶变换(FFT)的方法，需要渐进的较少的步骤。然而，在实践中，它们并不常见，因为它们的软件复杂度更高，而且对于典型的密钥大小，它们的速度可能会更慢。 许多商业上可用的RSA算法的软件和硬件实现的速度和效率都在迅速提高；有关最新数据，请参阅http://www.rsasecurity.com/。 相比之下，DES (参见3.2节)和其他块密码比RSA算法快得多。根据具体的实现，DES在软件上的速度通常是100倍，在硬件上是1000到10,000倍。由于需求大，RSA算法的实现可能会在未来几年缩小一些差距，但是块密码也会变得更快。

需要注意的一点(取决于您是否正在为您的论文编写代码)：RSA的大多数现实实现实际上将使用RSA来进行AES密钥交换。因此，用于加密/解密的O(k^2)和O(k^3)操作仅用于加密AES密钥。AES在软件/硬件上的速度是100到10K，用于交换数据的实际分组密码--这样，您就可以利用PKI (通过RSA) w/o来支付超常的计算代价。

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

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