Laying the foundation for modern encryption methods: Al-Kindi and frequency analysis

Abu Yusuf Yaqub ibn Ishaq as-Sabbah al-Kindi was a man of many disciplines, born in Kufa, Iraq around 801 AD. He was raised in Basra and educated in Baghdad. 

Multidisciplinary work

There his scholarship brought him to the attention of the Abbasid Caliph Al-Mamun, who appointed him to the Bayt al-Hikma (House of Wisdom) in Baghdad. Here, he with a team of scholars, translated the works of Greek philosophers and scientists into Arabic.

Al-Kindi composed at least 260 works on a variety of subjects. He wrote on philosophy, optics, medicine, mathematics, chemistry, music, astronomy, and cryptography. He introduced Greek philosophy to the Islamic world and championed the idea of seeking truth from far flung nations and peoples. Along with Al-Khwarizmi he popularized the use of Indian numerals in the Muslim world. 

Al-Kindi also authored a book titled Risala fi Istikhraj al-Kutub al-Muammah which is the earliest surviving book on cryptanalysis. In order to appreciate his creativity in this field, we need to travel back to the time of Julius Caesar. 

The Caesar shift cipher

In 54 BC, the Gaulish leader Ambiorix revolted against the Romans and surrounded the Roman legion commanded by Quintus Cicero. In desperation, Cicero appealed to Julius Caesar for help. Caesar with his legions marched to relieve Cicero. 

He also sent a message to let Cicero know that help was on the way. Greek letters were used in place of Latin ones to encrypt the message, making it unreadable in the event of the Gauls intercepting it. Upon receiving the message, Cicero read it to his soldiers, who were overjoyed to hear that help was on its way, encouraging them to hold out until Caesar rescued them.

This is one of the earliest recorded uses of a coded message in the battlefield. We do not know the exact nature of the code that Caesar used. However the historian Suetonius informs us of another code used by Caesar. This is now known as the Caesar shift cipher. It consists of replacing each letter by the letter three places down from it in the alphabet. Using lower case for plain text (PT) and upper case for coded text (CT) the Caesar shift-3 cipher is given by the following table.

Table 1: Shift-3 Cipher

The passage: “Suddenly I have come to know myself, All the false barriers have crumbled today!” (Kazi Nazrul Islam, tr Kabir Chowdhury) would be encoded as: 

VXGGHQOB L KDYH FRPH WR NQRZ PBVHOI DOO WKH IDOVH EDUULHUV KDYH FUXPEOHG WRGDB

To decode, we reverse this process, and replace every letter, by the letter three places behind it in the alphabet. Obviously this scheme can also be applied with a shift of any number between 1 and 26. For example, if we receive a message:

UFCPC RFC KGLB GQ UGRFMSR DCYP YLB RFC FCYB GQ FCJB FGEF UFCPC ILMUJCBEC GQ DPCC

And we try to decode it by going back three letters, we get: 

rczmz ocz hdiy dn rdocjpo azvm viy ocz czvy dn czgy cdbc rczmz fijrgzybz dn amzz

Obviously this did not work! But if we know that it is a shift right cipher, then we can try every shift from 1 to 26. When we use the shift-24 table to decode the message there is a 24 letter difference between the CT and PT and the message is:

“Where the mind is without fear and the head is held high. Where knowledge is free” (Rabindranath Tagore, tr Tagore)

Consequently we can solve any shift cipher by brute force. But, suppose we use a substitution method, where we change the order in which the letters appear in the alphabet. For example:

Table 2: Order of alphabet changed

Now there are over 400 septillion ciphers available. (400 septillion = 400 million billion billion = four followed by 26 zeroes!). Even if we had a computer that could check one billion ciphers per second it would take over 12 billion years to go through all such ciphers. Therefore the brute force method is useless in this situation.

He introduced Greek philosophy to the Islamic world and championed the idea of seeking truth from far flung nations and peoples

Al-Kindi’s method of decoding

Building on the work of scholars such as Al-Khalil, Al-Kindi introduced frequency analysis to crack the substitution cipher. Scholars of the Quran had been trying to establish the chronology of the suras. They counted the frequency of words in different suras. Suras which contained newer words were deemed to have been revealed later in time. In addition, they also looked at the frequency of letters and observed that some letters occurred much more frequently than others. This seemingly simple observation led to the first major breakthrough in cryptanalysis! (See The Code Book by Simon Singh).

Al-Kindi’s frequency analysis method for decoding is as follows. First, take a long excerpt of plain text, count the occurrence of each letter, and make a frequency table. Secondly, count the occurrence of the letters in the coded text and form another frequency table. Finally, replace the most frequently occurring letter in the coded text, by the most frequently occurring letter in the plain text and so on. If the coded text is not long enough, then the distribution of letters can differ from the plain text excerpt we examined. In that case, we look for combinations of letters to give us further clues.

In English, the most common letter is “e” followed by “t.” The 12 most frequent letters are usually given as: e; t; a; o; i; n; s; h; r; d; l; u.

However the occurrence of the letters t, a, o, i, and n will roughly be the same. Therefore, we have to be prepared to experiment with different combinations of assignments of cipher text to plain text to successfully decode the message.

Example decoding process 

Suppose that we are asked to decode the message: 

HTKGPAU TQOCPU EQNPVTXOGP MGPA OG XQNT GCTU K EQOG VQ DNTX ECGUCT PQV VQ RTCKUG JKO VJG GSKM VJCV OGP AQ MKSGU CHVGT VJGO VJG IQQA KU QHV KPVGTTGA ZKVJ VJGKT DQPGU UQ MGV KV DG ZKVJ ECGUCT 

Using the website www.dcode.fr/frequency-analysis we get the frequency table:

So, let us start with the following decoding table:

Using this we get: 

HaiesAn aoOCsn EoNstaXOes MesA Oe XoNa eCan i EoOe to DNaX ECenCa sot to RaCine JiO tJe eSiM tJCt Oes Ao MiSen CHtea tJeO tJe IooA in oHt isteaaeA ZitJ tJeia Dosen no Met it De ZitJ ECenCa

The word “tJe” must be “the,” which tells us that “J = h.” Now we extend the table and message:

HaiesAn aoOCsn EoNstaXOes MesA Oe XoNa eCan i EoOe to DNaX ECenCa sot to RaCine hiO the eSiM thCt Oes Ao MiSen CHtea theO the IooA in oHt isteaaeA Zith theia Dosen no Met it De Zith ECenCa 

The word “thCt” can be assumed as “that” and therefore “C = a.” The words Oe, hiO, and, theO tell us that “O = m” or “O = n.” Let’s only see the analysis for “O = m.”

Cryptex - Collected

Carrying on:

HTiesAn Tomasn EoNstTXmes MesA me XoNT eaTn i Eome to DNTX EaenaT sot to RTaine him the eSiM that mes Ao MiSen aHteT them the IooA in oHt isteTTeA Zith theiT Dosen no Met it De Zith EaenaT 

We deduce that “theiT = their” giving us “T = r.” And so we keep extending the decoding table as before and now we have:

HriesAn romasn EoNstrXmes MesA me XoNr earn i Eome to DNrX Eaenar sot to Rraine him the eSiM that mes Ao MiSen aHter them the IooA in oHt isterreA Zith their Dosen no Met it De Zith Eaenar 

The word “romasn” must be “Romans.” Therefore we switch the codes letters for n and s.

HrienAs romans EoNntrXmen MenA me XoNr ears i Eome to DNrX Eaesar not to Rraise him the eSiM that men Ao MiSes aHter them the IooA is oHt interreA Zith their Dones so Met it De Zith Eaesar

Assuming “Eaesar = caesar” therefore “E = c.” Also “aHter = after,” therefore ‘H=f’. Now we have:

frienAs romans coNntrXmen MenA me XoNr ears i come to DNrX caesar not to Rraise him the eSiM that men Ao MiSes after them the IooA is oft interreA Zith their Dones so Met it De Zith caesar 

Skipping ahead using our knowledge of Shakespeare’s play Julius Caesar, we see that the coded extract is from Mark Antony’s speech in the play

“Friends, Romans, countrymen, lend me your ears; I come to bury Caesar, not to praise him. The evil that men do lives after them; The good is oft interred with their bones; So let it be with Caesar.”

The full decoding table is: 

Table 9: Example full decoding table

The advent of frequency analysis forced cryptographers to introduce schemes to obscure the frequency of the letters

Al-Kindi’s legacy

Al-Kindi is one of the earliest philosophers in the Muslim world. He died around 873 AD and much of his work was lost over the subsequent centuries. In 1258 AD the Mongol Hulagu Khan attacked Baghdad after being insulted by the ruler Al-Mutasim. Baghdad was sacked, many inhabitants were massacred, the Caliph was executed, and the Abbasid dynasty came to an end. The libraries were destroyed and the books were torn apart. Although the larger libraries did start functioning again within two years of the siege, further sackings of Baghdad by Timur and invasions by the Ottomans led to the long term decline of the city. 

In 1987, Al-Kindi’s book on cryptanalysis was discovered in a library in Istanbul. This book showed that Al-Kindi’s use of statistical methods anticipated the theories of Pascal and Fermat by 800 years! (see The Mathematics of Encryption by Margaret Cozzens, Steven J Miller) 

The advent of frequency analysis forced cryptographers to introduce schemes to obscure the frequency of the letters. They created methods such as using more than one alphabet, using several alternatives to the most common letters or coding two and three letter words using a single symbol.

Over the years encryption techniques have become more and more complex. We have seen ciphers such as polyalphabetic substitution, Vigenere, Enigma, and public key encryption. These ciphers require much more sophisticated methods than frequency analysis to decipher them. And now we are entering the phase of quantum cryptography which promises even higher levels of security than public key cryptography. 

However, this does not imply that frequency analysis is no longer used. Google's Ngram viewer employs frequency analysis to display the occurrence of terms and phrases used in different years from the texts that the Ngram viewer indexes.

In 2023, the launch of ChatGPT by OpenAI, led to the widespread use of large language models (LLM) by the general public. One of the building blocks of large language models is frequency analysis. Suppose we are given the phrase “I am going to the ____”, and we want to know what words are likely to complete this sentence. There are many possibilities, such as office, store, dry cleaners, park, movies, studio, and so on. Using frequency analysis of web texts, we can write a program that furnishes the most likely ending for this sentence. This allows us to generate sentences that are grammatically correct, make sense, but are not necessarily true! Therefore, Al-Kindi’s frequency analysis methods are still being used -- even in the 21st century. 

Dr Riaz Khan is a mathematician and development professional.