# Big-O Notation: Encryption Algorithms

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.

-
Cross-post on SO: stackoverflow.com/questions/10094814/… –  CodesInChaos Apr 10 '12 at 23:18

Most of these algorithms (i.e. the block ciphers DES, Triple DES, AES, Blowfish) are normally only working on a fixed block size, and take approximately the same time independently of input, thus they are $O(1)$.

If you put them into a mode of operation to encrypt longer messages, you usually get an $O(m)$ complexity, where $m$ is the message size, as you have $O(m)$ blocks of data to encrypt.

(One could design modes of operations with different complexity, but they have to touch at least each input bit once to be reversible, thus $O(m)$ is a minimum. Also, with $O(m)$ block cipher calls you can do enough to make it secure, so there is no point of making it slower.)

Two more notes to specific ciphers:

• Yes, Triple-DES usually needs thrice the computing power as DES, but this then gets $O(1)$ or $O(m)$, too.

• Blowfish is known for its quite slow key schedule (which takes as long as encrypting about 4 KB of data), but this is still $O(1)$.

Thus, $O$-notation is not really an interesting thing to look at in block ciphers.

It gets a bit more interesting when we look at algorithms with a varying input size. For the asymmetric algorithm RSA, we have the public (and private) key modulus $n$, and its size $k = [\log_2 n]$ in bits can be considered a security parameter. (The private exponent $d$ is of similar size, while the public exponent $e$ is usually some small number like $3$ or $65537 = 2^{16}+1$.) The message size is then limited by $O(k)$, too.

Encryption and decryption are both modular exponentiations of plaintext or ciphertext modulo $n$, with the respective exponents. With the square-and-multiply algorithm, encryption needs $O(1)$, decryption $O(k)$ multiplications and a similar number of modular reductions, each of $k$-bit or $2k$-bit numbers ... which means about $O(k^2)$ or $O(k^3)$ elementary operations (with a quite small factor, as you use the word size build into your processor).

Decryption can be sped up by storing the factors of $n$, but this still gives only a constant factor, I think (i.e. it reduces the $k$ in the formulas).

RSA also uses one of various padding schemes, but this should be in O(k) and thus not contribute to the complexity.

-