encryption - 大 O 符号 : Encryption Algorithms

Question

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

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

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

RSA

DES

三重 DES(我希望与 DES 的顺序相同)

AES

河豚

先感谢您;如果您能提供指向信誉良好且可引用的来源的链接，将不胜感激。

Answer 1

部分答案:RSA 实验室提供了此分析，archived from rsa.com ，比较 RSA 操作与 DES。

How fast is the RSA algorithm?

An "RSA operation," whether encrypting, decrypting, signing, or verifying is essentially a modular exponentiation. This computation is performed by a series of modular multiplications.

In practical applications, it is common to choose a small public exponent for the public key. In fact, entire groups of users can use the same public exponent, each with a different modulus. (There are some restrictions on the prime factors of the modulus when the public exponent is fixed.) This makes encryption faster than decryption and verification faster than signing. With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O(k^2) steps, private key operations take O(k^3) steps, and key generation takes O(k^4) steps, where k is the number of bits in the modulus. ``Fast multiplication'' techniques, such as methods based on the Fast Fourier Transform (FFT), require asymptotically fewer steps. In practice, however, they are not as common due to their greater software complexity and the fact that they may actually be slower for typical key sizes.

The speed and efficiency of the many commercially available software and hardware implementations of the RSA algorithm are increasing rapidly; see http://www.rsasecurity.com/ for the latest figures.

By comparison, DES (see Section 3.2) and other block ciphers are much faster than the RSA algorithm. DES is generally at least 100 times as fast in software and between 1,000 and 10,000 times as fast in hardware, depending on the implementation. Implementations of the RSA algorithm will probably narrow the gap a bit in coming years, due to high demand, but block ciphers will get faster as well.