Big-O Notation: Encryption Algorithms

Question

I am currently completing a dissertation concerning the encryption of data through a variety of cryptographic algorithms.

I have spent much time reading journals and papers but as yet have been unable to find any record of their performance complexity.

Would anyone have an idea of the Big-O complexity of the following algorithms?

• RSA
• DES
• Triple DES (Which I would expect to be of the same order as DES)
• AES
• Blowfish

Thank you in advance; if you could provide a link to a reputable and citable source if would be very much appreciated.

Answer 1

Partial answer: RSA Laboratories provides this analysis, archived from rsa.com, comparing RSA operations vs. 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.

Answer 2

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.