Vigenère cipher: Encyclopedia - Vigenère cipher

Vigenère cipher

The Vigenère cipher is a method of encryption that uses a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution.

The Vigenère cipher has been reinvented many times. The method was originally described by Giovan Batista Belaso in his 1553 book La cifra del. Sig. Giovan Batista Belaso, however, the scheme was later misattributed to Blaise de Vigenère in the 19th century, and is now widely known as the "Vigenère cipher".

This cipher is well known because while it is easy to understand and implement, it often appears to beginners to be unbreakable; this earned it the moniker le chiffre indéchiffrable (French for 'the unbreakable cipher'). Consequently, many programmers have implemented obfuscation or encryption schemes in their applications, which are essentially Vigenère ciphers, only to have them broken.

Vigenère cipher - History

Leone Battista Alberti (the inventor of polyalphabetic ciphers), Johannes Trithemius (in his works Poligraphia and Stegonographia) and Giovanni Battista Della Porta (in Magia Naturalis) all created important predecessors to the Vigenère cipher. Trithemius was the first person to introduce the tabula recta, but he provided no system for switching between cipher alphabets.

The Vigenère cipher was originally described by Giovan Batista Belaso in his 1553 book La cifra del. Sig. Giovan Batista Belaso. Blaise de Vigenère published his description of the cipher before the court of Henry III of France, in 1586 (the same year that the Babington Plot was foiled because of frequency analysis). Later, in the 19th century, the invention of the cipher was misattributed to Vigenère.

Noted author and mathematician Charles Ludwidge Dodgson (Lewis Carroll) called the Vigenère cipher unbreakable in his 1868 piece "The Alphabet Cipher" in a children's magazine. In 1917, Scientific American described the Vigenère cipher as "impossible of translation"^[1]. Despite this reputation, however, the cipher was broken in the 19th century.

The Vigenère cipher can be simple enough to be a field cipher if it is used in conjunction with cipher disks ^[2]. The Confederacy used the Vigenère cipher during the American Civil War ^[3].

Gilbert Vernam tried to repair the broken cipher (creating the Vernam-Vigenère cipher in 1918), but no matter what he did the cipher was still vulnerable to cryptanalysis. Vernam's work, however, eventually led to the one-time pad, the only theoretically secure cipher.

Vigenère cipher - Description

In a Caesar cipher, each letter of the alphabet is shifted along some number of places; for example, in a Caesar cipher of shift 3, A would become D, B would become E and so on. The Vigenère cipher consists of using several Caesar ciphers in sequence with different shift values.

To encipher, a table of alphabets can be used, termed a tabula recta, Vigenère square, or Vigenère table. It consists of the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible Caesar ciphers. At different points in the encryption process, the cipher uses a different alphabet from one of the rows. The alphabet used at each point depends on a repeating keyword.

For example, suppose that the plaintext to be encrypted is:

The person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword "LEMON":

The first letter of the plaintext, A, is enciphered using the alphabet in row L, which is the first letter of the key. This is done by looking at the letter in row L and column A of the Vigenère square, namely L. Similarly, for the second letter of the plaintext, the second letter of the key is used; the letter at row E and column T is X. The rest of the plaintext is enciphered in a similar fashion:

Decryption is performed by finding the position of the ciphertext letter in a row of the table, and then taking the label of the column in which it appears as the plaintext. For example, in row L, the ciphertext L appears in column A, which taken as the first plaintext letter. The second letter is decrypted by looking up X in row E of the table; it appears in column T, which is taken as the plaintext letter.

Vigenère can also be viewed algebraically. If the letters A–Z are taken to be the numbers 0–25, and addition is performed modulo 26, then Vigenère encryption can be written,

and decryption,

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

Vigenère cipher - The cipher of Blaise de Vigenère

Vigenère actually invented a stronger cipher: an autokey cipher. The name "Vigenère cipher" became associated with this polyalphabetic cipher instead. In fact, the two ciphers were often confused, and both were sometimes called "le chiffre indéchiffrable", or "the unbreakable cipher". For nearly 300 years this cipher was thought to be unbreakable, but Charles Babbage and Friedrich Kasiski independently found a way to break it in the middle of the 19th century. Babbage actually broke the much stronger autokey cipher, while Kasiski is generally credited with the first published solution to the fixed-key polyalphabetic ciphers.

Vigenère cipher - Variants

Despite the Vigenère cipher's apparent strength it never became widely used throughout Europe. The Gronsfeld cipher is a variant created by Count Gronselfd which is identical to the Vigenère cipher; except that it uses just 10 different cipher alphabets (corresponding to the digits 0 to 9). The Gronsfeld cipher is strengthened because its key is not a word, but it is weakened because it has just 10 cipher alphabets. Gronsfeld's cipher did become widely used throughout Germany and Europe, despite its weaknesses.

The Beaufort cipher, created by Sir Francis Beaufort, uses a slightly modified enciphering mechanism which allows reciprocal encipherment (the enciphering and deciphering mechanisms are the same) and is easier to use.

Vigenère cipher - Notes

• ^ Codes, Ciphers, & Codebreaking (The Rise Of Field Ciphers)
• ^ The confederacy used the Vigenère key "Complete Victory", but changed it to "Come Retribution" as the war came to a close in 1865. (Conrad, James Lee (1997). The Young Lions: Confederate Cadets at War, 130, Stackpole Books. ISBN 0-81171-975-8.)
• ^ Knudsen, Lars R. (1998). "Block Ciphers— a survey" Bart Preneel and Vincet Rijmen State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures, 29. ISBN 3540654747.

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