Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
With AES-CTR the computation time to encrypt a message of lengh $n$ blocks is $n$ computations of the block cipher.
What is the running time to encrypt a message of $n$ bits using a stream cipher, like Salsa, Snow, trivium or any other stream cipher? How can I (generally) calculate a stream cipher computation cost?
For any typical stream cipher (including block ciphers in streaming modes like CBC / CFB / OFB / CTR), the time needed to encrypt a message consists of two parts:
Most ciphers will process the message (or at least generate the keystream) in chunks of more than one bit at a time. For block ciphers in streaming modes, the chunk size will typically equal the block size of the underlying block cipher. For dedicated stream ciphers, the chunk size may vary, even between different implementations of the same cipher. For some examples, RC4 generates its keystream in chunks of 8 bits, whereas Trivium can generate anything from 1 to 64 bits at a time, depending on how strongly the implementation is parallelized.
In any case, the typical runtime will be of the form $a + b \lceil n / c \rceil$, where $a$ is the setup (+ teardown) time, $b$ is the time per chunk, $c$ is the chunk length and $n$ is the message length (in appropriate units, typically bits or bytes). Asymptotically, this will be ${\rm O}(n)$.
One peculiar corner case is that, for ciphers that require the message to be unambiguously padded to a multiple of the chunk size (such as block ciphers in CBC mode), messages that already happen to be a whole number of chunks long will typically need to have an extra chunk appended, so that the time cost becomes of the form $a + b \lceil (n + 1) / c \rceil$.
Also, it should be noted that these are all theoretical timings. In the real world, if you graph the time needed to encrypt messages of varying size on a real CPU, you're likely to see all sorts of weird jags, kinks and noise due to things like cache misses, branch prediction, microcode optimizations, interrupts, concurrent threads, etc. On a large enough scale, though, the overall pattern will still generally look approximately linear in the message length.
