One of the first cryptologists was an Arab – did you know?

In recently was in Poznań, Poland, I learned that one of the greatest Arab scholars, al-Kindi (الْكِنْدِي), was one of the pioneers of cryptology. How did he manage to decrypt messages?

The museum in Poznan

Recently I had visited the monument of Marian Rejewski, Henryk Zygalski and Jerzy Różycki.

They were Polish mathematicians and cryptologists who cracked the secret code of the Nazi cipher machine Enigma which is considered as one of the most sophisticated cipher machines in history. 

Based on the Polish knowledge, the British scientist Alan Turing managed to build a huge computer that would finally crack the cipher.

I personally found it very interesting that in the small Polish exhibition, a genius of the 9^th century was also mentioned: al-Kindī>/mark> (الْكِنْدِي).

His full name was Abū Yūsuf Ya‘qūb bin Ishāq (أَبُو يَعْقُوب بن إِسْحاق الْكِنْدِي), known as the philosopher of the Arabs: failasūf al-‘Arab (فَيْلَسُوف الْعَرَب).

What do we know about al-Kindi?

a-Kindi was of South Arabian descent, which his name already indicates: Kinda (كِنْدة) was the name of an ancient tribal kingdom in the Najd (present-day Saudi-Arabia).

Al-Kindī was born probably at the beginning of the ninth century (ca. 800/~185 AH) in Kūfa, where his father was  a governor.

He was educated in Basra and Baghdad, then the great centers of learning.

Why did the exhibition mention al-Kindi?

Answer: Because he set a milestone in the field of cryptology: the frequency analysis.

For almost a thousand years, from 500 to 1400, the knowledge of cryptology of Western civilization did not really progress. People used very basic systems which were mainly based on steganography.

Steganography, in simple words, denotes that a secret message is being sent by concealing the contents of the message. For example, in ancient times, people shaved a messenger's head, wrote a message on his head and waited until hair had covered it again, so that he could deliver the secret, hidden message.

Then, in the 9^th century, there was a breakthrough: The Arabs understood the importance of cryptoanalysis. Cryptanalysis is the science of unscrambling a message without the knowledge of the key and is based on finding weaknesses in encryption methods in order to break them.

Why did al-Kindi work on cryptoanalysis?

The Arabs and Persians, back then, were among the best mathematics and linguistics at that time. This was mainly because they tried hard to analyze every detail of the Qur'an. How did they do that? They did it step by step.

1. First, Muslim theologians tried to extract a chronological order of the revelations.
2. They did that by counting the frequency of specific words in every single verse because some words arose earlier in comparison to other words.
3. Then, they analyzed the verses phonetically and at the level of single letters.
4. They realized that some letters occur more often than others
5. They realized that some letters are not found next to each other, and that some like to be accompanied by certain letters.
6. They discovered the rarest letters in Arabic and the most common letters: the letters Aleph (ا) and Lām (ل) are the most common in Arabic, whereas the letter Jīm  (ج) appears only a tenth as frequency.

When they put all that together, they made the first great breakthrough in cryptoanalysis: the frequency analysis.

How can Kindi's ideas be used to encrypt messages?

If you start counting the frequency of letters and arrange them in that order, you suddenly have a cipher-tool to decode messages.

Al-Kindī was probably the first scholar who wrote about that. His book Risāla fī Istikhrāj al-Kutub al-Mu'ammāh (رِسالة في اِسْتِخْراجِ  الْكُتُبِ المُعَمّاَة) contains the oldest known description of cryptanalysis by frequency analysis. The title literally means On Extracting Obscured Correspondence. Nowadays, we could translate it as On Decrypting Encrypted Correspondence.

In his writing, we find many interesting things about statistics, phonetics and Arabic syntax. In two paragraphs, he eventually describes the system of cryptanalysis.

Unfortunately, I have not found the original Arabic text – I can only rely on the translation given in the great book The Code Book: Science of Secrecy from Ancient Egypt to Quantum Cryptography by Simon Singh (page 17):

“One way to solve an encrypted message, if we know its language, is to find a different plaintext of the same language long enough to fill one sheet or so, and then we count the occurrences of each letter. We call the most frequently occurring letter the FIRST, the next most occurring letter the SECOND the following most occurring letter the THIRD, and so on, until we account for all the different letters in the plaintext sample. Then we look at the cipher text we want to solve, and we also classify its symbols. We find the most occurring symbol and change it to the form of the FIRST letter of the plaintext sample, the next most common symbol is changed to the form of the SECOND letter, and the following most common symbol is changed to the form of the THIRD letter, and so on, until we account for all symbols of the cryptogram we want to solve.”

al-Kindi

In short: Al-Kindī was the first to note that encrypted messages could be cracked by using “cribs”. A “crib” is a word or a set of words that is highly suspected to be in the message somewhere. For example, the Arabic definite article al (ال).

What happened to the Polish mathematicians?

Historians say that cracking the Enigma shortened World War II dramatically, at least by two years. So, why have most people outside Poland never heard about the Polish geniuses?

Despite their help, history in many countries has largely ignored their role. The same happened to many Arab, Persian and Berber scientists who never got the fame they would have deserved in my opinion.

The Hollywood movie The Imitation Game which tells the story of how the British mathematician Alan Turing cracked the Enigma barely mentioned the Poles. In 2014, the NSA (National Security Agency) honored Marian Rejewski by inducting him into the NSA Cryptologic Hall of Honour.

• Why is Arabic called a Semitic language?
• Why do superheros and villains have Arabic or Hebrew names?
• Who wrote the first book about Arabic grammar?
• Who wrote the first Arabic dictionary?
• Who invented the Arabic typewriter (keyboard)?

Pictures: (c) Gerald Drißner; wikipedia. Image by PublicDomainPictures from Pixabay