The Code Book (13 page)

Mr. Babbage Versus the Vigenère Cipher

The most intriguing figure in nineteenth-century cryptanalysis is Charles Babbage, the eccentric British genius best known for developing the blueprint for the modern computer. He was born in 1791, the son of Benjamin Babbage, a wealthy London banker. When Charles married without his father’s permission, he no longer had access to the Babbage fortune, but he still had enough money to be financially secure, and he pursued the life of a roving scholar, applying his mind to whatever problem tickled his fancy. His inventions include the speedometer and the cowcatcher, a device that could be fixed to the front of steam locomotives to clear cattle from railway tracks. In terms of scientific breakthroughs, he was the first to realize that the width of a tree ring depended on that year’s weather, and he deduced that it was possible to determine past climates by studying ancient trees. He was also intrigued by statistics, and as a diversion he drew up a set of mortality tables, a basic tool for today’s insurance industry.

Babbage did not restrict himself to tackling scientific and engineering problems. The cost of sending a letter used to depend on the distance the letter had to travel, but Babbage pointed out that the cost of the labor required to calculate the price for each letter was more than the cost of the postage. Instead, he proposed the system we still use today—a single price for all letters, regardless of where in the country the addressee lives. He was also interested in politics and social issues, and toward the end of his life he began a campaign to get rid of the organ grinders and street musicians who roamed London. He complained that the music “not infrequently gives rise to a dance by little ragged urchins, and sometimes half-intoxicated men, who occasionally accompany the noise with their own discordant voices. Another class who are great supporters of street music consists of ladies of elastic virtue and cosmopolitan tendencies, to whom it affords a decent excuse for displaying their fascinations at their open windows.” Unfortunately for Babbage, the musicians fought back by gathering in large groups around his house and playing as loud as possible.

The turning point in Babbage’s scientific career came in 1821, when he and the astronomer John Herschel were examining a set of mathematical tables, the sort used as the basis for astronomical, engineering and navigational calculations. The two men were disgusted by the number of errors in the tables, which in turn would generate flaws in important calculations. One set of tables, the
Nautical Ephemeris for Finding Latitude and Longitude at Sea
, contained over a thousand errors. Indeed, many shipwrecks and engineering disasters were blamed on faulty tables.

These mathematical tables were calculated by hand, and the mistakes were simply the result of human error. This caused Babbage to exclaim, “I wish to God these calculations had been executed by steam!” This marked the beginning of an extraordinary endeavor to build a machine capable of faultlessly calculating the tables to a high degree of accuracy. In 1823 Babbage designed “Difference Engine No. 1,” a magnificent calculator consisting of 25,000 precision parts, to be built with government funding. Although Babbage was a brilliant innovator, he was not a great implementer. After ten years of toil, he abandoned “Difference Engine No. 1,” cooked up an entirely new design, and set to work building “Difference Engine No. 2.”

When Babbage abandoned his first machine, the government lost confidence in him and decided to cut its losses by withdrawing from the project—it had already spent £17,470, enough to build a pair of battleships. It was probably this withdrawal of support that later prompted Babbage to make the following complaint: “Propose to an Englishman any principle, or any instrument, however admirable, and you will observe that the whole effort of the English mind is directed to find a difficulty, a defect, or an impossibility in it. If you speak to him of a machine for peeling a potato, he will pronounce it impossible: if you peel a potato with it before his eyes, he will declare it useless, because it will not slice a pineapple.”

Lack of government funding meant that Babbage never completed Difference Engine No. 2. The scientific tragedy was that Babbage’s machine would have been a stepping-stone to the Analytical Engine, which would have been programmable. Rather than merely calculating a specific set of tables, the Analytical Engine would have been able to solve a variety of mathematical problems depending on the instructions that it was given. In fact, the Analytical Engine provided the template for modern computers. The design included a “store” (memory) and a “mill” (processor), which would allow it to make decisions and repeat instructions, which are equivalent to the
“IF
 … 
THEN
 …” and
“LOOP”
commands in modern programming.

Figure 12
Charles Babbage. (
photo credit 2.2
)

A century later, during the course of the Second World War, the first electronic incarnations of Babbage’s machine would have a profound effect on cryptanalysis, but, in his own lifetime, Babbage made an equally important contribution to codebreaking: he succeeded in breaking the Vigenère cipher, and in so doing he made the greatest breakthrough in cryptanalysis since the Arab scholars of the ninth century broke the monoalphabetic cipher by inventing frequency analysis. Babbage’s work required no mechanical calculations or complex computations. Instead, he employed nothing more than sheer cunning.

