Codebreaker

"One day ladies will take their computers for walks in the park and tell each other, 'My little computer said such a funny thing this morning.'" -- Alan Turing.

Mathematician and code-breaker Alan Turing was born on this day in 1912 in London. A brilliant youth who was neglected by his parents, Alan Turing was shy and socially-awkward, despite being a gifted athlete as well as a math whiz. At boarding school he developed a deep friendship with a schoolmate, Christopher Morcom, whose death when Turing was 18 left Turing devastated. Both before and after Morcom's death, it appears that Turing was confused about his own sexuality, although in later years, while he made occasional comments about having children and settling down, he was thought to have been exclusively homosexual.

In 1931, Turing entered King's College, Cambridge and found it rocked by a debate over the limits of mathematical analysis in reaction to the concept of "undecidables" put forward by Kurt Godel, who proved that there were some mathematical problems that were beyond the reach of logic. At 25, Turing imposed his indelible stamp on the debate -- and the history of computer science -- with a paper entitled "On Computable Numbers," in which he described an imaginary machine that would be capable of answering any mathematical question which could be logically answered through algorithms. Turing observed that such a machine (which he dubbed the "Universal Turing Machine"), though universal in its ability to apply mathematical logic to a problem, would be incapable of deciding whether a question was "undecidable," thus supporting Godel's view.

More interesting to computer historians, however, was that Turing's conceptualization of the Universal Turing Machine was a theoretical blueprint for the modern programmable computer. Before anything could be made of the idea, World War II had begun and Turing was invited to join the secret group of British cryptanalysts at Bletchley Park, where he led the British government's attempts to break German codes scrambled by Arthur Scherbius' Enigma scrambling machine by conceptualizing the descrambling approach and stringing together multiple descramblers. In conducting the war, Winston Churchill came to rely heavily on Turing's work, and even increased funding to the project based on a direct request from Turing himself.

After the war, Turing worked with the British National Physical Laboratory and at the University of Manchester to attempt to build a prototype of the Universal Turing Machine. A proponent of artificial intelligence, Turing unveiled his now famous "Turing test" in 1950, whereby a subject would be locked in a room to pose questions to 2 unseen answer providers, one human, one computer; if the subject was not able to tell which was the human and which was the computer by the content of the answers, then according to Turing the machine would be said to be "thinking" as well as the human.

In 1952 he admitted to police that he was having a homosexual affair, and was convicted of "gross indecency." Subjected to female hormones as "therapy" for curbing homosexual lust, Turing grew depressed and committed suicide on June 7, 1954 in Wilmslow, Cheshire, England by eating a cyanide-poisoned apple (he had been an avid fan of Disney's Snow White and the Seven Dwarfs) at the age of 41. His role in cracking the Enigma code would not be revealed until the 1970s.

Also an accomplished marathon runner, during the 1940s, Turing was unofficially one of Britain's finest, achieving a personal-best time of 2:46:3, only about 11 minutes behind Delfo Cabrera's 1948 Olympic gold-medal winning time of 2:34:51.6.

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!