2
$\begingroup$

Does anyone know of an efficient way of breaking a modified Caesar cipher (where the key is a set of numbers (the amount of shift) that is repeated throughout the plaintext, e.g. {1,2,3,4,5}) via brute-force?

The way I'm currently trying to crack it is as follows:

  1. Generate all possible key combinations ( 5 numbers between 1 & 25)
  2. Use the generated key to "decipher" the message
  3. Use frequency analysis on deciphered messages to see which one is the best fit

As you can probably guess, the way I've come up with is the least efficient (in terms of time and memory) and I was wondering what would be the best way to decipher the message.

$\endgroup$
  • $\begingroup$ There are only 25 keys, so this approach seems okay. You could also search the deciphered message for common words like "the", "and". Of course, this assumes the plaintext language is English... $\endgroup$ – Stone True Nov 22 '15 at 2:52
  • $\begingroup$ @StoneTrue Yes, the plain text is English.However, I believe that the key is repeated for chunks of the text. For example: {1, 2, 3, 4, 5} would work for the letters 1-5 then 6-10 etc. So, searching for words like "the" would work unless it's plaintext, right? $\endgroup$ – TGRHavoc Nov 22 '15 at 2:53
  • 1
    $\begingroup$ Not familiar with the MODIFIED caeser, but it seems similar to a Vengiere cipher. $\endgroup$ – Stone True Nov 22 '15 at 3:29
  • $\begingroup$ @StoneTrue Just had a look and it's does look very similar and the main difference is the key... Ok, now with that information in mind, do know of any good resources that might help? $\endgroup$ – TGRHavoc Nov 22 '15 at 3:44
  • 1
    $\begingroup$ Nothing other than general references like Friedman's Principles of Military Cryptanalysis. It seems determining the key length is the first step. $\endgroup$ – Stone True Nov 22 '15 at 3:50
1
$\begingroup$

Assume the length is $n$. If the cipher text is $c_0, c_1, c_2, \ldots, c_N$ then consider the sub-text consisting of the characters $c_0, c_n, c_{2n},\ldots$. These have all been encrypted with the same Caesar, and you can break it by frequency analysis (the shifted 'e' should be the most common in standard English texts, or else maybe the 't' etc.). Suppose the shift you find is $s_0$. Then try the shifts $s_0 + 1, \ldots s_0 + (n-1)$ for the next sub-texts and see if you have a result. If not, try another $n$. This way you only brute force over $n$, essentially.

You could also determine the length $n$ by a statistical method (index of coincidence) or Kasiski (finding long repeats) as well. These will work for any Viginère cipher. But the above might be simpler if you already know that the shifts will be cyclic and consecutive.

| improve this answer | |
$\endgroup$
0
$\begingroup$

I'll speak to the solution after I speak to the method. What you have is not exactly a modified Caesar, its a polyalphabetical cipher. Because they are often the same thing. A Vigenere type of cipher is really just a list of Caesar ciphers keyed to some keyword. Your 12345 key is similar to the idea of a Vigenere cipher with a key of ABCDE. If you convert your numbers into an alphabet (A=1, B=2) and then use one of the Vigenere solvers, I bet you would be able to solve it with the press of a button. This is assuming the Caesar destination alphabet is a straight alphabet, but if it was also keyed, that would just change the type of Vigenere you solved for... Quagmire I-IV.

| improve this answer | |
$\endgroup$
0
$\begingroup$

What you describe is a Vigenère cipher, named after (but not actually invented by) the 16th century French cryptographer Blaise de Vigenère.

Breaking it efficiently basically involves two stages:

  1. Determine the most likely key length. There are several ways to do that, such as:

    • Kasiski examination, which involves finding repeating substrings in the ciphertext and looking for a common factor of the distances between their occurrences, or
    • the Friedman test, which involves splitting the ciphertext into blocks of $n$ characters, lining up those blocks into $n$ vertical columns, computing the index of coincidence (basically, the probability of two characters randomly picked from the same column being the same) and looking for the key length $n$ that maximizes this.
  2. Once you've guessed the key length $n$, split the ciphertext into $n$ columns as described above, such that each column is encrypted with the same element of the key, and apply standard frequency analysis to each of those columns as if you were breaking a simple Caesar cipher.

For more information, take a look at the various questions tagged with the tag here on crypto.SE, such as:

Of course, if you're lazy, there are also tools for automating this process, such as pygenere. You can also find several online Vigenère cipher solvers (such as this, this or this one) if you Google for them.

| improve this answer | |
$\endgroup$

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.