Vigenère cipher: Encyclopedia II - Vigenère cipher - Cryptanalysis

Vigenère cipher - Cryptanalysis

The strength behind the Vigenère cipher is, like all polyalphabetic ciphers, to make frequency analysis more difficult. Frequency analysis is the practice of decrypting a message by counting the frequency of ciphertext letters, and equating it to the letter frequency of normal text. For instance if P occurred most in a ciphertext whose plaintext is in English one could suspect that P corresponded to E, because E is the most frequently used letter in English. Using the Vigenère cipher, E can be enciphered as any of several letters in the alphabet at different points in the message thus defeating simple frequency analysis.

The critical weakness in the Vigenère cipher is the relatively short and repeated nature of its key. If a cryptanalyst discovers the key's length then the cipher text can be treated as a series of different Caesar ciphers, which individually are trivially broken. The Kasiski and Friedman tests help divine a ciphertext's key length.

Vigenère cipher - Kasiski examination

Friedrich Kasiski published the first successful attack on the Vigenère cipher in 1863, but Charles Babbage had already developed the same test in 1854. Babbage decided to break the Vigenère cipher when John Hall Brock Thwaites submitted a "new" cipher to the Journal of the Society of the Arts. When Babbage showed that Thwaites' cipher was essentially just another recreation of the Vigenère cipher Thwaites grew irritated and challenged Babbage to break his cipher.

The Kasiski examination, also called the Kasiski test, takes advantage of the fact that certain common words like "the" will, by chance, be encrypted using the same key letters, leading to repeated groups in the ciphertext. For example, a message encrypted with the keyword ABCDEF might not encipher "crypto" the same way each time it appears in the plain text:

Key:        ABCDEF AB CDEFA BCD EFABCDEFABCD
Plaintext:  CRYPTO IS SHORT FOR CRYPTOGRAPHY
Ciphertext: CSASXT IT UKSWT GQU GWYQVRKWAQJB

The encrypted text here will not have repeated sequences that correspond to repeated sequences in the plaintext. However, if the key length is different, as in this example:

Key:        ABCDAB CD ABCDA BCD ABCDABCDABCD
Plaintext:  CRYPTO IS SHORT FOR CRYPTOGRAPHY
Ciphertext: CSASTP KV SIQUT GQU CSASTPIUAQJB

Then the Kasiski test is effective. Longer messages make the test more accurate because they usually contain more repeated ciphertext segments. The following ciphertext has several repeated segments and allows a cryptanalyst to discover its key length:

Ciphertext: DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD

The distance between the repeated DYDUXRMHs is 18. This, assuming that the repeated segments represent the same plaintext segments, implies that the key is 18, 9 or 2 characters long. The distance between the NQDs is 20 characters. This means that the key length could be 20, 10, 5 or 2 characters long (all factors of the distance are possible key lengths). By taking the intersection of these sets one could safely conclude that the key length is 2.

Vigenère cipher - Friedman test

The Friedman test (also known as the Kappa test) was invented in 1925 by William F. Friedman. Friedman used the index of coincidence, the probability that any two cipher letters represent the same letter in the plaintext, to break the cipher. By knowing that the probability of any two randomly chosen letters in English are the same is about 6.5%, Friedman found that the key length is approximately equal to:

where I (the index of coincidence) equals

n is the length of the text and n₁ through n₂₆ are the frequencies of the letters.

The test is, however, only an approximation. It would be necessary to try key lengths close to the test result. The accuracy increases with the size of the text analyzed.

Adapted from the Wikipedia article "Cryptanalysis", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki