Cryptanalysis, frequency analysis and ciphers

This blog recently examined different strategies for solving Codeword puzzles, including frequency analysis or letter counting. This involves using an understanding of the frequency of occurrence and distribution of different letters to decipher encrypted text. Frequency analysis is a specific type of cryptanalysis, which more broadly means the analysis of information systems to understand the content of encrypted text even if the cryptographic key is unknown. The link between cryptography and puzzle solving is perhaps best exemplified by the recruitment test used at Bletchley Park during the Second World War, where applicants were selected in part based on their ability to solve the Telegraph crossword in under 12 minutes.

Frequency analysis is potentially the very oldest form of cryptanalysis, a methodology outlined by the 9^th century Islamic philosopher Al-Kindi in his Manuscript on Deciphering Cryptographic Messages. In natural languages, some letters and letter combinations occur more frequently than others. The most basic encryption technique, where one letter is simply replaced by another, fails to mask these frequency patterns, making the ciphertext relatively easy to decode provided it is long enough to contain a reasonably representative text.

The inventor Samuel Morse used a form of frequency analysis in the development of his coded messaging system, realising that it made sense to allocate the shortest codes to the most frequently occurring letters. To work out his letter ranking, Morse is said to have consulted his local newspaper printer, where individual letters (type) were assembled into blocks, which were then covered in ink to produce the printed newspaper. The printers needed more of certain letters to create each page, so Morse is said to have simply counted the number of pieces of type for each letter.

For a more sophisticated approach to encryption that is resistant to straightforward frequency analysis, polyalphabetic ciphers make use of multiple substitution alphabets to produce a more complex mapping between source text and encrypted text. The Enigma machines used by Nazi Germany during World War Two are an example of exactly this kind of encryption system. These devices used electro-mechanical rotors to generate the ciphers. Although Polish codebreakers had worked out how to read Enigma messages before the war, the Germans successfully protected subsequent texts by changing the cipher on a daily basis. Cracking this code before it changed was the challenge facing the team at Bletchley Park, whose cryptanalysis work was dramatized in the 2014 film The Imitation Game.

The advent of modern computer software, which can carry out frequency analysis on a massive scale in a matter of seconds, has rendered classical ciphers such as substitution ciphers ineffective. The latest cryptographic systems use encryption algorithms to increase resistance to cryptanalysis, taking encryption methodologies beyond the understanding of mere linguists and into the realm of mathematics and computer science.

For those of us whose numerical pattern matching skills don’t go much further than the 26 letters of the alphabet, there is a fun challenge at 101.computing.net, where you can deploy your frequency analysis skills to decrypt the text provided. Use the frequency distribution depicted to slot in likely letter substitutes one by one to work out the solution. And for the new Wordle obsessives among you, frequency analysis could very well underpin your first guess and guide your subsequent strategy, but that’s a discussion for a whole other blog!