Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have this cryptogram:

AEOLOMWSUOYCMKBSXNSKFSMDYBCSOBBKAEOLOMSXNSKCSOBBKVSWKCSOBBKHBKISXNSKZKZKAEOLOMWS
UOYCMKBSXNSKSXNSKQYVPVSWKCSOBBKHBKIOMRYBYWOYUSVYCSOBBKSXNSKQYVPVSWKCSOBBKHBKIOMR
YBYWOYUSVYCSOBBKSXNSKQYVPVSWKCSOBBKUSVYCSOBBKZKZKTEVSODZKZKWSUOAEOLOMOMRYSXNSKQY
VPVSWKCSOBBKJEVEWSUOQYVPHBKICSOBBKFSMDYBDKXQYOMRYDKXQYOMRYAEOLOMWSUOYCMKBSXNSKWS
UOBYWOYRYDOVWSUOOMRYNOVDKIKXUOOZKZKIKXUOOAEOLOMWSUOYCMKBSXNSKUSVYCSOBBKZKZKTEVSO
DLBKFYFSMDYBOMRYMRKBVSOGRSCUOIWSUOSXNSKFSMDYBFSMDYBOMRYJEVEWSUOQYVPHBKICSOBBKFSM
DYBVSWKCSOBBKHBKISXNSKZKZKWSUOBYWOYRYDOVWSUOOMRYDKXQYOMRYDKXQYOMRYLBKFYFSMDYBOMR
YMRKBVSOSXNSKQYVPVSWKCSOBBKEXSPYBWIKXUOOSXNSKPYHDBYDSXNSKQYVPAEOLOMWSUOYCMKBSXNS
KCSOBBKGRSCUOIQYVPOMRYFSMDYBWSUOBYWOYRYDOVWSUOOMRYYCMKBWSUOZKZKCSOBBKGRSCUOIWSUO
SXNSKFSMDYBFSMDYBOMRYDKXQYOMRYDKXQYOMRYXYFOWLOBIKXUOOZKZKWSUOSXNSKHBKIHBKIOMRYBY
WOYUSVYCSOBBKSXNSKQYVPVSWKCSOBBKHBKIOMRYBYWOYUSVYCSOBBKSXNSKQYVPVSWKCSOBBKFSMDYB
CSOBBKAEOLOMSXNSKCSOBBKGRSCUOIWSUOSXNSKFSMDYBFSMDYBOMRYNOVDKIKXUOOZKZKIKXUOOWSUO
BYWOYRYDOVWSUOOMRYEXSPYBWIKXUOOSXNSKPYHDBYDSXNSKQYVPTEVSODCSOBBKLBKFYHBKIFSMDYBC
SOBBKHBKIWSUOBYWOYRYDOVWSUOOMRYJEVEWSUOQYVPHBKICSOBBKFSMDYBOMRYZKZKDKXQYVSWKOMRY
ZKZKWSUOAEOLOMOMRYAEOLOMWSUOYCMKBSXNSKKVZRKVSWKWSUOGRSCUOIYCMKBSXNSKMRKBVSOCSOBB
KGRSCUOIQYVPOMRYFSMDYBWSUOBYWOYRYDOVWSUOOMRYQYVPVSWKOMRYFSMDYBZKZKWSUOSXNSKVSWKC
SOBBKHBKISXNSKZKZKWSUOBYWOYRYDOVWSUOOMRYDKXQYOMRYDKXQYOMRYLBKFYFSMDYBOMRYMRKBVSO
SXNSKQYVPVSWKCSOBBKAEOLOMWSUOYCMKBSXNSKFSMDYBCSOBBKAEOLOMSXNSKCSOBBKVSWKCSOBBKHB
KISXNSKZKZKAEOLOMWSUOYCMKBSXNSKSXNSKQYVPVSWKCSOBBKLBKFYFSMDYBOMRYMRKBVSOSXNSKQYV
PVSWKCSOBBKFSMDYBCSOBBKAEOLOMSXNSKCSOBBKYCMKBWSUOZKZKCSOBBKGRSCUOIWSUOSXNSKFSMDY
BFSMDYBOMRYSXNSKQYVPVSWKCSOBBKDKXQYOMRYDKXQYOMRYHBKIOMRYBYWOYUSVYCSOBBKZKZKWSUOA
EOLOMOMRYSXNSKQYVPVSWKCSOBBKLBKFYFSMDYBOMRYMRKBVSOSXNSKQYVPVSWKCSOBBKFSMDYBCSOBB
KAEOLOMSXNSKCSOBBKYCMKBWSUOZKZKCSOBBKGRSCUOIWSUOSXNSKFSMDYBFSMDYBOMRYJEVEWSUOQYV
PHBKICSOBBKFSMDYBGRSCUOIWSUOSXNSKFSMDYBFSMDYBOMRYEXSPYBWIKXUOOSXNSKPYHDBYDSXNSKQ
YVPWSUOBYWOYRYDOVWSUOOMRYGRSCUOIWSUOSXNSKFSMDYBFSMDYBOMRYOMRYZKZKDKXQYVSWKOMRYZK

