“Kitab al-Muammma” ( Arabic. كتاب المُعَمَّى - “The Secret Language Book” ) is an Arabic book compiled in the 8th century by Khalil ibn Ahmad al-Farahidhi based on his own encryption method.
| Kitab Al Muamma | |
|---|---|
| Kitab Al Muamma | |
| Authors | Khalil ibn Ahmad al-Farahidi |
| Date of writing | 8th century |
| Original language | Arab |
| Content | about cryptographic encryption method |
| Original | not preserved |
Since the VIII century AD e. The development of cryptography occurs mainly in Arab countries - it was the Arabs who were the first to use statistics and probability theory in one form or another. It is believed that the famous VIII-century Arab philologist Khalil ibn Ahmad al-Farahidi was the first to draw attention to the possibility of using standard plaintext phrases to decrypt texts.
Based on the decryption method he discovered, he wrote the book Kitab al-Muamma.
Background
Once Khalil ibn Ahmad needed to decrypt a cryptogram in Greek , which was sent to him by the Byzantine emperor . He explained his decryption method as follows:
 | I told myself that the letter should begin with the words “In the name of Allah” or something like that. So, I based on this the first letters, and everything turned out to be correct. |  |
In other words, his decision was based on known (correctly guessed ) plaintext at the message which began: “ In the name of Allah before everything ... ” In the name of Allah before all things ... ”. ).
This attack method was used in World War II. [ specify ] to crack German communications. [one]
Book Structure
The encryption method invented by al-Farahidhi is the audio part of an already known language (in the original, Arabic ). The dictionary includes some components of the source language. A rule is applied for the selection of words and letters, according to which the above should not obey the rules of phonological research, which al-Farahidi received earlier in his writings. To do this, he used his knowledge of music.
By distinguishing between signs and meanings, he was able to create a sign language alone. This differentiation allowed us to suggest the following: there are regular sounds ( musical ) and irregular sounds (aperiodic), that is, in other words, vowels and consonants. The consonants were then classified according to their point of articulation: from laryngeal sounds to labial sounds, vowels remained in the same group of sounds. In the future, this separation greatly facilitated the encryption process. [2]
Later, Arab cryptographers resorted to the frequency analysis of the text proposed by al-Farahidi to calculate the frequency of words in their works. [3]
Other works based on the proposed method
Unfortunately, “Kitab al-Muamma” has not survived, we know about it from the references in the works of other scientists. The most famous work based on the honey of deciphering Khalil ibn Ahmad is the work of Abu Yusuf Yakub ibn Ishaq ibn Sabba al-Kindi , a famous philosopher, mathematician and astronomer, which is called " Treatise on the decryption of cryptographic messages ."
The method proposed by Khalil ibn Ahmad contains many innovations, including the use of permutations and combinations of different words (in order to list all possible Arabic words without using vowels in them). [four]
But the entire revolutionary and refined cryptanalysis system proposed by al-Kindi fits in two short paragraphs:
“One way to read an encrypted message, if we know the language in which it is written, is to take another unencrypted text in the same language, the size of a page or so, and then count the appearance of each of the letters in it. Let us call the most frequently occurring letter “first,” the letter that comes second in terms of occurrence frequency, call “second,” the letter that comes second in terms of occurrence frequency, call “third,” and so on, until all the different numbers are counted letters in unencrypted text. Then we look at the ciphertext that we want to read, and in the same way we sort its characters. We will find the most common character and replace it with the “first” letter of unencrypted text, replace the second most frequent character with the “second” letter, replace the third most frequent character with the “third” letter, and so on, until all characters of the encrypted message are replaced, which we want to decrypt. ” |
[five]
In addition to the Al-Kindi treatise, there is no less famous work - it is an encyclopedia of 14 volumes, “ Shaub al-Asha ” (“A lamp for the blind in the craft of the clerk”), which was written by the scholar Shihab al-Din Abu-l-Abbas Ahmad ibn Ali al-Kalkashandi in 1412. All subsequent work on cryptanalysis in Arab countries until the 10th century was based on one of these two treatises - A Treatise on the Decryption of Cryptographic Messages or Shaub al-Asha, since the work of Khalil ibn Ahmad was not preserved. The author outlined all the cryptosystems known to him at that time. The work proposed seven encryption systems, which repeated the unpublished ideas of his predecessor, Ibn al-Duraykhim , who first used the frequency analysis of letters. These are the encryption systems:
- replacing one letter with another;
- spelling the word in reverse order;
- spelling some letters of words in the reverse order;
- replacing letters with numbers according to the accepted replacement of Arabic letters with numbers;
- replacing each plaintext letter with two Arabic letters that can be used as numbers and the sum of which is equal to the digital value of the encrypted plaintext letter;
- replacing each letter with the name of a person;
- using a replacement dictionary describing the position of the moon, the names of countries (in a specific order), the names of fruits, trees, etc.
These are just some of the ways to encrypt the source text to complicate breaking it, but already being encrypted. But the encryption system (that is, the key ) had to be specified so that the person to whom the message was intended could quickly decrypt it.
The first time in the history of ciphers in this encyclopedia was a list of permutation systems and replacement systems. But most importantly, for the first time, a description of the cryptanalytic study of ciphertext was presented. Apparently, it was compiled after an intensive and rigorous study of the Koran by Arabic grammars. They were engaged in counting the frequency of occurrence of words, studied the phonetics of words (to establish the morphological origin of a word - Arabic or it was borrowed from another language). When compiling dictionaries, the authors had to take into account the frequency of occurrence of letters, as well as which letters can stand nearby and which can never be found in the neighborhood. Gathering all the accumulated information together and starting from the idea of Khalil ibn Ahmad, Kalkashandi described in his book a way to decrypt the message:
If you want to read the message that you received in encrypted form, then start counting the letters, and then count how many times each character is repeated. If the inventor of the cipher was very careful and hid all the boundaries between the words in the message, then the first task is to find a sign that separates the words. This is done like this: you take a letter and work with it, on the assumption that the next letter is a sign that divides words. So you study the whole message, taking into account the various combinations of letters from which words can be composed. If it turns out, then everything is in order; if not, then you take the next letter in a row, etc., until you can establish a section sign between the words. After you need to find what letters are most often found in the message, and compare them with a sample of the frequency of occurrence of letters. When you see that one letter comes across more often than others in this message, you assume that it is the letter “ Alif ”. Then you assume that the next most frequent occurrence will be the letter “ Lyam ”. The accuracy of your assumption must be confirmed by the fact that in most contexts the letter “Lam” follows the letter “Alif”. The first words that you try to solve in the message should consist of two letters. This is done by evaluating the most likely letter combinations. You write out their equivalents whenever they come across a message. It is necessary to apply exactly the same principle with respect to three-letter words. You write out equivalents from the whole message. The same principle applies to words consisting of four and five letters. Whenever any doubt arises, it is necessary to make two, three assumptions or even more and write down each of them until it is confirmed on the basis of another word. |
[6]
In other words, Kalkashandi begins the presentation by saying that the cryptanalyst must know the language in which the cryptogram is written. The following is a detailed description of his linguistic characteristics (Kalkashandi uses the Arabic language as “the most noble and most beautiful of all languages”). This is followed by a list of letters that can never stand together in one word, and letters that rarely appear in the neighborhood. Also considered are letter combinations that cannot be found in words. The last is a list of letters in the order of "frequency of their use in Arabic in the light of the results of the study of the holy Quran." The author even notes that "in works not related to the Qur'an, the frequency of use may be different." [7]
Kalkashandi gave an example of the disclosure of a cipher: a decrypted cryptogram consists of two poetic lines encrypted using conditional characters. In conclusion, Kalkashandi noted that eight letters were not used and that these are exactly the letters that are at the end of the list, compiled by the frequency of occurrence. He emphasized: "However, this is a mere coincidence: the letter may not be put in the place that it should occupy in the above list." So Kalkashandi gave a clear example of the use of statistical text analysis in message encryption. It is noteworthy that this method is successfully used in decrypting messages encrypted using the single alphabet method (mono-alphabet method) to this day, but it is not cryptographic . [8]
Notes
- ↑ Bengt Beckman, 2002 .
- ↑ R. Rashed, 1994 .
- ↑ R. Rashed, 1996 , p. 378.
- ↑ Lyle D. Broemeling, 2011 , p. 255–257.
- ↑ V.V. Grebennikov, 2012 .
- ↑ I.Yu. Krachkovsky, 1957 .
- ↑ Kahn D., 1967 .
- ↑ New Faces, 2012 .
Literature
- Beckman, Bengt . "Codebreakers: Arne Beurling and the Swedish Crypto Program During World War II . " - "The Mathematical Intelligencer", 2002. - ISBN 0-8218-2889-4 . translated by Kiel-Ov Widman
- Rashed, R. "The Development of Arabic Mathematics: Between Arithmetic and Algebra . " - "The Mathematical Intelligencer", 1994. - ISBN 0-7923-2565-6 . (eng.)
- Rashed, R. “Combinational analysis, numerical analysis, Diophantine analysis and number theory.” Taken from Encyclopedia of the History of Arabic Science, Volume 2: Mathematics and the Physical Sciences . - "The Mathematical Intelligencer", 1996. - ISBN 0-4151-2411-5 . (eng.)
- Broemeling, Lyle D. "An Account of Early Statistical Inference in Arab Cryptology . " - Journal: "The American Statistician", 2011. (English)
- Grebennikov, V.V. "History of cryptology & secret zvyazku" ("History of cryptology & secret communication") . - 2012. (Ukrainian)
- I.Yu. Krachkovsky . Selected Works. T.IV. "Arab Geographical Literature." . - "Oriental literature", 1957. - ISBN 5-02-018380-6 . (Russian)
- David Kahn . "The codebreakers - The Story of Secret Writing . " - New York : Charles Scribner's Sons, 1967 .-- ISBN 0-684-83130-9 . Archived December 16, 2013 on the Wayback Machine
- "New Facets" . "Cryptography and ciphers in life . " - “NEW LIGHT”, journal registration number: PI No. 77-17225, 2012. - P. 42. Archived copy of December 16, 2013 on Wayback Machine (Russian)