What is the time complexity of the RC4 encryption & decryption algorithms?

Question

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

Answer 1

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.

Answer 2

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.

So:

 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.