by DAVID KAHN
But, important as all these were, the view that cryptology is black magic in itself springs ultimately from a superficial resemblance between cryptology and divination. Extracting an intelligible message from ciphertext seemed to be exactly the same thing as obtaining knowledge by examining the flight of birds, the location of stars and planets, the length and intersections of lines in the hand, the entrails of sheep, the position of dregs in a teacup. In all of these, the wizardlike operator draws sense from grotesque, unfamiliar, and apparently meaningless signs. He makes known the unknown. Of course the analogy errs. Augury, astrology, palmistry, haruspication, and the other divinatory techniques are all ultimately subjective and invalid, while cryptology is objective and perfectly valid. Nevertheless, the appearance often overwhelmed this reality. The simpleminded saw magic even in ordinary deciphering. Others, more sophisticated, saw it in cryptanalysis, whose drawing the veil from something concealed and buried seemed to them both mysterious and miraculous. They equated cryptology and magic.
All this stained cryptology so deeply with the dark hues of esoterism that some of them still persist, noticeably coloring the public image of cryptology. People still think cryptanalysis mysterious. Book dealers still list cryptology under “occult.” And in 1940 the United States conferred upon its Japanese diplomatic cryptanalyses the codename MAGIC.
In none of the secret writing thus far explored has there been any sustained cryptanalysis. Occasional isolated instances occurred, as that of the four Irishmen, or Daniel, or any Egyptians who may have puzzled out some of the hieroglyphic tomb inscriptions. But of any science of cryptanalysis, there was nothing. Only cryptography existed. And therefore cryptology, which involves both cryptography and cryptanalysis, had not yet come into being so far as all these cultures—including the Western—were concerned.
Cryptology was born among the Arabs. They were the first to discover and write down the methods of cryptanalysis. The people that exploded out of Arabia in the 600s and flamed over vast areas of the known world swiftly engendered one of the highest civilizations that history had yet seen. Science flowered. Arab medicine and mathematics became the best in the world—from the latter, in fact, comes the word “cipher.” Practical arts flourished. Administrative techniques developed. The exuberant creative energies of such a culture, excluded by its religion from painting or sculpture, and inspired by it to an explication of the Holy Koran, poured into literary pursuits. Storytelling, exemplified by Scheherazade’s Thousand and One Nights, word-riddles, rebuses, puns, anagrams, and similar games abounded; grammar became a major study. And included was secret writing.
Their interest appeared early. In the Arabic year 241, which is 855,* the scholar Abū Bakr Ahmad ben ‘Alī ben Wahshiyya an-Nabatī included several traditional cipher alphabets used for magic in his book Kitāb shauq al-mustahām fī ma‘rifat rumūz al-aqlām (“Book of the Frenzied Devotee’s Desire to Learn About the Riddles of Ancient Scripts”). One alphabet, called “dâwoûdî,” meaning “Davidian,” from the name of the king of Israel, was developed from Hebrew letters by changes in cursive form, by adding tails to letters, or by dropping parts of them. The copyist in 1076 of a treatise on magic operations enciphered such words as “opium” in dâwoûdî. It was considered the magic alphabet par excellence, and was sometimes called “rihani,” a form of a word meaning “magic.” Another classic substitution alphabet survived as late as 1775, when it was used in a spy letter to the regent of Algiers. This script was known in Turkey as “Misirli” (“Egyptian”), in Egypt as “Shāmī” (“Syrian”), and in Syria as “Tadmurī” (“Palmyrene”). In a manuscript on the art of war, probably of 14th-century Egyptian origin, cipher concealed the crucial ingredients of compounds to be hurled into besieged strongholds. Extremist sects in Islam cultivated cryptography to conceal their writings from the orthodox.
In rare cases, the Moslem states used ciphers—not codes, which they seem not to have known—for political purposes, perhaps deriving this practice from the Persian empire, upon which they modeled much of their administration. A few documents with ciphertext survive from the Ghaznavid government of conquered Persia, and one chronicler reports that high officials were supplied with a personal cipher before setting out for new posts. But the general lack of continuity of Islamic states and the consequent failure to develop a permanent civil service and to set up permanent embassies in other countries militated against cryptography’s more widespread use. Arabic writers occasionally allude to it. A genealogical tract said of an eighth-century secretary, Mullūl ben Ibrahim ben Yahzā as-Sanhā ğī, that “he was eloquent and quickly understood divers languages; he wrote in Syriac [perhaps meaning the classical Shāmī cipher alphabet] and in secret characters etc., and he excelled in this.” The monumental survey of history written in Egypt in the 14th century by ‘Abd al-Rahmān Ibn Khaldūn, The Muqaddimah, which Arnold Toynbee has called “undoubtedly the greatest work of its kind that has ever yet been created by any mind in any time or place,” noted that officials of the governmental tax and army bureaus “use a very special code among themselves, which is like a puzzle. It makes use of the names of perfumes, fruits, birds, or flowers to indicate the letters, or it makes use of forms different from the accepted forms of the letters. Such a code is agreed upon by the correspondents between themselves, in order to be able to convey their thoughts in writing.” The names of the birds recalls the Persian system that also used them, and points to a Persian origin for at least this cipher, and by implication for others.
The Arabic “Davidian” substitution cipher
The special cryptography of the tax officials, called “qirmeh,” simplified the forms of the Arabic letters, reduced the size of their bodies and elongated their tails, dropped diacritic points, ran words together and sometimes superimposed or intermingled them, and abbreviated many words. It first appeared in Egypt in the 16th century, and most of the financial records in Istanbul, Syria, and Egypt until the latter part of the 19th century were written in qirmeh. It was used only in documents pertaining to tax affairs, in order to keep revenue information secret.
The Arabic knowledge of cryptography was fully set forth in the section on cryptology in the Subh al-a ‘sha, an enormous, 14-volume encyclopedia written to afford the secretary class a systematic survey of all the important branches of knowledge. It was completed in 1412 and succeeded in its task. Its author, who lived in Egypt, was Shihāb al-Dīn abu ‘l-’Abbās Ahmad ben ‘Ali ben Ahmad ‘Abd Allāh al-Qalqashandi. The cryptologic section, “Concerning the concealment of secret messages within letters,” has two parts, one dealing with symbolic actions and allusions, the other with invisible inks and cryptology. The section falls under a larger heading, “On the technical procedures used in correspondence by the secretaries in eastern and western lands and in the Egyptian territories, ranging over the whole period from the appearance of Islam up to our own time,” which, in turn, is within a unit headed “On the forms of correspondence.”
Qalqashandi attributed most of his information on cryptology to the writings of Tāj ad-Dīn ‘Alī ibn ad-Duraihim ben Muhammad ath-Tha’ālibī al-Mausilī, who lived from 1312 to 1361 and held various teaching and official posts under the Mamelukes in Syria and Egypt. Except for a theological treatise, none of his writings is extant, but he is reported to have authored two works on cryptology. One was a poem, “Urjūza fi ‘l-mutarjam,” in a loose meter often used for didactic poems and perhaps chosen for mnemonic purposes. The other work consisted of a prose commentary on the poem “Miftāh al-kunūz fi īdah al-marmūz.” Though this must be included among the Lost Books of cryptology, most of its information was probably preserved in Qalqashandi.
Qalqashandi began by explaining that necessity sometimes compels concealment “because an enemy places some obstacle or similar thing between the sender and the addressee, e.g., between two rulers or two other persons. [It is used] when circumventory actions are of no avail, either because of interceptory ambushes or because of tho
rough probes into all letters coming from either of the two parties corresponding”—the latter remark a significant revelation of the need for cryptography and of the probable practice of cryptanalysis.
After explaining that one may write in an unknown language to obtain secrecy, Ibn ad-Duraihim, according to Qalqashandi, gave seven systems of cipher: (1) One letter may replace another. (2) The cryptographer may write a word backward. Muhammad (in the consonantal Arabic alphabet) would become DMHM. (3) He may reverse alternate letters of the words of a message. (4) He may give the letters their numerical value in the system in which the Arabic letters are used as numbers, and then write this value in Arabic numerals. Muhammad becomes 40+8+40+4, and the cryptogram looks like a list of figures. (5) The cryptographer may replace each plaintext letter with two Arabic letters, whose numerical value adds up to the numerical value of the plaintext letter. After giving some examples, Qalqashandi states that “other letters can be used, so long as they add up to the number of the original letter.” (6) “He may substitute for each letter the name of a man or something like that.” (7) The cryptographer may employ the lunar mansions as substitutes for the letters, or list the names of countries, fruits, trees, etc., in a certain order, or draw birds or other living creatures, or simply invent special symbols as ciphertext replacements. The similarity of this list to Ibn Khaldūn’s suggests that both writers took their information from a 10th-century manual for secretaries by Abū Bakr Muhammad ben Yahyā as-Sūlī, who gave both the bird and lunar substitutions, reporting that they are Persian in origin.
This list encompassed, for the first time in cryptography, both transposition and substitution systems, and, moreover, gave, in system 5, the first cipher ever to provide more than one substitute for a plaintext letter. Remarkable and important as this is, however, it is overshadowed by what follows—the first exposition on cryptanalysis in history.
It appeared in full maturity in Qalqashandi’s paraphrase of Ibn ad-Duraihim, but its beginnings are probably to be found in the intense and minute scrutiny of the Koran by whole schools of grammarians in Basra, Kufa, and Baghdad to elucidate its meanings. Among other studies, they counted the frequency of words to attempt a chronology for the chapters of the Koran, certain words being considered as having been used only in the later chapters. They examined words phonetically to see whether they were native Arabic or foreign loanwords. This led to generalizations about the composition of Arabic words. For example, one grammarian, referring to the lingual letters ra’, lām, and nūn, and the labials fā’, bā’ and mīm, declared: “Now when the six (labial and lingual) letters were pronounced and emitted by the tongue, they proved easy to form, and became common in speech-patterns. So no true quinquiliteral roots are free from them, or at least from one of them.” This very rule reappeared in Ibn ad-Duraihim’s work. Also of great importance in the discovery of linguistic phenomena that led to cryptanalysis was the development of lexicography. In making a dictionary, considerations of letter-frequency and of which letters go or do not go together virtually thrust themselves upon the lexicographer. For example, the Arabs recognized early that zā’ was the rarest letter in Arabic and, contrariwise, that the omnipresence of the definite article “al-” made alif and lām the most common letters in normal style.
It is therefore quite understandable that the Arab world’s first great philologist, the first man to conceive the idea of a comprehensive dictionary, a shining light of the Basra school of grammarians, wrote a “Kitāb al-mu‘ammā” (“Book of Secret Language”) relatively early in history. This was Abū ‘Abd al-Rahmān al-Khalīl ibn Ahmad ibn ‘Amr ibn Tammām al Farāhīdī al-Zadī al Yahmadī, who lived from the Arabic year 100 to between 170 and 175 (or A.D. 718/719 to between 786 and 791). Al-Khalīl was inspired to write the “Kitāb al-mu‘ammā”—which apparently is yet another Lost Book—by his solution of a cryptogram in Greek sent him by the Byzantine emperor. When he was asked how he managed to solve it, he said, “I said (to myself), the letter must begin ‘In the name of God’ or something of that sort. So I worked out its first letters on that basis, and it came right for me”
This description, and the fact that it took him a month before he could solve it, suggests that the Arabs had not yet formulated the more analytical techniques of cryptanalysis based upon letter-frequency. This makes sense—150 years or so after the Hegira they would probably still be in the early stages of their linguistic explorations. But by the time of Ibn ad-Duraihim, 600 years later, these studies would have ramified enough to stimulate some unknown genius to apply their findings to the solution of ciphers. Indeed, Ibn ad-Duraihim’s discussion of cryptanalysis, as reflected in Qalqashandi, is so mature that it implies a fairly long preceding period of development. The technique was at least moderately well known, for Ibn Khaldūn wrote in The Muqaddimah: “Occasionally, skillful secretaries, though not the first to invent a code [and with no previous knowledge of it], nonetheless find rules [for solving it] through combinations which they evolve for the purpose with the help of their intelligence, and which they call ‘solving the puzzle [cryptanalysis].’ Well-known writings on the subject are in the possession of the people. God is knowing and wise”
The Ibn ad-Duraihim-Qalqashandi exposition begins at the beginning: the cryptānalyst must know the language in which the cryptogram is written. Because Arabic, “the noblest and most exalted of all languages,” is “the one most frequently resorted to” (in that part of the world), there follows an extensive discussion of its linguistic characteristics. Lists are given of letters that are never found together in one word, of letters that rarely come together in a word, of combinations of letters that are not possible (“Thus tha’ may not precede shin.”), and so on. Finally, the exposition gives a list of letters in order of “frequency of usage in Arabic in the light of what a perusal of the Noble Koran reveals.” The writers even note that “In non-Koranic writings, the frequency may be different from this.” With these basics completed, Qalqashandi goes on:
Ibn ad-Duraihim has said: When you want to solve a message which you have received in code, begin first of all by counting the letters, and then count how many times each symbol is repeated and set down the totals individually. If the person devising the code has been very thorough and has concealed the word-divisions in the body of the messages, then the first thing to be worked out is the symbol which divides up the words. To do this, you take a letter and work on the assumption that the next letter is the word-divider. Then you go all through the message with it, having regard for the possible combinations of letters of which the words may be composed, as has been previously explained. If it fits, [then all right]; if not, you take the next letter after the second one. If that fits, [then all right]; if not, you take the next letter after that, and so on, until you are able to ascertain the division of the words. Next, look which letters occur most frequently in the message, and compare this with the pattern of letter-frequency previously mentioned. When you see that one letter occurs in the message more often than the rest, then assume that it is alif; then assume that the next most frequent is lām. The accuracy of your conjecture should be confirmed by the fact that in a majority of contexts, lam follows alif…. Then the first words which you try to work out in the message are the two-lettered ones, through estimating the most feasible combinations of their letters, until you are sure you have discovered something correct in them; then look at their symbols and write down the equivalents by them [whenever they occur in the message]. Apply the same principle to the message’s three-lettered words until you are sure you have got something, then write out the equivalents [all through the message]. Apply the same principle to the four- and five-lettered words, according to the previous procedure. Whenever there is any doubt, posit two or three or more conjectures and write each one down until it becomes certain from another word.
Qalqashandi follows this clear explanation with a four-page example of solution taken from Ibn ad-Duraihim. The cryptogram consists of two lines of
verse enciphered with symbols of apparently arbitrary invention. At the end, he notes that eight letters were not used and that they are exactly the same eight that stand at the foot of the frequency list. “This, however, is pure chance: a letter may be somewhat misplaced from the position it has been assigned in the above-mentioned list,” he observes—an observation that argues a fair amount of experience in cryptanalysis. To nail everything down, Qalqashandi gives a second example from Ibn ad-Duraihim, with a rather longer message. With this three-page illustration, he concludes the cryptologic section of his work.
To what extent the Arabs used the abilities so brilliantly evident here in the solution of military or diplomatic cryptograms, and what effects they had upon Moslem history, is not known. What does seem certain is that, like the Arabic civilization itself, this knowledge fell into desuetude and was soon lost. An episode of 250 years later dramatizes the decline.
In 1600, the Sultan of Morocco, Ahmad al-Mansūr, sent an embassy headed by his confidential secretary, ‘Abd al-Wahid ibn Mas’ud ibn Muhammad Anūn, to Queen Elizabeth of England to ally himself with her against Spain. The ambassador reported back in a monalphabetically enciphered dispatch, which shortly thereafter apparently somehow fell into the hands of an Arab, evidently intelligent, but as evidently ignorant of his great cryptologic heritage. In a memorandum, he wrote:
Praise be to Allah! Writing of the secretary ‘Abd al-Wahid ibn Mas ‘ud Anūn. I found a note written in his hand in which he had noted in secret characters some information destined for our protector Abū I’ Abbas al-Mansūr. This information relates to the Sultana of the Christians (May God destroy them!) who was in the country of London in the year 1009. From the moment when the note fell into my hands, I never stopped studying from time to time the signs which it bore…. About 15 years more or less passed, until the moment when God (Glory to Him!) did me the favor of permitting me to comprehend these signs, although no one taught them to me….