Al-Kindi, the father of cryptanalysis

Abu Yūsuf Yaʻqūb ibn ʼIsḥāq aṣ-Ṣabbāḥ al-Kindi was born in 801 in Kufa or Basra, Iraq, and died in Baghdad in 873. He is known as “the philosopher of the Arabs” but he was also a scholar, a mathematician, a doctor, a musician and a cryptologist.

Who was Al-Kindi

Having lived under the Abbasid Caliphate, he soon moved to Baghdad where he soon acquired great fame and the protection of various caliphs, starting with al-Ma’mun, and up to al-Mutawakkil, with whom he fell in disgrace.

Al-Kindi, as a philosopher, tried to reconcile Greek philosophical thought with Islamic orthodoxy; he dealt with astronomy, physics and in particular optics. As a mathematician he dealt with Indian numbers and Archimedes’ works on the measurement of the circle.

He was the first Arab Peripatetic philosopher and is still commonly regarded as the father of Arab philosophy due to its synthesis, adaptation and promotion of classical and Hellenistic Greek philosophy in the Muslim world.

Al-Kindi’s contribution to cryptography

In cryptography, Al-Kindi is remembered for being the first to study the statistics of the frequency of letters in a text.

Al-Kindi noted that the relative frequency of a letter in a given language tends to stabilize at a value, and he realized that frequency analysis is a sufficient tool to decrypt cipher texts by substitution.

He wrote a book, “On Decrypting Encrypted Correspondence”, where he proposed the following method for decrypting a cipher text: write the cipher text next to a plain text in the supposed line of the cipher and of the same length; the frequencies of the letters of the clear text and of the cipher text are counted; call the most frequent letter of the clear text first, the following one second, and so on. The same applies to the ciphertext. Comparing the two lists and with some exchanges will soon arrive at a plausible text.

This is enough to make Al-Kindi the father of cryptanalysis. But also the father of statistics, if it is true that this was the first practical application of statistical methods, 800 years before Pascal and Fermat.

Al-Kindi, in this work, also provides a classification of the figures then known, by transposition and substitution. He also hints at the possibility of combining multiple digits, thus a form of over-encryption, but without giving details or examples.

Al-Kindi and cryptology

Let us consider, as an example, the Hebrew mono-alphabetic (that is, one that has only one cipher alphabet) Hebrew known as Atbash (for more information, check the related article).

In it we have a clear alphabet (in green in the table) and a cipher alphabet (in red in the table).

To encrypt the message «classic cryptography», we take the clear message one letter at a time, from the first to the last and look for it in the clear (green) alphabet.

Once we have found it, we go down to the bottom row of the table and take the letter from the corresponding box. The succession of these letters constitutes the encrypted message or cipher.

In this example the first letter of the message, c, is encrypted with X, the second letter, r, is encrypted with i and so on until the end of the clear message, whose figure is: XIRGGLTIZURZ XOZHHRXZ.

The recipient of the encrypted message, proceeding symmetrically to the encryption, is able to obtain the clear message.

The letters of the encrypted message are searched in the cipher alphabet, one at a time. Find them by going back to the letter in the immediately upper box of the clear alphabet. The succession of plain letters thus obtained constitutes the understandable message. This procedure is called decryption.

But if a third person, different from the sender and the recipient, were in possession of the encrypted message and did not know the cipher alphabet, he could still “read it in clear text?”. The answer is yes! Thanks to the contribution of Al-Kindi».

The method of frequency analysis

Assuming that the language in which the message was written is English and that the frequency distribution of the letters of the message is similar to that of the English language, then we take a vocabulary of the English language and choose all the words with the exception of their definition in order to calculate these frequencies.

So we count all the a’s in these words of the dictionary, then all the b’s, then all the other letters to follow. Then we divide all these values by the total number of letters, multiplied by one hundred, and we get the percentage frequency of each letter.

The e is the most frequent letter: its frequency corresponds to about 10% of the total, the a to 8%, the i to 9% and so on.

Note: The accented letters or with other diacritical marks must be replaced with the letters of the basic alphabet: that is, the letter is = e, ê = e, ç = c, etc.

Now let’s move on to the cipher: in it we calculate the percentage frequency of each letter. Then we compare the frequencies of the encrypted message and of the English language: at a given frequency of a letter of the encrypted message, an analogous or similar frequency of another letter of the English language could correspond, we can then put a correspondence relationship between the two letters, i.e. one letter is the digit of the other.

Example: if the letter of the encrypted message K has a frequency in the encryption equal to about 10%, probably the K of the encrypted message corresponds to the e of the clear message, it too has a frequency of about 10%. Thus, with a few attempts, the encrypted message can be resolved.

The frequency analysis method was Al-Kindi’s contribution to cryptology: this technique constituted the primum movens of cryptanalysis, a branch of cryptology.

A practical example of cryptanalysis

And we see cryptanalysis in action… The Queen of Scotland Mary Stuart, a Catholic, plots with the Catholic Lord Babington against her cousin Elizabeth I, a Protestant, who is holding her prisoner in the Tower of London but has no intention of suppressing her.

Between Mary Stuart and Lord Babington there is an intense exchange of messages which are intercepted by Elizabeth’s counter-intelligence. A man from Elizabeth’s secret service, Felipes, who is aware of Al-Kindi’s cryptanalysis, resolves all the messages encrypted with the mono-alphabetical cipher of the conspirators.

These messages indisputably demonstrate Mary’s participation in the conspiracy to assassinate Queen Elizabeth and for this she is tried and sentenced to death by beheading which will take place on February 8, 1587.

From this historical episode it is clear that mono-alphabet encryption is not secure at all. The response of cryptographers to frequency analysis was the use of polyalphabetic encryption, which provoked a similar cryptoanalytic counter-response. A war of techniques that will extend to the present day.