Can we say that any shift cipher to be decrypted needs an algorithm of complexity “n * n!”? (where n is number of possible values. 26 in case of English language).

My reasoning related to reaching n * n! was as follows:

Take the word BRAZIL for example. We have 26 possibilities for B, 25 for R, 24 forA, etc. ThusO(n!). We also can have this 26 times, B was A now, but is a G in the next time, thus 26 which isO(n)henceO(n * n!)`.

  • $\begingroup$ Probably not. What's $n$ anyway? $\endgroup$ – fkraiem Feb 11 '15 at 20:37
  • $\begingroup$ @fkraiem see updated question $\endgroup$ – tony9099 Feb 11 '15 at 20:42
  • $\begingroup$ Please note that "decryption" usually means an algorithm which knows the key. And knowing the key, you should be able to decrypt a text in O(length of text). $\endgroup$ – Paŭlo Ebermann Feb 12 '15 at 19:13
  • $\begingroup$ @PaŭloEbermann good point ! $\endgroup$ – tony9099 Feb 13 '15 at 15:02

How on earth did you arrive at that formula?

You can break a Caesar cipher by calculating the result of applying all of the $n-1$ (i.e., 25) possible shifts to the ciphertext and picking the one that makes sense. The computational complexity is just $\mathcal{O}(n)$.

If you want to automate the process based on frequency analysis, the correlation step where you pick the most likely offset would perhaps have $\mathcal{O}(n^2)$ complexity, but in practice you could probably achieve this by only considering a small subset of the most common letters. (For the English alphabet, E, T, A, I, O and N should suffice).

  • $\begingroup$ Thanks. I updated my answer and included my reasoning. Can you please check and let me know where/how I got it wrong ? $\endgroup$ – tony9099 Feb 11 '15 at 21:46
  • $\begingroup$ @tony9099 In a Caesar shift cipher, every letter is shifted by the same offset. So there are just 25 possible keys to test. That's all. You appear to be thinking of a monoalphabetic substitution cipher, where any letter can be mapped to any other. Although this has a larger keyspace (26 factorial), the code can still be broken by frequency analysis with O(n^2) complexity. (Actually I don't understand the last bit where you say we "have this 26 times". What does that mean?) $\endgroup$ – r3mainer Feb 11 '15 at 22:01
  • 1
    $\begingroup$ Strictly speaking, wouldn't brute-force be $O(2^n)$ just like it is on every other scheme (because $n$ is the length of the key, not number of possible keys)? $\endgroup$ – cpast Feb 11 '15 at 22:53
  • $\begingroup$ @cpast No. A 26-bit key would give you a keyspace of 2^26 (64M) permutations. But a key that consists of a single number from 1 to 25 can only give you 25 permutations. $\endgroup$ – r3mainer Feb 11 '15 at 23:10
  • $\begingroup$ @squeamishossifrage EDIT: Never mind, I didn't notice the questions quirky definition of $n$. $\endgroup$ – cpast Feb 11 '15 at 23:19

If you consider arbitrary permutations, you have $\frac{n(n+1)}{2}$ possibilities. That means, $O(n^2)$ is the correct complexity in big-O notation, but I don't understand why you need that at all, if you can provide the result as exact formula.

Caesar cipher contains just a subset of $n$ possibilities, and therefore obviously $O(n)$.

Anyway, this doesn't cover algorithms like frequency analysis, which works both for the Caesar cipher and the general simple substitution cipher.


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.