Vigenère cipher: Difference between revisions
Content deleted Content added
m →Kasiski examination: fix ref |
←Replaced content with 'I'm editing this page, so I've taken it down for a while. I promise it'll be back in a few minutes, so Admins please don't take disciplinary action! --~~~' |
||
| Line 1: | Line 1: | ||
I'm editing this page, so I've taken it down for a while. I promise it'll be back in a few minutes, so Admins please don't take disciplinary action! --[[User:Nmatavka|Nmatavka]] ([[User talk:Nmatavka|talk]]) |
|||
[[Image:Vigenere.jpg|right|thumbnail|The Vigenère cipher is named for Blaise de Vigenère (pictured), although [[Giovan Battista Bellaso]] had invented the cipher earlier. Vigenère did invent a stronger [[autokey cipher]].]] |
|||
The '''Vigenère cipher''' is a method of [[encryption|encrypting]] [[alphabet]]ic text by using a series of different [[Caesar cipher]]s based on the letters of a keyword. It is a simple form of [[Polyalphabetic cipher|polyalphabetic substitution]]. |
|||
The Vigenère ({{IPA-fr|viʒnɛːʁ}}) cipher has been reinvented many times. The method was originally described by [[Giovan Battista Bellaso]] in his 1553 book ''La cifra del. Sig. Giovan Battista Bellaso''; 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 description '''le chiffre indéchiffrable''' (French for 'the indecipherable cipher'). Consequently, many people have tried to implement encryption schemes that are essentially Vigenère ciphers, only to have them broken<ref>{{cite book|first=Laurence D.|last=Smith|year=1943|title=Cryptography the Science of Secret Writing: The Science of Secret Writing|chapter=Substitution Ciphers|editor=|others=|pages=81|publisher=Dover Publications|isbn=0-486-20247-X}}</ref>. |
|||
==History== |
|||
The first well documented description of a polyalphabetic cipher was formulated by [[Leon Battista Alberti]] around 1467 and 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. This was known as the [[Trithemius cipher]]. |
|||
What is now known as the Vigenère cipher was originally described by [[Giovan Battista Bellaso]] in his 1553 book ''La cifra del. Sig. Giovan Battista Bellaso''. He built upon the tabula recta of Trithemius, but added a repeating "countersign" (a [[Key (cryptography)|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 Bellaso'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".<ref name="KahnOrigin">{{cite book|first=Kahn|last=David|year=1999|title=The Codebreakers: The Story of Secret Writing|chapter=On the Origin of a Species|publisher=Simon & Schuster|isbn=0684831309}}</ref> |
|||
The Vigenère cipher gained a reputation for being exceptionally strong. Noted author and mathematician Charles Lutwidge 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".<ref>{{cite book|first=Lars R.|last=Knudsen|year=1998|title=State of the Art in Applied Cryptography: Course on Computer Security and Industrial Cryptograph Leuven Belgium, June 1997 Revised Lectures |chapter=Block Ciphers— a survey|editor=Bart Preneel and Vincent Rijmen|others=|pages=29|publisher=Springer|isbn=3540654747|location=Berlin ; London}}</ref> This reputation was not deserved. [[Charles Babbage]] broke a related, though slightly different cipher known as the [[autoclave cypher]]; however, he didn't publish his work.<ref name="Singh">{{cite book|first=Simon|last=Singh|year=1999|title=The Code Book|chapter=Chapter 2: Le Chiffre Indéchiffrable|editor=|pages=63–78|publisher=[[Anchor Books#Divisions and imprints|Anchor Books]], [[Random House]]|isbn=0-385-49532-3}}</ref> Kasiski entirely broke the cipher and published the technique in the 19th century. Even before this, though, some skilled cryptanalysts could occasionally break the cipher in the 16th century.<ref name="KahnOrigin" /> |
|||
[[File:Confederate cipher disk.png|right|thumb|A reproduction of the Confederacy's cipher disk on display at the [[National Cryptologic Museum]]]] |
|||
The Vigenère cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks. <ref>[http://www.vectorsite.net/ttcode_03.html#m2 Codes, Ciphers, & Codebreaking] (The Rise Of Field Ciphers)</ref> 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 key phrases, "Manchester Bluff", "Complete Victory" and, as the war came to a close, "Come Retribution".<ref>{{cite book|first=Kahn|last=David|year=1999|title=The Codebreakers: The Story of Secret Writing|chapter=Crises of the Union|pages=217–221|publisher=Simon & Schuster|isbn=0684831309}}</ref> |
|||
[[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]], a provably unbreakable cipher. |
|||
{{-}} |
|||
==Description== |
|||
[[Image:Vigenère square.svg|right|thumbnail|300px|The Vigenère square or Vigenère table, also known as the ''[[tabula recta]]'', can be used for encryption and decryption.]] |
|||
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, <tt>A</tt> would become <tt>D</tt>, <tt>B</tt> would become <tt>E</tt> and so on. The Vigenère cipher consists of several Caesar ciphers in sequence with different shift values. |
|||
To encrypt, 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: |
|||
:<tt>ATTACKATDAWN</tt> |
|||
The person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword "LEMON": |
|||
:<tt>LEMONLEMONLE</tt> |
|||
The first letter of the plaintext, <tt>A</tt>, is enciphered using the alphabet in row <tt>L</tt>, which is the first letter of the key. This is done by looking at the letter in row <tt>L</tt> and column <tt>A</tt> of the Vigenère square, namely <tt>L</tt>. Similarly, for the second letter of the plaintext, the second letter of the key is used; the letter at row <tt>E</tt> and column <tt>T</tt> is <tt>X</tt>. The rest of the plaintext is enciphered in a similar fashion: |
|||
{| |
|||
| Plaintext: || <tt>ATTACKATDAWN</tt> |
|||
|- |
|||
| Key: || <tt>LEMONLEMONLE</tt> |
|||
|- |
|||
| Ciphertext: || <tt>LXFOPVEFRNHR</tt> |
|||
|} |
|||
Decryption is performed by going to the row in the table corresponding to the key, finding the position of the ciphertext letter in this row, and then using the column's label as the plaintext. For example, in row <tt>L</tt> (from ''L''EMON), the ciphertext <tt>L</tt> appears in column <tt>A</tt>, which is the first plaintext letter. Next we go to row <tt>E</tt> (from L''E''MON), find the ciphertext <tt>X</tt> in column <tt>T</tt>, which is the second plaintext letter. |
|||
Vigenère can also be viewed algebraically. If the letters <tt>A</tt>–<tt>Z</tt> are taken to be the numbers 0–25, and addition is performed [[modular arithmetic|modulo]] 26, then Vigenère encryption can be written, |
|||
:<math>C_i \equiv (P_i + K_i) \pmod {26}</math> |
|||
and decryption, |
|||
:<math>P_i \equiv (C_i - K_i) \pmod {26}</math> |
|||
Thus using the previous example, to encrypt <tt>A</tt> (<math>\equiv 0</math>) with key letter <tt>L</tt> (<math>\equiv 11</math>) the calculation would result in 11 <math>\equiv</math> <tt>L</tt>. |
|||
:<math>11 \equiv (0+11) \pmod {26}</math> |
|||
Therefore to decrypt <tt>R</tt> (<math>\equiv 17</math>) with key letter <tt>E</tt> (<math>\equiv 4</math>) the calculation would result in 13 <math>\equiv</math> <tt>N</tt>. |
|||
:<math>13 \equiv (17-4) \pmod {26}</math> |
|||
==Cryptanalysis== |
|||
[[Image:Vigenere letter frequencies.PNG|thumb|right|400px|The Vigenère cipher masks the characteristic letter frequencies of English plaintexts, but some patterns remain.]] |
|||
The idea behind the Vigenère cipher, like all polyalphabetic ciphers, is to disguise plaintext [[letter frequencies]], which interferes with a straightforward application of [[frequency analysis]]. For instance, if <tt>P</tt> is the most frequent letter in a ciphertext whose plaintext is in [[English language|English]], one might suspect that <tt>P</tt> corresponds to <tt>E</tt>, because <tt>E</tt> is the most frequently used letter in English. However, using the Vigenère cipher, <tt>E</tt> can be enciphered as different ciphertext letters at different points in the message, thus defeating simple frequency analysis. |
|||
The primary weakness of the Vigenère cipher is the repeating nature of its [[Key (cryptography)|key]]. If a cryptanalyst correctly guesses the key's length, then the cipher text can be treated as interwoven [[Caesar cipher]]s, which individually are easily broken. The Kasiski and Friedman tests can help determine the key length. |
|||
===Kasiski examination=== |
|||
:''For more details on this topic, see [[Kasiski examination]].''<!-- details --> |
|||
In 1863 [[Friedrich Kasiski]] was the first to publish a successful general attack on the Vigenère cipher. Earlier attacks relied on knowledge of the plaintext, or use of a recognizable word as a key. Kasiski's method had no such dependencies. Kasiski was the first to publish an account of the attack, but it's clear that there were others who were aware of it. In 1854, [[Charles Babbage]] was goaded into breaking the Vigenère autoclave cipher (related to, but different to, the simple Vigenère) 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 autoclave cipher, Thwaites challenged Babbage to break his cipher encoded twice, with keys of different length. Babbage 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. Babbage never explained the method he used. Studies of Babbage's notes reveal that he had used the method later published by Kasiski, and suggest that he had been using the method as early as 1846.<ref>Franksen, O. I. (1985) Mr. Babbage's Secret: The Tale of a Cipher—and APL. Prentice Hall.</ref> |
|||
The [[Kasiski examination]], also called the Kasiski test, takes advantage of the fact that repeated words may, by chance, sometimes be encrypted using the same key letters, leading to repeated groups in the ciphertext. For example, Consider the following encryption using the keyword <tt>ABCD</tt>: |
|||
Key: ABCDABCDABCDABCDABCDABCDABCD |
|||
Plaintext: ''CRYPTO''ISSHORTFOR''CRYPTO''GRAPHY |
|||
Ciphertext: ''CSASTP''KVSIQUTGQU''CSASTP''IUAQJB |
|||
There is an easily seen repetition in the ciphertext, and the Kasiski test will be effective. |
|||
Here the distance between the repetitions of <tt>CSASTP</tt> is 16. Assuming that the repeated segments represent the same plaintext segments, this implies that the key is 16, 8, 4, 2, or 1 characters long. (All [[Factorization|factors]] of the distance are possible key lengths – a key of length one is just a simple [[shift cipher]], where cryptanalysis is much easier.) Since key lengths 2 and 1 are unrealistically short, one only needs to try lengths 16, 8, or 4. Longer messages make the test more accurate because they usually contain more repeated ciphertext segments. The following ciphertext has two segments that are repeated: |
|||
Ciphertext: ''VHVS''SP''QUCE''MRVBNBBB''VHVS''URQGIBDUGRNICJ''QUCE''RVUAXSSR |
|||
The distance between the repetitions of <tt>VHVS</tt> is 18. Assuming that the repeated segments represent the same plaintext segments, this implies that the key is 18, 9, 6, 3, 2, or 1 characters long. The distance between the repetitions of <tt>QUCE</tt> is 30 characters. This means that the key length could be 30, 15, 10, 6, 5, 3, 2, or 1 characters long. By taking the [[Intersection (set theory)|intersection]] of these sets one could safely conclude that the most likely key length is 6, since 3, 2, and 1 are unrealistically short.<!-- the key is CARBON and the message is THERECOULDYETBEANOTHERGEOGRAPHERWHOWOULDDISAGREE --> |
|||
===Friedman test=== |
|||
The Friedman test (sometimes known as the kappa test) was invented during the 1920s by [[William F. Friedman]]. Friedman used the [[index of coincidence]], which measures the unevenness of the cipher letter frequencies, to break the cipher. By knowing the probability <math>\kappa_p</math> that any two randomly chosen source-language letters are the same (around 0.067 for monocase English) and the probability of a coincidence for a uniform random selection from the alphabet <math>\kappa_r</math> (1/26 = 0.0385 for English), the key length can be estimated as: |
|||
: <math>{\kappa_p-\kappa_r}\over{\kappa_o-\kappa_r}</math> |
|||
from the observed coincidence rate |
|||
: <math>\kappa_o=\frac{\sum_{i=1}^{c}n_i(n_i -1)}{N(N-1)}</math> |
|||
where ''c'' is the size of the alphabet (26 for English), ''N'' is the length of the text, and ''n''<sub>1</sub> through ''n''<sub>''c''</sub> are the observed ciphertext [[letter frequencies]], as integers. |
|||
This is, however, only an approximation whose accuracy increases with the size of the text. It would in practice be necessary to try various key lengths close to the estimate.<ref>{{cite book |editor=Henk C.A. van Tilborg |title=Encyclopedia of Cryptography and Security |publisher=Springer |edition=First |isbn=0-387-23473-X |pages=115 |year=2005}}</ref> A better approach for repeating-key ciphers is to copy the ciphertext into rows of a matrix having as many columns as an assumed key length, then compute the average [[Index of coincidence#Example|index of coincidence]] with each column considered separately; when this is done for each possible key length, the highest average I.C. then corresponds to the most likely key length.<ref>{{cite journal | author=Mountjoy, Marjorie | title= The Bar Statistics | journal=NSA Technical Journal | year=1963 | volume=VII | issue=2,4}} Published in two parts.</ref> Such tests may be supplemented by information from the Kasiski examination. |
|||
===Frequency analysis=== |
|||
Once the length of the key is known, the ciphertext can be rewritten into that many columns, with each column corresponding to a single letter of the key. Each column consists of plaintext that has been encrypted by a single [[Caesar cipher]]; the Caesar key (shift) is just the letter of the Vigenère key that was used for that column. Using methods similar to those used to break the Caesar cipher, the letters in the ciphertext can be discovered. |
|||
An improvement to the Kasiski examination, known as [[Auguste Kerckhoffs|Kerckhoffs]]' method, matches each column's letter frequencies to shifted plaintext frequencies to discover the key letter (Caesar shift) for that column. Once every letter in the key is known, the cryptanalyst can simply decrypt the ciphertext and reveal the plaintext.<ref>{{cite web |url=http://courses.umass.edu/cs415/labs/lab1/415-lab1-crypto.pdf |title=Lab exercise: Vigenere, RSA, DES, and Authentication Protocols |accessdate=2006-11-10 |format=PDF |work=CS 415: Computer and Network Security }}</ref> Kerckhoffs' method is not applicable when the Vigenère table has been scrambled, rather than using normal alphabetic sequences, although Kasiski examination and coincidence tests can still be used to determine key length in that case. |
|||
===Key Elimination=== |
|||
The Vigenère cipher function is essentially modulo arithmetic, and thus commutative. So if the key length is known (or guessed) then subtracting the cipher text from itself, offset by the key length will produce the cipher text encrypted with itself. If any words in the cipher text are known or can be guessed at then the plain text and hence the key will be revealed. This is useful if the key is an obscure sequence of letters because the plain text will generally be ordinary words. |
|||
==Variants== |
|||
The [[running key cipher|running key]] variant of the Vigenère cipher was also considered unbreakable at one time. This version uses as the key a block of text as long as the plaintext. Since the key is as long as the message the Friedman and Kasiski 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 Vigenère cipher is that the cryptanalyst has statistical information about the key (assuming that the block of text is in a known language) and that information will be reflected in the ciphertext. |
|||
If using a key which is truly random, is at least as long as the encrypted message and is used only once, the Vigenère cipher is theoretically unbreakable. However, in this case it is the key, not the cipher, which provides cryptographic strength and such systems are properly referred to collectively as [[one time pad]] systems, irrespective of which ciphers are employed. |
|||
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 [[Gronsveld|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. |
|||
==References== |
|||
{{reflist}} |
|||
==Sources== |
|||
*{{cite book|first=Albrecht|last=Beutelspacher|year=1994|title=Cryptology|chapter=Chapter 2|editor=|others=translation from German by J. Chris Fisher|pages=27–41|publisher=Mathematical Association of America|isbn=0-88385-504-6|location=Washington, DC}} |
|||
*{{cite book|first=Simon|last=Singh|year=1999|title=The Code Book|chapter=Chapter 2: Le Chiffre Indéchiffrable|editor=|pages=|publisher=Anchor Book, [[Random House]]|isbn=0-385-49532-3}} |
|||
*{{cite book|first=Helen Fouche|last=Gaines|year=1939|title=Cryptanalysis a Study of Ciphers and Their Solutions|chapter=The Gronsfeld, Porta and Beaufort Ciphers|editor=|pages=117–126|publisher=[[Dover Publications]]|isbn=0486200973}} |
|||
Mendelsohn, Charles J. (1940). "Blaise De Vigenere and The "Chiffre Carre"," ''Proceedings of the American Philosophical Society'' 82, no. 2 |
|||
==See also== |
|||
* [[Caesar cipher]] |
|||
* [[Roger Frontenac]] ([[Nostradamus]] quatrain decryptor, [[1950]]) |
|||
==External links== |
|||
===Articles=== |
|||
* [http://home.att.net/~tleary/cryptolo.htm History of the cipher from Cryptologia] |
|||
* [http://www.bbc.co.uk/dna/h2g2/alabaster/A613135 Basic Cryptanalysis] at H2G2 |
|||
* [http://www-math.cudenver.edu/~wcherowi/courses/m5410/m5410cc.html Lecture Notes on Classical Cryptology including an explanation and derivation of the Friedman Test] |
|||
* [http://www.simonsingh.net/The_Black_Chamber/cracking_tool.html Online Vigenère Cracking Tool] |
|||
===Programming=== |
|||
* [http://sharkysoft.com/misc/vigenere/ Sharky's Online Vigenere Cipher] — Encode and decode messages, using a known key, within a Web browser ([[JavaScript]]) |
|||
* [http://smurfoncrack.com/pygenere/ PyGenere: an online tool for automatically deciphering Vigenère-encoded texts] (6 languages supported) |
|||
* [http://ljplawcom00.web707.discountasp.net/Vigenere/Vigenere.aspx/ Vigenère Cipher encryption and decryption program (browser version, English only)] |
|||
* [http://search.cpan.org/~alizta/Crypt-Vigenere-0.07/Vigenere.pm Crypt::Vigenere] — a [[CPAN]] module implementing the Vigenère cipher |
|||
* [http://www.dharmainitiative.it/index.php?id=test&n=3 Vigenère Encrypter] Encode messages using a keyword |
|||
* [http://www.perlmonks.org/?node_id=550450 Breaking the indecipherable cipher: Perl code to decipher Vigenère text, with the source in the shape of Babbage's head] |
|||
* [http://buchananweb.co.uk/security27.aspx Random Vigenère Challenges] |
|||
* [http://papacharliefox3.wordpress.com/2009/04/02/desafio-de-crypto-ii-cifra-de-vigenere/ Vigenère in BASH] |
|||
* [http://faruk.akgul.org/blog/entry/the-vigene-cipher Vigenère Cipher] - Source code in Java ([[GNU General Public License|GNU GPLv3]]) |
|||
* [http://www.vigenere.tk Java Vigenere] applet with source code ([[GNU General Public License|GNU GPL]]) |
|||
* [http://log.flirt-wind.net/2010/08/vigenere-cipher-in-java/ Vigenere Cipher in Java] |
|||
{{Crypto navbox | classical}} |
|||
{{DEFAULTSORT:Vigenere Cipher}} |
|||
[[Category:Classical ciphers]] |
|||
[[Category:Stream ciphers]] |
|||
[[ca:Xifratge de Vigenère]] |
|||
[[cs:Vigenèrova šifra]] |
|||
[[es:Cifrado de Vigenère]] |
|||
[[fr:Chiffre de Vigenère]] |
|||
[[hr:Vigenèreova šifra]] |
|||
[[id:Sandi Vigenère]] |
|||
[[it:Cifrario di Vigenère]] |
|||
[[he:צופן ויז'נר]] |
|||
[[hu:Vigenère-rejtjel]] |
|||
[[nl:Vigenèrecijfer]] |
|||
[[ja:ヴィジュネル暗号]] |
|||
[[no:Vignerechifferet]] |
|||
[[pl:Szyfr Vigenère'a]] |
|||
[[pt:Cifra de Vigenère]] |
|||
[[ru:Шифр Виженера]] |
|||
[[sr:Вижнерова шифра]] |
|||
[[sv:Vigenère-chiffret]] |
|||
[[tr:Vigenere tablosu]] |
|||
[[uk:Шифр Віженера]] |
|||
[[zh:维吉尼亚密码]] |
|||
Revision as of 20:21, 3 December 2010
I'm editing this page, so I've taken it down for a while. I promise it'll be back in a few minutes, so Admins please don't take disciplinary action! --Nmatavka (talk)