Vigenère Polyalphabetic Cipher
The Vigenère Cipher is one of the truly great breakthroughs in the development of cryptography, much stronger than other ciphers that preceded it. The birth of the cipher can be traced back to the work of Leon Alberti. Born in 1404, Alberti was one the leading figures of the Renaissance; a painter, composer, poet and philosopher.
He is probably best known as an architect, having designed Rome's first Trevi Fountain and having written 'De Re Aedificatoria", the first printed book on architecture, which acted as a catalyst for the transition from Gothic to Renaissance design.
Sometime in the 1460's, Alberti had a conversation with Leonardo Dato, the Pope's secretary, about some of the finer points of cryptography. This prompted Alberti to write an essay on the subject, outlining what he believed to be a new form of cipher. Up until this point, a substitution cipher involved establishing a single cipher alphabet for encrypting each message. However, Alberti proposed using two or more cipher alphabets and switching between them during encipherment, thereby confusing potential cryptanalysts.
Although he had hit upon the most significant breakthrough in encryption for over one thousand years, he failed to develop his concept into a fully formed system of encryption.
Blaise de Vigenère, a French diplomat, became acquainted with the writings of Alberti when he was sent to Rome on a two-year diplomatic mission in 1549. Initially, his interest in cryptography was purely practical and was linked to his diplomatic work. Then, at the age of 39 in 1565, Vigenère decided that he had accumulated enough money to be able to abandon his career and concentrate on a life of study. It was only then that his powerful new cipher reached its final form.
The cipher Alberti shared in his writings used 2 or at most 3 cipher alphabets. However, the Vigenère cipher uses 26 cipher alphabets! The 26 cipher alphabets are contained in the Vigenère Square, shown below, which has a plaintext alphabet followed by 26 cipher alphabets, each one shifted by one more letter with respect to the previous one. Hence, row number 1 represents a cipher alphabet with a Caesar shift of 1, row number 2 represents a cipher alphabet with a Caesar shift of 2, and so on.
A different column of the square can be used to encrypt each letter of the message. In other words, the sender might encrypt the first letter according to column E, the second according to column M, and the third letter according to column U, and so on. In order to unscramble the message, it is important that the intended receiver knows which column of the Vigenère Square has been used to encipher each letter, and so there must be an agreed system of switching between columns. This agreement is achieved via a keyword.
A different column of the square can be used to encrypt each letter of the message. In other words, the sender might encrypt the first letter according to column E, the second according to column M, and the third letter according to column U, and so on. In order to unscramble the message, it is important that the intended receiver knows which column of the Vigenère Square has been used to encipher each letter, and so there must be an agreed system of switching between columns. This agreement is achieved via a keyword.
- The plaintext is written out;
- The keyword is written above the plaintext in letter-to-letter correspondence, with the keyword repeated as many times as needed to match the plaintext length;
- The cryptographer uses the column of the keyword letter and the row of the plaintext letter to find the ciphertext;
- The cryptographer can then send the message to the intended recipient, who knows the keyword by prior arrangement and can decrypt the message.
The strength of the Vigenère Cipher is that the same letter can be encrypted in different ways.
For example, if the keyword is KING, then every plaintext letter can be encrypted in 4 ways, because the keyword contains 4 letters. Each letter of the keyword defines a different cipher alphabet in the Vigenère Square. Longer keywords with more unique letters make the cryptanalyst's task more difficult; by the time they have broken the cipher and read the message, the information may no longer need to be protected.
At first glance the Vigenère Cipher appears to be unbreakable, due to its use of up to 26 different cipher alphabets. Ciphers like this, which use more than one cipher alphabet are known as polyalphabetic (multiple alphabet) ciphers. These can be incredibly difficult to decipher, because of their resistance to the frequency analysis that makes vulnerable Caesar ciphers. Indeed, over time, the Vigenère cipher became known as "Le Chiffre Undechiffrable," or "The Unbreakable Cipher."
It wasn't until 1854, about two hundred years later, that the Vigenère Cipher was finally cracked independently by Polish Major Friedrich Kasiski and British cryptographer Charles Babbage. Both realized that looking for repeated sets or "runs" of letter patterns in the stream of ciphertext would give a fair idea of the length of the keyword setting for the message. If the cryptanalyst knows the target language and often-used phrases in the context of the likely subject of the message then the same approach to the Caesar cipher can work, made more difficult, but not impossible, by the added degree of difficulty of multiple Caesar ciphers.
Vigenère Ciphers Resources Online
Kasiski Analysis
http://pages.mtu.edu/~shene/NSF-4/Tutorial/VIG/Vig-Kasiski.html
Charles Babbage, computer pioneer
