Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
Cross-post on SO: stackoverflow.com/questions/10094814/… –  CodesInChaos Apr 10 '12 at 23:18
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.