Babbage had become interested in ciphers at a very young age. In later life, he recalled how his childhood hobby occasionally got him into trouble: “The bigger boys made ciphers, but if I got hold of a few words, I usually found out the key. The consequence of this ingenuity was occasionally painful: the owners of the detected ciphers sometimes thrashed me, though the fault lay in their own stupidity.” These beatings did not discourage him, and he continued to be enchanted by cryptanalysis. He wrote in his autobiography that “deciphering is, in my opinion, one of the most fascinating of arts.”

He soon gained a reputation within London society as a cryptanalyst prepared to tackle any encrypted message, and strangers would approach him with all sorts of problems. For example, Babbage helped a desperate biographer attempting to decipher the shorthand notes of John Flamsteed, England’s first Astronomer Royal. He also came to the rescue of a historian, solving a cipher of Henrietta Maria, wife of Charles I. In 1854, he collaborated with a barrister and used cryptanalysis to reveal crucial evidence in a legal case. Over the years, he accumulated a thick file of encrypted messages, which he planned to use as the basis for an authoritative book on cryptanalysis, entitled
The Philosophy of Decyphering
. The book would contain two examples of every kind of cipher, one that would be broken as a demonstration and one that would be left as an exercise for the reader. Unfortunately, as with many other of his grand plans, the book was never completed.

While most cryptanalysts had given up all hope of ever breaking the Vigenère cipher, Babbage was inspired to attempt a decipherment by an exchange of letters with John Hall Brock Thwaites, a dentist from Bristol with a rather innocent view of ciphers. In 1854, Thwaites claimed to have invented a new cipher, which, in fact, was equivalent to the Vigenère cipher. He wrote to the
Journal of the Society of Arts
with the intention of patenting his idea, apparently unaware that he was several centuries too late. Babbage wrote to the Society, pointing out that “the cypher … is a very old one, and to be found in most books.” Thwaite was unapologetic and challenged Babbage to break his cipher. Whether or not it was breakable was irrelevant to whether or not it was new, but Babbage’s curiosity was sufficiently aroused for him to embark on a search for a weakness in the Vigenère cipher.

Cracking a difficult cipher is akin to climbing a sheer cliff face. The cryptanalyst is seeking any nook or cranny which could provide the slightest purchase. In a monoalphabetic cipher the cryptanalyst will latch on to the frequency of the letters, because the commonest letters, such as e, t and a, will stand out no matter how they have been disguised. In the polyalphabetic Vigenère cipher the frequencies are much more balanced, because the keyword is used to switch between cipher alphabets. Hence, at first sight, the rock face seems perfectly smooth.

Remember, the great strength of the Vigenère cipher is that the same letter will be enciphered in different ways. For example, if the keyword is KING, then every letter in the plaintext can potentially be enciphered in four different ways, because the keyword contains four letters. Each letter of the keyword defines a different cipher alphabet in the Vigenère square, as shown in
Table 7
. The e column of the square has been highlighted to show how it is enciphered differently, depending on which letter of the keyword is defining the encipherment:

If the K of KING is used to encipher e, then the resulting ciphertext letter is O.

If the I of KING is used to encipher e, then the resulting ciphertext letter is M.

If the N of KING is used to encipher e, then the resulting ciphertext letter is R.

If the G of KING is used to encipher e, then the resulting ciphertext letter is K.

Table 7
A Vigenère square used in combination with the keyword KING. The keyword defines four separate cipher alphabets, so that the letter e may be encrypted as O, M, R or K.

Similarly, whole words will be deciphered in different ways: the word the, for example, could be enciphered as DPR, BUK, GNO or ZRM, depending on its position relative to the keyword. Although this makes cryptanalysis difficult, it is not impossible. The important point to note is that if there are only four ways to encipher the word the, and the original message contains several instances of the word the, then it is highly likely that some of the four possible encipherments will be repeated in the ciphertext. This is demonstrated in the following example, in which the line The Sun and the Man in the Moon has been enciphered using the Vigenère cipher and the keyword KING.

The word the is enciphered as DPR in the first instance, and then as BUK on the second and third occasions. The reason for the repetition of BUK is that the second the is displaced by eight letters with respect to the third the, and eight is a multiple of the length of the keyword, which is four letters long. In other words, the second the was enciphered according to its relationship to the keyword (the is directly below ING), and by the time we reach the third the, the keyword has cycled around exactly twice, to repeat the relationship, and hence repeat the encipherment.

Babbage realized that this sort of repetition provided him with exactly the foothold he needed in order to conquer the Vigenère cipher. He was able to define a series of relatively simple steps which could be followed by any cryptanalyst to crack the hitherto
chiffre indéchiffrable
. To demonstrate his brilliant technique, let us imagine that we have intercepted the ciphertext shown in
Figure 13
. We know that it was enciphered using the Vigenère cipher, but we know nothing about the original message, and the keyword is a mystery.