Computer Cipher Solving – Lesson 7: cross-reduction

Last September I wrote a series of blog posts on computer cipher solving. They continue to get quite a few views, so it seems to be a popular topic. Today I’m resuming the topic by discussing cross-reduction of word patterns. This method has been used for centuries with simple substitution ciphers and it is still useful today for several types of ACA ciphers. Clearly it can be done without computers, but it is simple to program and a great time-saver. Often it’s the only way to break some tough ciphers. Don’t confuse this usage with cross-reduction in mathematics, which is a method to reduce fractions. The idea is to use the patterns of one word to reduce the possible solutions of a second word and vice versa.

The basic concept is simple. Take two ciphertext words enciphered with the same key, preferably long words, and compare the patterns to produce combinations of possible words that fit both patterns. It’s easier to understand by looking at an example. Headlines puzzles contain simple substitution ciphers, but they are often very short and have uncommon words such as proper nouns so usual methods like hill-climbing may not work. Consider this ciphertext from a recent ACA Headlines puzzle: EA’I NG THJLUZI IGIAHN AWBA’I MBCG. My hillclimber had no luck with it, but cross-reduction solved it easily.

Begin by reading through a word list and identifying all words with same pattern as THJLUZI, which is to say, all 7-letter words with no repeated letters. That sounds like a large list, but you can reduce its size by considering that Headlines puzzles use K3 alphabets to encipher. No, that’s not Kindergarten – 3rd grade. That K3 as used here: Click on Keywords to get an explanation. The significance is that if a letter stands for itself in a K3 substitution, then all the letters must stand for themselves. In effect, the entire plaintext would be showing. Since it isn’t, that means none of the letters of the words stands for itself. That means you can eliminate all words beginning with T, having H as the second letter, etc. Next do the same thing with the word IGIAHN. Here, the 1st and 3rd letters are the same, so your list will probably be somewhat shorter. These lists may be saved in arrays or in files. Finally, you compare the two lists word by word to produce pairs of words such that there are no conflicts. That means the 2nd letter of word 1 must be the same as the 5th letter of word 2, the last letter of word 1 must be the same as the 1st letter of word 2, and so on.

The easiest way to do this with programming is to write a pattern function, one that produces ABACDEF for IGIAHN, etc. When you test every word pair (word1 and word2) from your lists all you have to do is ask if the pattern(word1+word2) = pattern(THJLUZI +IGIAHN). If it does, then display it or save that pair as a possible solution. My program produced about 200 pairs that fit the pattern. That didn’t appear to help much at first, especially since several combos seemed like plausible phrases from a newspaper headline (e.g. AEROBIC CYCLES). But notice that two words in the ciphertext end with an apostrophe I. That strongly suggests that I stands for plaintext S. Looking through my lists, there was only one word there that looked possible for the 2nd word: SYSTEM. The combos included DEVIOUS SYSTEM and LEPROUS SYSTEM, but it wasn’t hard to spot NERVOUS SYSTEM as the most likely candidate, and that proved to be correct. The solution is “IT’S MY NERVOUS SYSTEM THAT’S LAZY”. This method works best when you can find two words that have many common letters; if they’re adjacent, too, that’s even better, but not necessary. Needless to say, it only works if both words are in your word lists. When I get no solutions this way, I sometimes drop the final letter of one of the words in case it’s an inflected form (e.g. plural or past tense) and try again hoping the base word will be in the list.

This method will work with Key Phrase ciphers, too, even though that doesn’t use simple substitution. You just have to write a different comparison routine. Of course it works with Xenocrypts as long as you have good word lists for the language.


Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.