Once you have this information, you can split the ciphertext into four groups. The first group consists of the first letter, fifth letter, ninth letter, and so on. The second group consists of the second letter, sixth letter, tenth letter, and so on. The same substitution cipher will have been used to encode the letters in any one of these four groups, so you can now use frequency analysis on each group in turn, and the code is cracked.
As soon as the Vigenére code was broken, the search was on for a new way to encode messages securely. When the Enigma machine was developed in Germany in the 1920s, many people believed that the ultimate uncrackable code had been created.
The Enigma machine works on the principle of changing the substitution cipher each time a letter is encoded. If I want to encode the sequence aaaaaa (to indicate perhaps that I’m in pain), then each a will get encoded in a different way. The beauty of the Enigma machine was that it mechanized the change from one substitution to the next very efficiently. The message is typed on a keyboard. There is a second bank of letters—the “light board” above the keyboard—and when a key is pressed on the keyboard, one of the letters above lights up to indicate the encoded letter. But the keyboard isn’t wired directly to the light board: the connections are via three disks that contain a maze of wiring and can be rotated.
One way to understand how an Enigma machine works is to imagine a large cylinder consisting of three rotating drums. At the top of the cylinder are 26 holes around the rim, labeled with the letters of the alphabet. To encode a letter, you drop a ball into the hole corresponding to that letter. The ball drops into the first drum, which has 26 holes around the rim at the top and 26 holes around the rim at the bottom. Tubes connect the upper and lower holes—but they don’t simply connect the holes at the top to the holes directly below them. Instead, the tubes twist and turn, so that a ball entering the drum at the top will pop out of a hole at the bottom in a completely different location. The middle and lower drums are similar, but their connecting tubes link the holes at the top with the holes at the bottom in different ways. When the ball drops out of a hole at the bottom of the third drum, it enters the last piece of the contraption and emerges from one of 26 holes at the bottom of the cylinder, each of which is, again, labeled with the letters of the alphabet.
Figure 4.2 The principle behind the Enigma machine: drop a ball through the tubes to encode a letter. The cylinders rotate after each encoding, so the letters are scrambled differently each time.
Now, if our contraption just stayed as it was, it would be nothing more than a complicated way of reproducing a substitution cipher. But here’s the genius of the Enigma machine: every time a ball drops through our cylinder, the first drum rotates by th of a turn. So when the next ball is dropped through, the first drum will send it on a completely different route. For example, while the letter a might first be encoded by the letter C, once the first drum moves on one step, a ball dropped in the letter a hole will emerge from a different hole at the bottom. And so it was with the Enigma machine: after the first letter had been encoded, the first rotating disk clicked around by one position.
The rotating disks work a bit like an odometer: once the first disk has clicked around through all 26 positions, as it returns to its starting position, it moves the second disk on by th of a turn. So in all, there are 26 × 26 × 26 different ways to scramble the letters. Not only that, but the Enigma operator could also alter the order of the disks, multiplying the number of possible substitution ciphers by a factor of 6 (corresponding to the 3! different ways of arranging the three disks).
Each operator had a codebook that described how, at the start of each day, the three disks should be arranged to encode messages. The recipient would decode the message with the same setting from the codebook. More complexities were introduced into the way the Enigma machine was constructed, and there were ultimately over 158 million million million different ways to set up the machine.
In 1931, the French government discovered the plans for the German machine, and they were horrified. There seemed to be no possible way to work out from an intercepted message how the disks were set up for each day’s encoding—which was crucial if a message was to be decoded. But they had a pact with the Poles to exchange any intelligence that was gathered, and the threat of German invasion had the effect of concentrating Polish minds.
Mathematicians in Poland realized that each setting of the disks had its own particular features, and that patterns could be exploited to help work backward and crack encrypted messages. If the operator typed an a, for example, it would be encoded according to how the disks were set—let’s say as D. The first disk then clicks on one step. If, when another a is typed, it’s encoded as Z, then in some sense, D is related to Z by the way the disks have been set.
We could investigate this using our contraption. By resetting the drums and dropping balls twice through each letter in turn, we would build up a complete set of relationships that might look like this:
Table 4.3
Each letter appears once and once only in each row because each row corresponds to a single substitution cipher.
How did the Poles use these relationships? On any given day, all the German Enigma operators would be using the same setting for the wheels, which they would find in their codebook. They would then choose their own setting, which they would then send using the original setting from the codebook. To be on the safe side, they were encouraged to repeat their choice by typing it twice. Far from being safe, this turned out to be a fatal mistake. It gave the Poles a hint about how the wheels connected the letters—a clue as to how the Enigma machine was set up for that day.
A group of mathematicians based in a country house at Bletchley Park, halfway between Oxford and Cambridge, studied the patterns that the mathematicians in Poland had spotted and found a way to automate the search for the settings using a machine they built that was known as a bombe. It’s been said that those mathematicians shortened the Second World War by two years, saving countless lives. And the machines they built ultimately gave birth to the computers we all rely on today.
For an online simulation of the Enigma machine, check out www.bletchleypark.org.uk/content/enigmasim.rhtm, which you can access directly by scanning this code with your smartphone.
From the Number Mysteries website, you can download a PDF of instructions for making your own Enigma machine.
GETTING THE MESSAGE ACROSS
Whether your message is encoded or not, you still need to find a way to transmit it from one location to another. Many ancient cultures, from the ancient Chinese to the Native Americans, used smoke signals as a way of communicating over long distances. It’s said that the fires that were lit on the towers of the Great Wall of China could communicate a message for three hundred miles along the wall in a matter of hours.
Visual codes based on flags date back to 1684, when Robert Hooke, one of the most famous scientists of the seventeenth century, suggested the idea to the Royal Society in London. The invention of the telescope had made it possible to communicate visual signals over large distances, but Hooke was spurred on by something that has led to many new technological advances: war. The previous year, the city of Vienna had almost been captured by the Turkish army without the rest of Europe knowing. Suddenly, it was a matter of urgency to come up with a way of sending messages quickly over large distances.
Hooke proposed setting up a system of towers right across Europe. If one tower sent a message, it would be repeated by all the other towers within visual range—a two-dimensional version of the way messages were sent down the length of the Great Wall of China. The method of transmitting messages wasn’t very sophisticated: large characters would have to be hoisted aloft on ropes. Hooke’s proposal, however, was never implemented, and it was another hundred years before a similar idea was put into practice.
In 1791, the brothers Claude and Ignace Chappe built a system of towers to speed up the French Revolutionary government’s communications (tho
ugh one tower was attacked when mobs thought it was actually the Royalists who were communicating with each other). The idea came from a system that the brothers had used to send messages between dormitories at the strict school where they had boarded as children. They experimented with lots of different ways of sending messages visually, and in the end, they settled on wooden rods set at different angles, which the human eye could easily distinguish.
Figure 4.3 The Chappe brothers’ code was transmitted via hinged wooden arms.
The brothers developed a code based on a movable system of hinged wooden arms to denote different letters or common words. The main cross arm could be set at four different angles, while two smaller arms attached to the end of the cross arm had seven different settings, making it possible to communicate a total of 7 x 7 x 4 = 196 different symbols. Although part of the code was used for public communication, 92 of the symbols, combined in pairs, were used by the brothers for a secret code, representing 92 x 92 = 8,464 different words or phrases.
Figure 4.4 Letters and numbers as transmitted by the Chappe brothers’ communication system.
In their first test, on March 2, 1791, the Chappe brothers successfully sent the message “If you succeed, you will soon bask in glory” across a distance of ten miles. The government was sufficiently impressed with the brothers’ proposal that in four years, a system of towers and flags was constructed that stretched right across France. In 1794, one line of towers, covering a distance of 143 miles, successfully communicated the news that the French had captured the town of Condé-sur-l’Escaut from the Austrians less than an hour after it had happened. Unfortunately, success did not lead to the glory that very first message had predicted. Claude Chappe got so depressed when he was accused of plagiarizing existing telegraph designs that he ended up drowning himself in a well.
It was not long before flags began to replace wooden arms on the tops of towers, and flags were adopted by sailors for communicating at sea, since all they had to do was wave them from a position visible to other ships. Perhaps the most famous coded message to be sent between ships using flags was this one, sent at 11:45 on October 21, 1805:
Figure 4.5 Admiral Nelson’s famous message.
This was the message that Horatio Nelson hoisted on his flagship HMS Victory just before the British navy engaged in the decisive clash that won the Battle of Trafalgar. The navy was using a secret code developed by another admiral, Sir Home Popham. Codebooks were distributed to each of the ships in the navy and were lined with lead so that if the ship was taken, the codebook could be thrown overboard to stop the enemy from capturing the British secret cipher.
The code worked by using combinations of ten different flags in which each flag represented a different numeral from 0 to 9. The flags would be run up the mast of a ship three at a time, indicating a number from 000 to 999. The recipient of the message would then look in the codebook to see what word was encoded by that number. England was encoded by the number 253, and the word man by 471. Some words, such as duty, were not in the codebook and would need to be spelled out by flags reserved for individual letters. Originally, Nelson had wanted to send the message “England confides that every man will do his duty,” in the sense that England was confident, but the signal officer, Lieutenant John Pasco, couldn’t find the word confides in the codebook. Rather than spelling it out, he politely suggested to Nelson that maybe expects, which was in the book, was a better word.
The use of flags was overtaken by the development of telecommunications, but the modern system, using a flag held in each hand, is still learned by sailors today and is known as semaphore. There are eight different positions for each arm, making 8 x 8 = 64 possible different symbols.
Figure 4.6 Semaphore.
Nujv!
Figure 4.7
On the front cover of their album Help!, the Beatles are apparently using semaphore to announce the title. But though they are making semaphore signs, when you decode the message, it doesn’t read HELP but NUJV. Robert Freeman, who had the idea of using semaphore on the cover, explained that “when we came to do the shot, the arrangement of the arms with those letters didn’t look good. So we decided to improvise and ended up with the best graphic positioning of the arms.”
They should have been doing this:
Figure 4.8
The Beatles aren’t the only band to have used codes incorrectly on an album cover, as we shall see.
To see how a message translates into semaphore, check out http://inter.scoutnet.org/semaphore or scan this code with your smartphone.
Figure 4.9 Did you know that the peace symbol used by the Campaign for Nuclear Disarmament is actually semaphore? It represents the letters n and d combined into one symbol.
WHAT IS THE CODED MESSAGE IN BEETHOVEN’S FIFTH SYMPHONY?
Beethoven’s Fifth Symphony begins with one of the most famous openings in the history of music—three short notes followed by a long note. But why, during the Second World War, did the BBC start every radio broadcast of the news with Beethoven’s famous motif? The answer is that it contains a coded message. This new code exploited technology that could send signals through wires in a series of electromagnetic pulses.
One of the first to experiment with this form of communication was Carl Friedrich Gauss, whose work on prime numbers we looked at in chapter 1. As well as mathematics, he was also interested in physics, including the emerging field of electromagnetism. He and the physicist Wilhelm Weber rigged up a wire a kilometer in length running from Weber’s laboratory in Göttingen to the observatory where Gauss lived, and used it to send messages to each other.
To do this, they needed to develop a code. At each end of the wire, they set up a needle attached to a magnet that the wire was wrapped around. By changing the direction of the current, the magnet could be made to turn left or right. Gauss and Weber devised a code that turned letters into combinations of left and right turns:
Table 4.4
Weber was so excited by the potential of their discovery that he prophetically declared, “When the globe is covered with a net of railroads and telegraph wires, this net will render services comparable to those of the nervous system in the human body, partly as a means of transport, partly as a means for the propagation of ideas and sensations with the speed of light.”
Many different codes were suggested to fulfill the potential of electromagnetism to communicate messages, but the code developed by the American Samuel Morse in 1838 was so successful that it put all the others out of business. It was similar to Gauss and Weber’s scheme, converting each letter into a combination of long and short bursts of electricity: dashes and dots.
The logic on which Morse based his code is something like the frequency analysis used by code breakers to crack the substitution cipher. The most common letters in the English alphabet are e and t, so it makes sense to use the shortest possible sequence to encode them. So e is represented by a dot (a short burst of electricity), and t is represented by a dash (a long burst). The less common letters require longer sequences, so z, for example, is dash-dash-dot-dot.
Figure 4.10 Morse code.
With the aid of Morse code, we can now crack the message hidden in Beethoven’s Fifth. If we interpret the dramatic opening of the piece as Morse code, then dot-dot-dot-dash is Morse for the letter v, which the BBC used to symbolize victory.
Although Beethoven certainly didn’t intend to hide messages in Morse in his music, given that he died before it was invented, other composers have deliberately used rhythm to add an extra layer of meaning to their work. The music for the famous detective series Inspector Morse appropriately enough begins with a rhythm that spells out the detective’s name in Morse code:
Figure 4.11
In some of the episodes, the composer even threaded the name of the story’s killer in Morse during the incidental music accompanying the program, though red herrings sometimes found their way into the score.
Although Morse code has been used extensively—not
just by composers but by telegraph operators the world over—there is an inherent problem. If you receive a dot followed by a dash, how should you decode it? This is Morse for the letter a —but it is also Morse for the letter e followed by the letter t. As a result, mathematicians have found that a different sort of code, using 0s and 1s, is much more suitable for machines to understand.
WHAT IS THE NAME OF COLDPLAY’S THIRD ALBUM?
When fans rushed out to buy Coldplay’s third album, released in 2005, there was a lot of excitement over the meaning of the graphics on the front cover, which depicted various colored blocks arranged in a grid. What was the significance of the picture? It turned out to be the title of the album written in one of the very first binary codes, proposed in 1870 by a French engineer, Émile Baudot. The colors were irrelevant: what mattered was that each block represents a 1, and gaps are to be read as 0s.
The seventeenth-century German mathematician Gottfried Leibniz was one of the first to realize the power of 0s and 1s as an effective way of coding information. He got the idea from the Chinese book I Ching —Book of Changes —which explores the dynamic balance of opposites. It contains a set of 64-line arrangements known as hexagrams, which are meant to represent different states or processes, and it was these that inspired Leibniz to create the mathematics of binary (which we met in the last chapter, when we looked at how to win at nim). The symbols consist of a stack of six horizontal lines in which each line in the symbol is either solid or broken. The I Ching explains how these symbols can be used in divination by tossing sticks or coins to determine the structure of the hexagram.