The Code Book: The Secret History of Codes and Code-breaking. Simon Singh
Чтение книги онлайн.

Читать онлайн книгу The Code Book: The Secret History of Codes and Code-breaking - Simon Singh страница 7

Название: The Code Book: The Secret History of Codes and Code-breaking

Автор: Simon Singh

Издательство: HarperCollins

Жанр: Прочая образовательная литература

Серия:

isbn: 9780007378302

isbn:

СКАЧАТЬ the religious scholars did not stop their scrutiny at the level of words. They also analysed individual letters, and in particular they discovered that some letters are more common than others. The letters a and I 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 realised 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
fYa’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.

      Figure 6 The first page of al-Kind

’s manuscript On Deciphering Cryptographic Messages, containing the oldest known description of cryptanalysis by frequency analysis. Ibrahim A. Al-Kadi and Mohammed Mrayati, King Saud University, Riyadh.

      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 analysing the frequency of the characters in the ciphertext.

      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.

      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.

      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 operandi of the cryptanalyst. Although frequency analysis requires logical thinking, you will see that it also demands guile, intuition, flexibility and guesswork.

      Cryptanalysing 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 cryptanalysing the ciphertext, but if you feel confident then you might prefer to ignore this and attempt your own independent cryptanalysis.

      The immediate reaction of any cryptanalyst upon seeing such a ciphertext is to analyse the frequency of all the letters, which results in Table 2. Not surprisingly, the letters vary in their frequency. The question is, can we identify what any of them represent, based on their frequencies? The ciphertext is relatively short, so we cannot slavishly apply frequency analysis. It would be naive to assume that the СКАЧАТЬ