|
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 people have tried to implement obfuscation or encryption schemes that are essentially Vigenère ciphers, only to have them broken•.
History The first polyalphabetic cipher, created by Leone Battista Alberti around 1467, used a metal cipher disc to switch between cipher alphabets. Alberti's system only switched alphabets after several words, and switches were indicated by writing the letter of the corresponding alphabet in the ciphertext. Later, in 1508, Johannes Trithemius, in his work Poligraphia, invented the tabula recta, a critical component of the Vigenère cipher. Trithemius, however, only provided a progressive, rigid and predictable system for switching between cipher alphabets. What is now known as the Vigenère cipher was originally described by Giovan Batista Belaso in his 1553 book La cifra del. Sig. Giovan Batista Belaso. He built upon the tabula recta of Trithemius, but added a repeating "countersign" (a key) to switch cipher alphabets every letter. Blaise de Vigenère published his description of a similar but stronger autokey cipher before the court of Henry III of France, in 1586. Later, in the 19th century, the invention of Belaso's cipher was misattributed to Vigenère. David Kahn in his book The Codebreakers lamented the misattribution by saying that history had "ignored this important contribution and instead named a regressive and elementary cipher for him Vigenère though he had nothing to do with it".• The Vigenère cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks. The Confederate States of America, for example, used a brass cipher disk to implement the Vigenère cipher during the American Civil War. The Confederacy's messages were far from secret and the Union regularly cracked their messages. Throughout the war, the Confederate leadership primarily relied upon three keywords, "Manchester Bluff", "Complete Victory" and, as the war came to a close, "Come Retribution".• 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. Description
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 determine a ciphertext's key length. Kasiski examination For more details on this topic, see 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 was goaded into breaking 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. Babbage tried to get out of it, but eventually gave in and succeeded in decrypting a sample, which turned out to be the poem "The Vision of Sin," by Alfred Tennyson, encrypted according to the keyword "Emily," the first name of Tennyson's wife•. 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, 6, 3, or 2 characters long. The distance between the NQDs is 20 characters. This means that the key length could be 20, 10, 5, 4, or 2 characters long (all factors of the distance are possible key lengths – a key of length one is just a simple shift cipher, where cryptanalysis is much easier). By taking the intersection of these sets one could safely conclude that the key length is (almost certainly) 2. 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 through are the letter frequencies. 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. Frequency analysis Once the length of the key is known, the ciphertext is split into sections with each section corresponding to a single letter in the key. Each portion of the divided ciphertext is equivalent to a single Caesar shift ciphertext. The letter shifts in the sections are determined by the letters in the key for the corresponding portions of the ciphertext. Using methods similar to those used to break the Caesar cipher, the letters in the key can be discovered. Once every letter in the key is known, the cryptanalyst can simply decrypt the ciphertext and reveal the plaintext. Variants The running key variant of the Vigenère cipher was also considered unbreakable at one time. This version uses a block of text as long as plaintext as the key. Since the key is as long as the message the Friedman and Kassiski tests no longer work (the key is not repeated). In 1920, Friedman was the first to discover this variant's weaknesses. The problem with the running key Vigenere cipher is that the cryptanalyst has statistical information about the key (assuming that the block of text is in English) and that information will be reflected in the ciphertext. Vigenère actually invented a stronger cipher: an autokey cipher. The name "Vigenère cipher" became associated with a simpler polyalphabetic cipher instead. In fact, the two ciphers were often confused, and both were sometimes called "le chiffre indéchiffrable". Babbage actually broke the much stronger autokey cipher, while Kasiski is generally credited with the first published solution to the fixed-key polyalphabetic ciphers. A simple variant is to encrypt using the Vigenère decryption method, and decrypt using Vigenère encryption. This method is sometimes referred to as "Variant Beaufort". This is different from the Beaufort cipher, created by Sir Francis Beaufort, which nonetheless is similar to Vigenère but uses a slightly modified enciphering mechanism and tableau. The Beaufort cipher is a reciprocal cipher. Despite the Vigenère cipher's apparent strength it never became widely used throughout Europe. The Gronsfeld cipher is a variant created by Count Gronsfeld 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. Sources | ||||||||||
|
| |||||||||||
 |
|
| |