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'm trying to figure out what the time complexity of RC4 encryption & decryption algorithms is, in big-O-notation.

share|improve this question
    
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)$. –  Ilmari Karonen May 26 '12 at 18:10
add comment

2 Answers 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.

share|improve this answer
    
thank you very much !! How about for Block Cipher like AES? is it O(n) too? –  Kriss Wen May 23 '12 at 6:15
    
Most block ciphers will be O(n) against the number of blocks, yes. –  Polynomial May 23 '12 at 7:30
2  
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). –  Polynomial May 23 '12 at 7:39
add comment

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.

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.