Wednesday, April 05, 2006

The Vigenère Cipher


Cryptographer Blaise de Vigenère was born on this day in 1523 in Sainte-Pourcain, France.

Vigenère was a French diplomat who began his career at 17 as a junior secretary. While in Rome during his 20s, he came into contact with the cryptoanalytical theory of Leonbattista Alberti -- the Italian polymath whose best known works included the first scientific study of perspective (De pictura, 1435 -- a work that had a profound influence upon Italian painters during the early Renaissance in Florence) and the design for the facade of the church of Santa Maria Novella in Florence (1456-70).

Prior to Alberti, the most common form of cipher was the Caesar Shift, by which the person encoding a message chose a letter of the alphabet to represent 'A,' and shifted all the letters in a message ahead by their relation to that original letter (i.e., if 'T' were to stand for 'A,' then 'U' would stand for 'B,' 'V' would stand for 'C,' and so on). As codebreakers of the time were aware, however, all you had to do to break something encoded using the Caesar Shift would be to try out 26 different alphabets; eventually, you could figure out the message.

The Caesar Shift is known as a monoalphabetic substitution code, since only one shift was employed throughout the entire message. Alberti proposed, rather casually after a conversation with an Italian diplomat, that more than one shift be employed in the encoding of messages -- that a polyalphabetic substitution scheme be used.

Vigenère systematized Alberti's suggestion in his treatise, Traicte de Chiffres, published in 1585 after he retired from diplomatic service. As many sources now observe, an Italian cryptoanalyst named Giovanbattista Belaso actually beat Vigenère to the punch, publishing his own polyalphabetic cipher system in 1553, but the world tends to think of Vigenère as the inventor of the system, so that the code is now universally referred to as the Vigenère cipher. Vigenère died of throat cancer on February 19, 1596 in Paris, a relatively wealthy man and a respected scholar.

The principal way in which the Vigenère cipher differs from the Caesar Shift is that the sender and receiver both would have in their possession a "key" that would unlock the various shifts employed. If the key were a word, such as the word "RIPE," then it would be employed as follows: for the first letter of the message, the shift would be such that 'R' stood for 'A' and all other letters would shift accordingly; for the second letter of the message, the shift would be such that 'I' stood for 'A' and all other letters would shift accordingly, and so on -- with the sequence 'R,' then 'I,' then 'P,' then 'E' repeating itself throughout the message. Although this cipher system is not foolproof -- it can be solved through frequency analysis, without having access to the key -- it certainly made it much more difficult for a casual codebreaker to stumble upon the meaning of a coded message.

As an illustration of how the Vigenère cipher works, the following is a message encoded through the use of a relatively simple Vigenère scheme:

BXZZNYFRDKOKAORRBUEJEOBOSOXBJZNEKYOOMCHGSMOR
OJMNGDRAZPMKIJDWVRFYTPQGOVBAJEJRYETKXMWTQAYG
TKJPZNWWIALDPGPUALGKWAUQKQWPJVGWZWSIFNCWAYEE
CWTAIBDSVSWOMJQCNNLBVPDLUVXSGYCUUGQDLZEHLTNK
RBFIJQQTBFEQKGFQJCQNWTQVQNWDUTRWPSQQYFHFJACD
EDIHQKNGVARAPHWVZZYZIYLIXJKFUGSUWNMUXXUUSZLY
YMNJARYDYOOLGGDNGUFSYETGJPKYJKBDBILNKBXINLXX
HUBDHIKAPRWYWGHDWVBIKEVYZZRGPMNALXXHLIAEINWB
AIMYWZBNFIZLMIONWGWIOPYVUPHXQRPWHGXGCYXGDUCY
ILCBGXFUIYEJVWOBUJOPSBGGKYFNHESPACXHMTITWWGJ
JRWUXGODZLBLYXDFOZSEHLJUOSYLSNBARWNTDKFIEXNY
LGNXQVSTXSYSZZVMGRPNQWMQTARNSJSKZXQEXWPUCJWO
HALAMSIPXIWOPJWYMNUKSGCJJFPCWGLWDDGNRYDEWBKC
SGKDGOZSSWWQHUICJXXDKXFHDUNFWHIMXDAWPMMIUFTD
CTPPHHF

It is eminently solvable. The first person to send the correct answer to BVSquares-at-yahoo.com will receive my autograph on that crude, silly caricature of Vigenère seen above.

Some clues:

1. The layout of the message employs a graphic trick that should be easy to figure out -- in other words, the letters in the message do not read horizontally left to right.

2. There are a number of decoy letters; however, once you figure out the graphic trick, the message will appear as a string of consecutive letters.

3. For Vigenère enthusiasts, it will be important for you to know that A=1 as opposed to zero, and that blank spaces are filtered out.

4. Finally, the key is an English language word that has not appeared on this blog, either in this post or in any post prior to today's.

Send your solution and your mailing address to the email above -- and good luck! This post will be updated once some semi-clever person comes up with the correct solution.

UPDATE: 5/01/06

I am surprised to report that no one has even ventured a guess on this one, although this little puzzle has been visited by numerous contestants. A special 'hello' to all my friends in Slovakia and the Czech Republic who have come here in search of code to break, as well as to my one loyal Vigenèrean from Brazil. Good fortune to you all!

UPDATE: 6/28/12

All contests must come to an end, and so must this one.  No winners!

Labels:

1 Comments:

Anonymous Anonymous said...

Can you describe "graphic trick"? I know how to solve it but without "graphic trick" (sorry my english - i am from Slovakia...)

2:13 PM  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home