Clearly it's a Caesar cipher with a simple shift of 10, which decrypts to:

QUEBECMIKEOSCARINDIAVICTORSIERRAQUEBECINDIASIERRALIMASIERRAXRAYINDIAPAPAQUEBECMI
KEOSCARINDIAINDIAGOLFLIMASIERRAXRAYECHOROMEOKILOSIERRAINDIAGOLFLIMASIERRAXRAYECH
OROMEOKILOSIERRAINDIAGOLFLIMASIERRAKILOSIERRAPAPAJULIETPAPAMIKEQUEBECECHOINDIAGO
LFLIMASIERRAZULUMIKEGOLFXRAYSIERRAVICTORTANGOECHOTANGOECHOQUEBECMIKEOSCARINDIAMI
KEROMEOHOTELMIKEECHODELTAYANKEEPAPAYANKEEQUEBECMIKEOSCARINDIAKILOSIERRAPAPAJULIE
TBRAVOVICTORECHOCHARLIEWHISKEYMIKEINDIAVICTORVICTORECHOZULUMIKEGOLFXRAYSIERRAVIC
TORLIMASIERRAXRAYINDIAPAPAMIKEROMEOHOTELMIKEECHOTANGOECHOTANGOECHOBRAVOVICTORECH
OCHARLIEINDIAGOLFLIMASIERRAUNIFORMYANKEEINDIAFOXTROTINDIAGOLFQUEBECMIKEOSCARINDI
ASIERRAWHISKEYGOLFECHOVICTORMIKEROMEOHOTELMIKEECHOOSCARMIKEPAPASIERRAWHISKEYMIKE
INDIAVICTORVICTORECHOTANGOECHOTANGOECHONOVEMBERYANKEEPAPAMIKEINDIAXRAYXRAYECHORO
MEOKILOSIERRAINDIAGOLFLIMASIERRAXRAYECHOROMEOKILOSIERRAINDIAGOLFLIMASIERRAVICTOR
SIERRAQUEBECINDIASIERRAWHISKEYMIKEINDIAVICTORVICTORECHODELTAYANKEEPAPAYANKEEMIKE
ROMEOHOTELMIKEECHOUNIFORMYANKEEINDIAFOXTROTINDIAGOLFJULIETSIERRABRAVOXRAYVICTORS
IERRAXRAYMIKEROMEOHOTELMIKEECHOZULUMIKEGOLFXRAYSIERRAVICTORECHOPAPATANGOLIMAECHO
PAPAMIKEQUEBECECHOQUEBECMIKEOSCARINDIAALPHALIMAMIKEWHISKEYOSCARINDIACHARLIESIERR
AWHISKEYGOLFECHOVICTORMIKEROMEOHOTELMIKEECHOGOLFLIMAECHOVICTORPAPAMIKEINDIALIMAS
IERRAXRAYINDIAPAPAMIKEROMEOHOTELMIKEECHOTANGOECHOTANGOECHOBRAVOVICTORECHOCHARLIE
INDIAGOLFLIMASIERRAQUEBECMIKEOSCARINDIAVICTORSIERRAQUEBECINDIASIERRALIMASIERRAXR
AYINDIAPAPAQUEBECMIKEOSCARINDIAINDIAGOLFLIMASIERRABRAVOVICTORECHOCHARLIEINDIAGOL
FLIMASIERRAVICTORSIERRAQUEBECINDIASIERRAOSCARMIKEPAPASIERRAWHISKEYMIKEINDIAVICTO
RVICTORECHOINDIAGOLFLIMASIERRATANGOECHOTANGOECHOXRAYECHOROMEOKILOSIERRAPAPAMIKEQ
UEBECECHOINDIAGOLFLIMASIERRABRAVOVICTORECHOCHARLIEINDIAGOLFLIMASIERRAVICTORSIERR
AQUEBECINDIASIERRAOSCARMIKEPAPASIERRAWHISKEYMIKEINDIAVICTORVICTORECHOZULUMIKEGOL
FXRAYSIERRAVICTORWHISKEYMIKEINDIAVICTORVICTORECHOUNIFORMYANKEEINDIAFOXTROTINDIAG
OLFMIKEROMEOHOTELMIKEECHOWHISKEYMIKEINDIAVICTORVICTORECHOECHOPAPATANGOLIMAECHOPA

OK, 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 Caesar 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.

share|improve this question
    
Just in case you didn't recognize it, the words appear to be from the NATO phonetic alphabet. – Ilmari Karonen May 30 at 8:22
up vote 5 down vote accepted

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.

share|improve this answer

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.