Vigenère cipher

The Vigenère cipher (French pronunciation: [viʒnɛːʁ]) is a method of encrypting alphabetic text where each letter of the plaintext is encoded with a different Caesar cipher, whose increment is determined by the corresponding letter of another text, the key.

For example, if the plaintext is attacking tonight and the key is oculorhinolaryngology, then and so on; yielding the message ovnlqbpvt eoegtnh.

If the recipient of the message knows the key, they can recover the plaintext by reversing this process.

[1][2] First described by Giovan Battista Bellaso in 1553, the cipher is easy to understand and implement, but it resisted all attempts to break it until 1863, three centuries later.

This earned it the description le chiffrage indéchiffrable (French for 'the indecipherable cipher').

[3] In 1863, Friedrich Kasiski was the first to publish a general method of deciphering Vigenère ciphers.

In the 19th century, the scheme was misattributed to Blaise de Vigenère (1523–1596) and so acquired its present name.

Later, Johannes Trithemius, in his work Polygraphia (which was completed in manuscript form in 1508 but first published in 1518),[5] invented the tabula recta, a critical component of the Vigenère cipher.

[8] He built upon the tabula recta of Trithemius but added a repeating "countersign" (a key) to switch cipher alphabets every letter.

In the 19th century, the invention of this cipher, essentially designed by Bellaso, was misattributed to Vigenère.

David Kahn, in his book, The Codebreakers lamented this misattribution, 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".

Charles Babbage is known to have broken a variant of the cipher as early as 1854 but did not publish his work.

[citation needed] 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": Each row starts with a key letter.

The rest of the plaintext is enciphered in a similar fashion: Decryption is performed by going to the row in the table corresponding to the key, finding the position of the ciphertext letter in that row and then using the column's label as the plaintext.

For example, in row L (from LEMON), the ciphertext L appears in column A, so a is the first plaintext letter.

However, by using the Vigenère cipher, e can be enciphered as different ciphertext letters at different points in the message, which defeats simple frequency analysis.

In 1863, Friedrich Kasiski was the first to publish a successful general attack on the Vigenère cipher.

[17] Earlier attacks relied on knowledge of the plaintext or the use of a recognizable word as a key.

For example, consider the following encryption using the keyword ABCD: There is an easily noticed repetition in the ciphertext, and so the Kasiski test will be effective.

Longer messages make the test more accurate because they usually contain more repeated ciphertext segments.

By taking the intersection of those sets, one could safely conclude that the most likely key length is 6 since 3, 2, and 1 are unrealistically short.

(1⁄26 = 0.0385 for English), the key length can be estimated as the following: from the observed coincidence rate in which c is the size of the alphabet (26 for English), N is the length of the text and n1 to nc are the observed ciphertext letter frequencies, as integers.

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 Kerckhoffs' method, matches each column's letter frequencies to shifted plaintext frequencies to discover the key letter (Caesar shift) for that column.

[24] Kerckhoffs' method is not applicable if the Vigenère table has been scrambled, rather than using normal alphabetic sequences, but Kasiski examination and coincidence tests can still be used to determine key length.

The Vigenère cipher, with normal alphabets, essentially uses modulo arithmetic, which is commutative.

The running key variant of the Vigenère cipher was also considered unbreakable at one time.

This is demonstrated by encrypting attackatdawn with IOZQGH, to produce the same ciphertext as in the original example.

If one uses a key that is truly random, is at least as long as the encrypted message, and is used only once, the Vigenère cipher is theoretically unbreakable.

The Gronsfeld cipher is a variant attributed by Gaspar Schott to Count Gronsfeld (Josse Maximilaan van Gronsveld né van Bronckhorst) but was actually used much earlier by an ambassador of Duke of Mantua in 1560s-1570s.