I'm trying to figure out what the time complexity of RC4 encryption & decryption algorithms is, in big-O-notation.

  • $\begingroup$ This is very similar to Complexity of ECB and OFB; note that most stream ciphers like RC4 behave very much like a block cipher in OFB mode. Anyway, the short answer is, it's all $O(n)$. $\endgroup$ – Ilmari Karonen May 26 '12 at 18:10

Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit.


 c = m ⊕ G(k)
 m = c ⊕ G(k)

Where c is ciphertext, m is plaintext, G is the RNG and k is the key.

As such, all stream ciphers should be O(n) against the length of input data.

  • $\begingroup$ thank you very much !! How about for Block Cipher like AES? is it O(n) too? $\endgroup$ – Kriss Wen May 23 '12 at 6:15
  • $\begingroup$ Most block ciphers will be O(n) against the number of blocks, yes. $\endgroup$ – Polynomial May 23 '12 at 7:30
  • 2
    $\begingroup$ Keep in mind, though, that time complexity is practically meaningless as a measure of speed in this sense, because it tells you nothing about how fast the cipher is. If it always takes 10 milliseconds to encrypt a block in a cipher, it's O(n). If it always takes 10 minutes to encrypt a block in a cipher, it's still O(n). $\endgroup$ – Polynomial May 23 '12 at 7:39

Any reversible cipher will need at least $\Omega(n)$ time (where $n$ is the size of the plaintext), since we need to touch each bit at least once.

A stream cipher (i.e. deterministic pseudo-random bit generator) does some fixed amount of work for each bit (or larger unit) of output (with maybe some initial preparation overhead), which is $O(n)$.

A block cipher needs some fixed (or at least, bounded) amount of work for each block.

All common bulk encryption block cipher modes of operation need just $O(n)$, too, since they execute the block cipher once (or another fixed amount) for each block of data, together with some fixed amount of work around these calls.

This shows that it is possible to do encryption in $O(n)$, thus I would never ever use a cipher for bulk encryption which takes longer than $O(n)$ ... and I don't think there are any serious proposals of such ones.

As Polynomial noted, the input size complexity doesn't tell anything about the actual speed of a cipher, as they are all in the same complexity class.

A more interesting use of complexity is when we have a family of algorithms with some modifiable security parameter $k$ (such as key size). Then we can look at the complexity of encrypting or decrypting (or various attacks on the cipher).

But still actual time and other resource usage when implementing the cipher on a computer (or other devices) for common choices of the security parameters is interesting, when comparing it to other competing algorithms.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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