Figure 4 To encrypt a plaintext message, the sender passes it through an encryption algorithm. The algorithm is a general system for encryption, and needs to be specified exactly by selecting a key. Applying the key and algorithm together to a plaintext generates the encrypted message, or ciphertext. The ciphertext may be intercepted by an enemy while it is being transmitted to the receiver, but the enemy should not be able to decipher the message. However, the receiver, who knows both the key and the algorithm used by the sender, is able to turn the ciphertext back into the plaintext message.
In addition to keeping the key secret, a secure cipher system must also have a wide range of potential keys. For example, if the sender uses the Caesar shift cipher to encrypt a message, then encryption is relatively weak because there are only 25 potential keys. From the enemy’s point of view, if they intercept the message and suspect that the algorithm being used is the Caesar shift, then they merely have to check the 25 possibilities. However, if the sender uses the more general substitution algorithm, which permits the cipher alphabet to be any rearrangement of the plain alphabet, then there are 400,000,000,000,000,000,000,000,000 possible keys from which to choose. One such is shown in Figure 5. From the enemy’s point of view, if the message is intercepted and the algorithm is known, there is still the horrendous task of checking all possible keys. If an enemy agent were able to check one of the 400,000,000,000,000,000,000,000,000 possible keys every second, it would take roughly a billion times the lifetime of the universe to check all of them and decipher the message.
Figure 5 An example of the general substitution algorithm, in which each letter in the plaintext is substituted with another letter according to a key. The key is defined by the cipher alphabet, which can be any rearrangement of the plain alphabet.
The beauty of this type of cipher is that it is easy to implement, but provides a high level of security. It is easy for the sender to define the key, which consists merely of stating the order of the 26 letters in the rearranged cipher alphabet, and yet it is effectively impossible for the enemy to check all possible keys by the so-called brute-force attack. The simplicity of the key is important, because the sender and receiver have to share knowledge of the key, and the simpler the key, the less the chance of a misunderstanding.
In fact, an even simpler key is possible if the sender is prepared to accept a slight reduction in the number of potential keys. Instead of randomly rearranging the plain alphabet to achieve the cipher alphabet, the sender chooses a keyword or keyphrase. For example, to use JULIUS CAESAR as a keyphrase, begin by removing any spaces and repeated letters (JULISCAER), and then use this as the beginning of the jumbled cipher alphabet. The remainder of the cipher alphabet is merely the remaining letters of the alphabet, in their correct order, starting where the keyphrase ends. Hence, the cipher alphabet would read as follows.
The advantage of building a cipher alphabet in this way is that it is easy to memorize the keyword or keyphrase, and hence the cipher alphabet. This is important, because if the sender has to keep the cipher alphabet on a piece of paper, the enemy can capture the paper, discover the key, and read any communications that have been encrypted with it. However, if the key can be committed to memory it is less likely to fall into enemy hands. Clearly the number of cipher alphabets generated by keyphrases is smaller than the number of cipher alphabets generated without restriction, but the number is still immense, and it would be effectively impossible for the enemy to unscramble a captured message by testing all possible keyphrases.
This simplicity and strength meant that the substitution cipher dominated the art of secret writing throughout the first millennium A.D. Codemakers had evolved a system for guaranteeing secure communication, so there was no need for further development-without necessity, there was no need for further invention. The onus had fallen upon the codebreakers, those who were attempting to crack the substitution cipher. Was there any way for an enemy interceptor to unravel an encrypted message? Many ancient scholars considered that the substitution cipher was unbreakable, thanks to the gigantic number of possible keys, and for centuries this seemed to be true. However, codebreakers would eventually find a shortcut to the process of exhaustively searching all keys. Instead of taking billions of years to crack a cipher, the shortcut could reveal the message in a matter of minutes. The breakthrough occurred in the East, and required a brilliant combination of linguistics, statistics and religious devotion.
The Arab Cryptanalysts
At the age of about forty, Muhammad began regularly visiting an isolated cave on Mount Hira just outside Mecca. This was a retreat, a place for prayer, meditation and contemplation. It was during a period of deep reflection, around A.D. 610, that he was visited by the archangel Gabriel, who proclaimed that Muhammad was to be the messenger of God. This was the first of a series of revelations which continued until Muhammad died some twenty years later. The revelations were recorded by various scribes during the Prophet’s life, but only as fragments, and it was left to Abū Bakr, the first caliph of Islam, to gather them together into a single text. The work was continued by Umar, the second caliph, and his daughter Hafsa, and was eventually completed by Uthmān, the third caliph. Each revelation became one of the 114 chapters of the Koran.
The ruling caliph was responsible for carrying on the work of the Prophet, upholding his teachings and spreading his word. Between the appointment of Abū Bakr in 632 to the death of the fourth caliph, Alī, in 661, Islam spread until half of the known world was under Muslim rule. Then in 750, after a century of consolidation, the start of the Abbasid caliphate (or dynasty) heralded the golden age of Islamic civilization. The arts and sciences flourished in equal measure. Islamic craftsmen bequeathed us magnificent paintings, ornate carvings, and the most elaborate textiles in history, while the legacy of Islamic scientists is evident from the number of Arabic words that pepper the lexicon of modern science such as algebra, alkaline and zenith.
The richness of Islamic culture was to a large part the result of a wealthy and peaceful society. The Abbasid caliphs were less interested than their predecessors in conquest, and instead concentrated on establishing an organized and affluent society. Lower taxes encouraged businesses to grow and gave rise to greater commerce and industry, while strict laws reduced corruption and protected the citizens. All of this relied on an effective system of administration, and in turn the administrators relied on secure communication achieved through the use of encryption. As well as encrypting sensitive affairs of state, it is documented that officials protected tax records, demonstrating a widespread and routine use of cryptography. Further evidence comes from many administrative manuals, such as the tenth-century Adab al-Kuttāb (“The Secretaries’ Manual”), which include sections devoted to cryptography.
The administrators usually employed a cipher alphabet which was simply a rearrangement of the plain alphabet, as described earlier, but they also used cipher alphabets that contained other types of symbols. For example, a in the plain alphabet might be replaced by # in the cipher alphabet, b might be replaced by +, and so on. The monoalphabetic substitution cipher is the general name given to any substitution cipher in which the cipher alphabet consists of either letters or symbols, or a mix of both. All the substitution ciphers that we have met so far come within this general category.
Had the Arabs merely been familiar with the use of the monoalphabetic substitution cipher, they would not warrant a significant mention in any history of cryptography. However, in addition to employing ciphers, the Arab scholars were also capable of destroying ciphers. They in fact invented cryptanalysis, the science of unscrambling a message without knowledge of the key. While the cryptographer develops new methods of secret writing, it is the cryptanalyst who struggles to find weaknesses in these methods in order to break into secret messages. Arabian cryptanalysts succeeded in finding a method for breaking the monoalphabetic substitution cipher, a cipher that had remained invulnerable for several centuries.
Cryptana
lysis could not be invented until a civilization had reached a sufficiently sophisticated level of scholarship in several disciplines, including mathematics, statistics and linguistics. The Muslim civilization provided an ideal cradle for cryptanalysis, because Islam demands justice in all spheres of human activity, and achieving this requires knowledge, or ilm. Every Muslim is obliged to pursue knowledge in all its forms, and the economic success of the Abbasid caliphate meant that scholars had the time, money and materials required to fulfill their duty. They endeavored to acquire the knowledge of previous civilizations by obtaining Egyptian, Babylonian, Indian, Chinese, Farsi, Syriac, Armenian, Hebrew and Roman texts and translating them into Arabic. In 815, the Caliph al-Ma’mūn established in Baghdad the Bait al-Hikmah (“House of Wisdom”), a library and center for translation.
At the same time as acquiring knowledge, the Islamic civilization was able to disperse it, because it had procured the art of papermaking from the Chinese. The manufacture of paper gave rise to the profession of warraqīn, or “those who handle paper,” human photocopying machines who copied manuscripts and supplied the burgeoning publishing industry. At its peak, tens of thousands of books were published every year, and in just one suburb of Baghdad there were over a hundred bookshops. As well as such classics as Tales from the Thousand and One Nights, these bookshops also sold textbooks on every imaginable subject, and helped to support the most literate and learned society in the world.
In addition to a greater understanding of secular subjects, the invention of cryptanalysis also depended on the growth of religious scholarship. Major theological schools were established in Basra, Kufa and Baghdad, where theologians scrutinized the revelations of Muhammad as contained in the Koran. The theologians were interested in establishing the chronology of the revelations, which they did by counting the frequencies of words contained in each revelation. The theory was that certain words had evolved relatively recently, and hence if a revelation contained a high number of these newer words, this would indicate that it came later in the chronology. Theologians also studied the Hadīth, which consists of the Prophet’s daily utterances. They tried to demonstrate that each statement was indeed attributable to Muhammad. This was done by studying the etymology of words and the structure of sentences, to test whether particular texts were consistent with the linguistic patterns of the Prophet.
Significantly, the religious scholars did not stop their scrutiny at the level of words. They also analyzed individual letters, and in particular they discovered that some letters are more common than others. The letters a and l are the most common in Arabic, partly because of the definite article al-, whereas the letter j appears only a tenth as frequently. This apparently innocuous observation would lead to the first great breakthrough in cryptanalysis.
Although it is not known who first realized that the variation in the frequencies of letters could be exploited in order to break ciphers, the earliest known description of the technique is by the ninth-century scientist Abū Yūsūf Ya’qūb ibn Is-hāq ibn as-Sabbāh ibn ‘omrān ibn Ismaīl al-Kindī. Known as “the philosopher of the Arabs,” al-Kindī was the author of 290 books on medicine, astronomy, mathematics, linguistics and music. His greatest treatise, which was rediscovered only in 1987 in the Sulaimaniyyah Ottoman Archive in Istanbul, is entitled A Manuscript on Deciphering Cryptographic Messages; the first page is shown in Figure 6. Although it contains detailed discussions on statistics, Arabic phonetics and Arabic syntax, al-Kindī’s revolutionary system of cryptanalysis is encapsulated in two short paragraphs:
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 ciphertext 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-Kindī’s explanation is easier to explain in terms of the English alphabet. First of all, it is necessary to study a lengthy piece of normal English text, perhaps several, in order to establish the frequency of each letter of the alphabet. In English, e is the most common letter, followed by t, then a, and so on, as given in Table 1. Next, examine the ciphertext in question, and work out the frequency of each letter. If the most common letter in the ciphertext is, for example, J then it would seem likely that this is a substitute for e. And if the second most common letter in the ciphertext is P, then this is probably a substitute for t, and so on. Al-Kindī’s technique, known as frequency analysis, shows that it is unnecessary to check each of the billions of potential keys. Instead, it is possible to reveal the contents of a scrambled message simply by analyzing the frequency of the characters in the ciphertext.
Figure 6 The first page of al-Kindī’s manuscript On Deciphering Cryptographic Messages, containing the oldest known description of cryptanalysis by frequency analysis. (photo credit 1.2)
However, it is not possible to apply al-Kindī’s recipe for cryptanalysis unconditionally, because the standard list of frequencies in Table 1 is only an average, and it will not correspond exactly to the frequencies of every text. For example, a brief message discussing the effect of the atmosphere on the movement of striped quadrupeds in Africa would not yield to straightforward frequency analysis: “From Zanzibar to Zambia and Zaire, ozone zones make zebras run zany zigzags.” In general, short texts are likely to deviate significantly from the standard frequencies, and if there are less than a hundred letters, then decipherment will be very difficult. On the other hand, longer texts are more likely to follow the standard frequencies, although this is not always the case. In 1969, the French author Georges Perec wrote La Disparition, a 200-page novel that did not use words that contain the letter e. Doubly remarkable is the fact that the English novelist and critic Gilbert Adair succeeded in translating La Disparition into English, while still following Perec’s shunning of the letter e. Entitled A Void, Adair’s translation is surprisingly readable (see Appendix A). If the entire book were encrypted via a monoalphabetic substitution cipher, then a naive attempt to decipher it might be stymied by the complete lack of the most frequently occurring letter in the English alphabet.
Table 1 This table of relative frequencies is based on passages taken from newspapers and novels, and the total sample was 100,362 alphabetic characters. The table was compiled by H. Beker and F. Piper, and originally published in Cipher Systems: The Protection Of Communication.
Letter Percentage
a 8.2
b 1.5
c 2.8
d 4.3
e 12.7
f 2.2
g 2.0
h 6.1
i 7.0
j 0.2
k 0.8
l 4.0
m 2.4
n 6.7
o 7.5
p 1.9
q 0.1
r 6.0
s 6.3
t 9.1
u 2.8
v 1.0
w 2.4
x 0.2
y 2.0
z 0.1
Having described the first tool of cryptanalysis, I shall continue by giving an example of how frequency analysis is used to decipher a ciphertext. I have avoided peppering the whole book with examples of cryptanalysis, but with frequency analysis I make an exception. This is partly because frequency analysis is not as difficult as it sounds, and partly because it is the primary cryptanalytic tool. Furthermore, the example that follows provides insight into the modus opera
ndi of the cryptanalyst. Although frequency analysis requires logical thinking, you will see that it also demands guile, intuition, flexibility and guesswork.
Cryptanalyzing a Ciphertext
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV OPVOV LBO LXRO CI SX’XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: “DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?”
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK
Imagine that we have intercepted this scrambled message. The challenge is to decipher it. We know that the text is in English, and that it has been scrambled according to a monoalphabetic substitution cipher, but we have no idea of the key. Searching all possible keys is impractical, so we must apply frequency analysis. What follows is a step-by-step guide to cryptanalyzing the ciphertext, but if you feel confident then you might prefer to ignore this and attempt your own independent cryptanalysis.