Kasiski test
In cryptanalysis, the Kasiski examination or Kasiski test is a method of attacking polyalphabetic substitution ciphers, such as Vigenere ciphers. It was developed by Friedrich Kasiski.
The Kasiski examination allows a cryptanalyst to deduce the length of the keyword used in the polyalphabetic substitution cipher. 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.
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 them 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.
"Crypto" is a repeated string, and the distance between the occurrences is 20 characters. We will line up the plaintext with first a six-character keyword "abcdef" (6 does not divide 20) and a five-character keyword "abcde" (5 divides 20).
abcdefabcdefabcdefabcdefabcdefabc
Crypto is short for cryptography.
Notice that the first instance of "crypto" lines up with "abcdef" and the second instance lines up with "cdefab". The two instances will encrypt to different ciphertexts.
abcdeabcdeabcdeabcdeabcdeabcdeabc
Crypto is short for cryptography.
Note that both occurrences of "crypto" now line up with "abcde". The two instances will encrypt to the same ciphertext.
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, human interaction is still required, since some repeated strings may just be coincidence, and the distances will have a greatest common divisor of 1. A human cryptanalyst has to rule out the coincidences to find the correct length. Then, of course, the human has to cryptanalyze the monoalphabetic ciphertexts that result.
