Kasiski examination
Encyclopedia
In cryptanalysis
, Kasiski examination (also referred to 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.
.
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.
"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 and the Kasiski examination will reveal nothing.
abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto is short for cryptography.
Note that both occurrences of "crypto" now line up with "abcdea". The two instances will encrypt to the same ciphertext and the Kasiski examination will be effective.
Modern attacks on polyalphabetic ciphers are essentially identical to that described above, with the one improvement of coincidence counting. Instead of looking for repeating groups, a modern analyst would take two copies of the message and lay one above another.
Modern analysts use computers, but this description illustrates the principle that the computer algorithms implement.
The generalized method
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
, Kasiski examination (also referred to as Kasiski's Test or Kasiski's Method) is a method of attacking polyalphabetic substitution ciphers
Polyalphabetic cipher
A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. The Vigenère cipher is probably the best-known example of a polyalphabetic cipher, though it is a simplified special case...
, such as the Vigenère cipher
Vigenère cipher
The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution....
. It was first published by Friedrich Kasiski
Friedrich Kasiski
Major Friedrich Wilhelm Kasiski was a Prussian infantry officer, cryptographer and archeologist. Kasiski was born in Schlochau, West Prussia .-Military service:...
in 1863, but seems to have been
independently discovered by Charles Babbage
Charles Babbage
Charles Babbage, FRS was an English mathematician, philosopher, inventor and mechanical engineer who originated the concept of a programmable computer...
as early as 1846.
How it works
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 analysisFrequency analysis
In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers....
.
The Kasiski examination involves looking for strings of characters that are repeated in the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
. 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
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
of all the distances.
The reason this test works is that if a repeated string occurs in the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
, 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.
"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 and the Kasiski examination will reveal nothing.
abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto is short for cryptography.
Note that both occurrences of "crypto" now line up with "abcdea". The two instances will encrypt to the same ciphertext and the Kasiski examination will be effective.
A string based attack
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 was FGXTHJAQWNFGXQ, the distance between FGX's is 10. The analyst records the distances for all repeated groups in the text.
- The analyst next factorsInteger factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
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 analysisFrequency analysisIn cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers....
. - 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.
Superposition
Kasiski actually used "superimposition" to solve the Vigenère cipher. He started by finding the key length, as above. Then he took multiple copies of the message and laid them one-above-another, each one shifted left by the length of the key. Kasiski then observed that each column was made up of letters encrypted with a single alphabet. His method was equivalent to the one described above, but is perhaps easier to picture.Modern attacks on polyalphabetic ciphers are essentially identical to that described above, with the one improvement of coincidence counting. Instead of looking for repeating groups, a modern analyst would take two copies of the message and lay one above another.
Modern analysts use computers, but this description illustrates the principle that the computer algorithms implement.
The generalized method
- The analyst shifts the bottom message one letter to the left, then two letters to the left, etc., each time going through the entire message and counting the number of times the same letter appears in the top and bottom message.
- The number of "coincidences" goes up sharply when the bottom message is shifted by a multiple of the key length, because then the adjacent letters are in the same language using the same alphabet.
- Having found the key length, cryptanalysis proceeds as described above using frequency analysisFrequency analysisIn cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers....
.