The author and physicist Simon Singh writes about the philosopher Abu Yusuf al-Kindi (801-873) and his use of frequency analysis to break codes. According to the 2010 article in The American Statistician by Lyle D. Broemeling, al-Kindi is author of the oldest known book on cryptology and his work is considered an early use of statistical inference. From Singhs website:

Usually, encryption meant substituting conventional letters with other letters (or symbols), a system known as the substitution cipher. So instead of writing A the sender might write J, instead of B he might write W, and so on. The Swedish singing sensation of the seventies would then be encrypted as JWWJ.

The substitution cipher, at first sight, offers a high level of security. An enemy interceptor looks at the encrypted message and has to guess which of the 26 letters does A really represent? If by some fluke he guesses right, then he has to guess which of the other 25 letters for B really represent? And so on. The chances of correctly guessing all 26 letters is 1 in (26x25xx1), or 1 in 400 million billion billion, or effectively zero. Checking all possible substitutions would take longer than the age of the universe.

However, there is a shortcut, which enables a codebreaker to crack the substitution cipher within a matter of minutes. Historians of science have long been trying to track down the inventor of the shortcut, and over the last decade Professor Mohammed Mrayati has at last made a breakthrough. Myrayati, an engineer and historian based with the UN in Lebanon, while sifting through the Sulaimaniyyah Ottoman Archive in Istanbul uncovered a hitherto unknown document entitled A Manuscript on Deciphering Cryptographic Messages, first published in around 850 AD. The author was Abu Yusuf al-Kindi, otherwise known as the philospher of the Arabs.

Al-Kindi was director of the House of Wisdom, a research institute and library, based in Baghdad. The House of Wisdom was also a centre of translation, and texts were brought from all over the ancient world in order to gain more knowledge. In some cases, the texts were encrypted, so al-Kindis motivation for codebreaking may have been his craving to access these encrypted secrets.

Al-Kindis breakthrough, known as frequency analysis, may seem obvious to modern eyes, but at the time it was a radical breakthrough that destroyed the security of the existing encryption system. He realised that letters of the alphabet appear with varying frequencies in written text, e.g., on average E accounts for 12.7 per cent of letters in an English text, whereas J, Q, X and Z combined add up to less than 1%. If encryption involves substituting each letter for a different one, then the new letters will take on the frequencies of the letters that they actually represent. Hence, al-Kindi advised codebreakers to count the frequencies of letters in an encrytped text, and then identify their true meaning according to the frequencies, e.g. the most common letter probably represents E.

Al-Kindis invention was based on new mathematical techniques that were being developed by the Arabs and on a deeper understanding of the structure of language and of writing which was driven by a desire to gain a deeper insight into the Koran. Indeed, when Mrayati read al-Kindis manuscript it became clear that it contained the earliest known discussion of statistics. We were the first film crew to have access to the manuscript and we all wondered how many other Arab discoveries were hidden in the Istanbul archives, where the cataloguing of thousands of ancient documents is an ongoing project.

Frequency analysis was eventually exported to or reinvented in Europe, where court code breakers used it to decipher the messages of their enemies. The Babington Plot was intended to assassinate Elizabeth I and put Mary Queen of Scots on the English throne, but the English codebreaker Thomas Phelippes used frequencies to crack the plotters cipher and read their correspondence.

(a) Explain why the chances of correctly guessing all 26 letters in a message is 1 in 400 million billion billion.

(b) Explain in your own words how to use frequency analysis to break a code.