Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen
Чтение книги онлайн.

Читать онлайн книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen страница 26

СКАЧАТЬ

      The method of coincidences

      We will now use the second principle of “coincidences,” to find the length of the keyword. The sequence of plain text letters in positions 1 to n, n plus 1 to 2 n, 2 n plus 1, to 3 n, etc., should be approximately the same, especially if n is large. It follows that a similar result holds true for the corresponding sequences of cipher text letters. Thus, if we slide the cipher text along itself and count the number of coincidences (i.e. agreements) at each displacement, then on average the maximum number of coincidences will occur after an integer multiple of the keyword length n (i.e. the max occurs for some lamda n, lamda equals 1 comma 2 comma 3 comma ellipsis). This technique can be illustrated using the following example: We will first determine the period n and use it to determine the nature of the keyword from a cipher text passage:

VVHZK UHRGF HGKDK ITKDW EFHEV SGMPH
KIUWA XGSQX JQHRV IUCCB GACGF SPGLH
GFHHD MHZGF BSPSW SDSXR DFHEM OEPGI
QXKZW LGHZI PHLIV VFIPH XVA

      To find n, write the cipher text on a long strip of paper, and copy it onto a second strip of paper beneath the first strip. For a displacement of 1, move the bottom strip to the left by one letter and count the number of character coincidences. Repeat this process for several displacements until the maximum displacement is obtained. The shift shown below corresponds to a displacement of 3:

V V H Z K U H R G F H G K D ellipsis ellipsis
V V H Z K U H R G F H G K D K I T ellipsis ellipsis
Displacement Number of coincidences
1 4
2 4
3 9
4 12
5 5
6 2
7 7
8 7

      From our results, the maximum number of occurrences appears for a displacement of 4. Since we know the maximum displacement occurs for a scalar multiple of the period, the period is likely either 2 or 4.

      Remark

      In applying the second principle, we are using a probabilistic argument. That is, in the above example, we cannot be certain that the period is either 2 or 4; however, we can say with high probability that it is likely to be either 2 or 4. If we were unable to decipher the text with a keyword length of 2 or 4, we would then try with the next highest number of coincidences, which occurs for displacement 3.

      Finding the keyword