Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 47

Now that the Vigenère cipher has been defined, we will show how to use the frequencies of letters in English, to break this cipher. We have two tasks.

 Find the keyword length.

 Find the keyword itself.

We have two methods to find the length of the keyword. The first method, the Babbage–Kasiski method, attempts to find repeated successive triples (or four‐tuples, or five‐tuples, etc.,) of letters in the cipher text. The second method treats the English language like a stationary or even ergodic source (see Chapter 11).

We will use two fundamental principles in carrying out our tasks.

 “E” is the most frequent letter of the English language.

 Informally, written English tends to “repeat itself.” This means that the frequencies of a passage starting in position 1 are similar to the frequencies of the passage starting in position when we slide the text along itself.

Once we obtain , the key‐length, we can find the keyword itself. We do this by using the first fundamental property above. Namely, we exploit the statistics of the letters in English, or pairs of letters (i.e. digrams), or trigrams, etc.

The second principle has two important interpretations. For the Babbage–Kasiski method, this means that if we find a repeated letter (or sequence of letters) in the cipher text there is a good chance that it comes from a given letter (or sequence of letters) in the plain text that has been enciphered by a given letter (or letters) in the key. Thus, there is a reasonable expectation that the distances between such repeated sequences of letters equals the key length or a multiple of the key length.

The second principle has an important implication in terms of our second method, called the method of “coincidences,” as well. The basic idea is explained in an example below.