Al-Kindi and frequency analysis: how a substitution is broken

Every simple substitution cipher, from Caesar's to Atbash, shares a hidden weakness: the letters change their appearance but keep their frequency. The first systematic description of this principle is owed to a ninth-century Arab philosopher, Abu Yusuf Yaqub ibn Ishaq al-Kindi, active in Baghdad, who explained in a short treatise how to read a ciphered message without knowing its key.

The philosopher of the Arabs

Al-Kindi was born around 801, probably in Kufa, and lived in Baghdad in the time of the Abbasid caliphs al-Mamun and al-Mutasim, when the city was the centre of a vast movement translating Greek works into Arabic. Tradition remembers him as “the philosopher of the Arabs”, because he was among the first to engage with Aristotle and the Neoplatonists in Arabic. He wrote on mathematics, astronomy, medicine, music and optics.

His output, according to the old bibliographies, numbered hundreds of titles, most of them lost. The setting in which he worked, made up of philologists busy comparing manuscripts, studying the language of the Quran and counting letters and words, fostered precisely that quantitative attention to writing from which cryptanalysis was born.

The treatise on decipherment

Al-Kindi's work on this subject, known as Risala fi istikhraj al-muamma, that is a treatise on deciphering ciphered messages, was rediscovered in the twentieth century in a manuscript kept in Istanbul. It describes several types of cipher and, above all, the method for attacking them: take a sufficiently long plain text in the same language, count how often each letter appears and compare the proportions with those of the signs in the ciphered message.

The most frequent letter of the ciphertext will probably correspond to the most frequent letter of the language, the second to the second, and so on. Al-Kindi notes that short texts lend themselves less to this calculation and that combinations of letters and recurring words must also be considered. The method does not give mechanical results, but it offers a starting point for reconstructing the whole alphabet.

An Arabic tradition of cryptology

After al-Kindi other authors writing in Arabic developed this research. In the fourteenth century Ibn ad-Durayhim wrote about ciphers and their solution, and in the fifteenth century the Egyptian encyclopaedist al-Qalqashandi included in his great manual for chancery secretaries, the Subh al-asha, a section on ciphered writing, with examples of substitutions and transpositions. Cryptology was regarded as part of the culture of a good official.

In Europe frequency analysis appears explicitly only in the Renaissance, with Leon Battista Alberti and the cipher clerks of the Italian chanceries. We do not know whether there was direct transmission from the Arab world; the method may have been rediscovered independently. The fact remains that the idea had already been clearly formulated in Baghdad some six centuries earlier.

Al-Kindi's discovery marks the beginning of a contest that runs through the whole history of ciphers. From then on every new system, from Alberti's disk to Bellaso's table and on to rotor machines, can be read as an attempt to escape the counting of letters, and every great decipherment as proof that the escape is never complete.