Касиски әдісі: Полиалфавиттік шифрларды талдау жолы

Method in cryptanalysis
In cryptanalysis, Kasiski examination (also known as Kasiski's test or Kasiski's method) is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. It was first published by Friedrich Kasiski in 1863, but seems to have been independently discovered by Charles Babbage as early as 1846.

In polyalphabetic substitution ciphers where the substitution alphabets are chosen by the use of a keyword, the Kasiski examination allows a cryptanalyst to deduce the length of the keyword. Once the length of the keyword is discovered, the cryptanalyst lines up the ciphertext in n columns, where n is the length of the keyword. Then each column can be treated as the ciphertext of a monoalphabetic substitution cipher. As such, each column can be attacked with frequency analysis. Similarly, where a rotor stream cipher machine has been used, this method may allow the deduction of the length of individual rotors. The Kasiski examination involves looking for strings of characters that are repeated in the ciphertext. The strings should be three characters long or more for the examination to be successful. Then, the distances between consecutive occurrences of the strings are likely to be multiples of the length of the keyword. Thus finding more repeated strings narrows down the possible lengths of the keyword, since we can take the greatest common divisor of all the distances. The reason this test works is that if a repeated string occurs in the plaintext, and the distance between corresponding characters is a multiple of the keyword length, the keyword letters will line up in the same way with both occurrences of the string. For example, consider the plaintext:

crypto is short for cryptography.

"" is a repeated string, and the distance between the occurrences is 20 characters. If we line up the plaintext with a 6 character keyword "" (6 does not divide into 20):

crypto is short for cryptography. the first instance of "" lines up with "" and the second instance lines up with "". The two instances will encrypt to different ciphertexts and the Kasiski examination will reveal nothing. However, with a 5 character keyword "" (5 divides into 20):

crypto is short for cryptography. both occurrences of "" line up with "". The two instances will encrypt to the same ciphertext and the Kasiski examination will be effective.

The difficulty of using the Kasiski examination lies in finding repeated strings. This is a very hard task to perform manually, but computers can make it much easier. However, care is still required, since some repeated strings may just be coincidence, so that some of the repeat distances are misleading. The cryptanalyst has to rule out the coincidences to find the correct length. Then, of course, the monoalphabetic ciphertexts that result must be cryptanalyzed. A cryptanalyst looks for repeated groups of letters and counts the number of letters between the beginning of each repeated group. For instance, if the ciphertext were , the distance between groups is 10. The analyst records the distances for all repeated groups in the text. The analyst next factors each of these numbers. If any number is repeated in the majority of these factorings, it is likely to be the length of the keyword. This is because repeated groups are more likely to occur when the same letters are encrypted using the same key letters than by mere coincidence; this is especially true for long matching strings. The key letters are repeated at multiples of the key length, so most of the distances found in step 1 are likely to be multiples of the key length. A common factor is usually evident. Once the keyword length is known, the following observation of Babbage and Kasiski comes into play. If the keyword is N letters long, then every Nth letter must have been enciphered using the same letter of the keytext. Grouping every Nth letter together, the analyst has N "messages", each encrypted using a one alphabet substitution, and each piece can then be attacked using frequency analysis. Using the solved message, the analyst can quickly determine what the keyword was. Or, in the process of solving the pieces, the analyst might use guesses about the keyword to assist in breaking the message. Once the interceptor knows the keyword, that knowledge can be used to read other messages that use the same key.