Kasiski examination

Kasiski examination

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 independently developed by Charles Babbage and later Friedrich Kasiski.

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 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 "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, 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.

# 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 repeats this for as many repeated groups as appear in the text.
# The analyst next factors each of these numbers. If any number is repeated in the majority of these factorings, this is probably the length of the keyword. This is because repeated groups can appear by coincidence, but are much more likely to occur when the same letters are encrypted using the same key letters. The key letters are repeated at multiples of the key length, so the distances found in step 1 are likely to be multiples of the key length.
# Once the keyword length is known, the clever observation of Babbage and Kasiski comes into play. If the keyword is N letters long, then every Nth letter must be 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 solved 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, he or she can use that knowledge to read future messages, if the key does not change.

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 then 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 analysis.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Friedrich Kasiski — Major Friedrich Wilhelm Kasiski (29 November 1805 ndash;22 May 1881) was a Prussian infantry officer, cryptographer and archeologist. Kasiski was born in Schlochau, West Prussia (now Człuchów, Poland).Military serviceKasiski enlisted in East… …   Wikipedia

  • 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.The Vigenère (pronEng|ˌviːdʒɪˈnɛəɹ, veedj ih nair )… …   Wikipedia

  • Classical cipher — A cipher is a means of concealing a message, where letters of the message are substituted or transposed for other letters, letter pairs, and sometimes for many letters. In cryptography, a classical cipher is a type of cipher that was used… …   Wikipedia

  • Cryptanalysis — Close up of the rotors in a Fialka cipher machine Cryptanalysis (from the Greek kryptós, hidden , and analýein, to loosen or to untie ) is the study of methods for obtaining the meaning of encrypted information, without access to the secret… …   Wikipedia

  • Substitution cipher — In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters,… …   Wikipedia

  • Cryptography — Secret code redirects here. For the Aya Kamiki album, see Secret Code. Symmetric key cryptography, where the same key is used both for encryption and decryption …   Wikipedia

  • One-time pad — Excerpt from a one time pad In cryptography, the one time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit …   Wikipedia

  • Transposition cipher — In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext… …   Wikipedia

  • ROT13 — replaces each letter by its partner 13 characters further along the alphabet. For example, HELLO becomes URYYB (or, rev …   Wikipedia

  • Caesar cipher — The action of a Caesar cipher is to replace each plaintext letter with one fixed number of places down the alphabet. This example is with a shift of three, so that a B in the p …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”