How does this Cesar Cipher work?

Question

Suppose I have this cryptogram: http://pastebin.com/QpfRMBg1

Clearly it's a Ceasar Cipher which decrypts to: http://pastebin.com/r50heZuU with a simple shift of 10... OKay, no big deal. Let's take a look at the first line two lines or so: QUEBEC MIKE OSCAR INDIA VICTOR SIERRA QUEBEC INDIA SIERRA LIMA SIERRA XRAY INDIA PAPA QUEBEC MIKE OSCAR INDIA INDIA GOLF LIMA SIERRA XRAY ECHO ROMEO KILO SIERRA INDIA GOLF LIMA SIERRA XRAY ECHO

If you take the first letter you get QMOIVSQISLSXIPQMOIIGLSXERKSIGLSXE which another Cesar shift of 4 gives you MIKEROMEOHOTELMIKEECHOTANGOECHOTA or MIKE ROMEO HOTEL MIKE ECHO TANGO ECHO TA or MRHMETET and another shift of 4 gives INDIAPAP... can somebody explain this? is it famous and explained in a lecture somewhere? It appears infinite from my small sampling.

Thanks!

Answer 1

Yes, it's a fun little cryptogram which recursively decrypts to meaningful words. It's not difficult to create such a ciphertext, you just need to generate it bottom-up. Here is how to do it:

---

Let there exist a mapping $\text{M} (c) = \mathrm{W}$ which maps every distinct letter $c$ to some word $\mathrm{W}$, for instance "e" -> "echo", "d" -> "delta", and so on. You can use more than one mapping, but this will do fine. The mapping must be bijective (one-to-one, so that it can be reversed for decryption).

1. Select a random character $c$ in your alphabet, and let $\mathrm{W} = c$ (one-word character).

2. Generate a new "expanded word" $\mathrm{W}' = \mathrm{M} (c_1) || \mathrm{M} (c_2) || \cdots \|| \mathrm{M} (c_k)$.

3. Shift this new word to get $\mathrm{C}' = \text{Caesar}_n (\mathrm{W}')$.

4. If $\mathrm{C}'$ is large enough, return it. Otherwise, recurse to step 2 with $\mathrm{C} \leftarrow \mathrm{C}'$.

If you go through the steps in reverse to try and decrypt it, you'll see this construction produces the behaviour you observe with the given cryptogram. It can be made as large as desired. Backwards:

1. Read the ciphertext as $\mathrm{W}$.

2. Decrypt this word, as $\mathrm{W}' = \mathrm{Decrypt}_n (\mathrm{C}')$.

3. If this word only contains a single character, we're finished.

4. Split the word into multiple distinct words (e.g. "echodelta" -> "echo" "delta").

5. Apply the inverse mapping $\mathrm{M}^{-1}$ to each word to obtain the "reduced" word $\mathrm{W}$.

6. Recurse to step 2 with $\mathrm{C}' \leftarrow \mathrm{W}$.

---

Using different shift values $n$ for every depth is valid, you can even change the letter to word mapping and it'll still work (and the resulting ciphertext will be a little more varied).

I recommend you try and generate a small one yourself. First, create a mapping table at your leisure (you can reuse the one used in the given ciphertext, using military codewords). Then, apply the generation algorithm until you have a sufficiently big ciphertext. Then, write down the inverse mapping table to help you with decryption, and apply the decryption algorithm.

It may also help drawing some kind of tree representing each generation step, and see how you can traverse the tree backwards, reversing each step.