The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography

by Simon Singh

Evolution is a wholly appropriate term, because the development of codes can be viewed as an evolutionary struggle. A code is constantly under attack from codebreakers. When the codebreakers have developed a new weapon that reveals a code’s weakness, then the code is no longer useful. It either becomes extinct or it evolves into a new, stronger code. In turn, this new code thrives only until the codebreakers identify its weakness, and so on. This is analogous to the situation facing, for example, a strain of infectious bacteria. The bacteria live, thrive and survive until doctors discover an antibiotic that exposes a weakness in the bacteria and kills them. The bacteria are forced to evolve and outwit the antibiotic, and, if successful, they will thrive once again and reestablish themselves. The bacteria are continually forced to evolve in order to survive the onslaught of new antibiotics.

In the sixteenth century, the Italian scientist Giovanni Porta described how to conceal a message within a hard-boiled egg by making an ink from a mixture of one ounce of alum and a pint of vinegar, and then using it to write on the shell. The solution penetrates the porous shell, and leaves a message on the surface of the hardened egg albumen, which can be read only when the shell is removed.

first ever military cryptographic device, the Spartan scytale, dating back to the fifth century B.C. The scytale is a wooden staff around which a strip of leather or parchment is wound, as shown in Figure 2. The sender writes the message along the length of the scytale, and then unwinds the strip, which now appears to carry a list of meaningless letters.

One of the earliest descriptions of encryption by substitution appears in the Kāma-Sūtra, a text written in the fourth century A.D. by the Brahmin scholar Vātsyāyana, but based on manuscripts dating back to the fourth century B.C. The Kāma-Sūtra recommends that women should study 64 arts, such as cooking, dressing, massage and the preparation of perfumes. The list also includes some less obvious arts, namely conjuring, chess, bookbinding and carpentry. Number 45 on the list is mlecchita-vikalpā, the art of secret writing, advocated in order to help women conceal the details of their liaisons.

It was definitively stated in 1883 by the Dutch linguist Auguste Kerckhoffs von Nieuwenhof in his book La Cryptographie militaire: “Kerckhoffs’ Principle: The security of a cryptosystem must not depend on keeping secret the crypto-algorithm. The security depends only on keeping secret the key.”

The cipher of Mary Queen of Scots clearly demonstrates that a weak encryption can be worse than no encryption at all. Both Mary and Babington wrote explicitly about their intentions because they believed that their communications were secure, whereas if they had been communicating openly they would have referred to their plan in a more discreet manner.

Each European power had its own so-called Black Chamber, a nerve center for deciphering messages and gathering intelligence. The most celebrated, disciplined and efficient Black Chamber was the Geheime Kabinets-Kanzlei in Vienna. It operated according to a rigorous timetable, because it was vital that its nefarious activities should not interrupt the smooth running of the postal service. Letters which were supposed to be delivered to embassies in Vienna were first routed via the Black Chamber, arriving at 7 A.M. Secretaries melted seals, and a team of stenographers worked in parallel to make copies of the letters. If necessary, a language specialist would take responsibility for duplicating unusual scripts. Within three hours the letters had been resealed in their envelopes and returned to the central post office, so that they could be delivered to their intended destination. Mail merely in transit through Austria would arrive at the Black Chamber at 10 A.M., and mail leaving Viennese embassies for destinations outside Austria would arrive at 4 P.M. All these letters would also be copied before being allowed to continue on their journey. Each day a hundred letters would filter through the Viennese Black Chamber. The copies were passed to the cryptanalysts, who sat in little kiosks, ready to tease out the meanings of the messages. As well as supplying the emperors of Austria with invaluable intelligence, the Viennese Black Chamber sold the information it harvested to other ...

Before the overhaul of the postage system in the mid-1800s, sending a letter cost about a shilling for every hundred miles, beyond the means of most people. However, newspapers could be posted free of charge, and this provided a loophole for thrifty Victorians. Instead of writing and sending letters, people began to use pinpricks to spell out a message on the front page of a newspaper. They could then send the newspaper through the post without having to pay a penny.

the French listening posts learned to recognize a radio operator’s fist. Once encrypted, a message is sent in Morse code, as a series of dots and dashes, and each operator can be identified by his pauses, the speed of transmission, and the relative lengths of dots and dashes. A fist is the equivalent of a recognizable style of handwriting. As well as operating listening posts, the French established six direction finding stations which were able to detect where each message was coming from. Each station moved its antenna until the incoming signal was strongest, which identified a direction for the source of a message. By combining the directional information from two or more stations it was possible to locate the exact source of the enemy transmission. By combining fist information with direction finding, it was possible to establish both the identity and the location of, say, a particular battalion. French intelligence could then track its path over the course of several days, and potentially deduce its destination and objective. This form of intelligence gathering, known as traffic analysis, was particularly valuable after the introduction of a new cipher. Each new cipher would make cryptanalysts temporarily impotent, but even if a message was indecipherable it could still yield information via traffic analysis.

Rejewski’s strategy for attacking Enigma focused on the fact that repetition is the enemy of security: repetition leads to patterns, and cryptanalysts thrive on patterns.

Rejewski had vastly simplified the task of finding the day key by divorcing the problem of finding the scrambler settings from the problem of finding the plugboard settings. On their own, both of these problems were solvable. Originally, we estimated that it would take more than the lifetime of the universe to check every possible Enigma key. However, Rejewski had spent only a year compiling his catalogue of chain lengths, and thereafter he could find the day key before the day was out. Once he had the day key, he possessed the same information as the intended receiver and so could decipher messages just as easily.

Even when the Germans made a minor alteration to the way they transmitted messages, Rejewski fought back. His old catalogue of chain lengths was useless, but rather than rewriting the catalogue he devised a mechanized version of his cataloguing system, which could automatically search for the correct scrambler settings. Rejewski’s invention was an adaptation of the Enigma machine, able to rapidly check each of the 17,576 settings until it spotted a match. Because of the six possible scrambler arrangements, it was necessary to have six of Rejewski’s machines working in parallel, each one representing one of the possible arrangements. Together, they formed a unit that was about a meter high, capable of finding the day key in roughly two hours. The units were called bombes, a name that might reflect the ticking noise they made while checking scrambler settings. Alternatively, it is said that Rejewski got his inspiration for the machines while at a cafe eating a bombe, an ice cream shaped into a hemisphere. The bombes effectively mechanized the process of decipherment. It was a natural response to Enigma, which was a mechanization of encipherment.

cryptanalysts began to invent their own shortcuts for finding the Enigma keys. For example, they cottoned on to the fact that the German Enigma operators would occasionally choose obvious message keys. For each message, the operator was supposed to select a different message key, three letters chosen at random. However, in the heat of battle, rather than straining their imaginations to pick a random key, the overworked operators would sometimes pick three consecutive letters from the Enigma keyboard (Figure 46), such as QWE or BNM. These predictable message keys became known as cillies. Another type of cilly was the repeated use of the same message key, perhaps the initials of the operator’s girlfriend—indeed, one such set of initials, C.I.L., may have been the origin of the term. Before cracking Enigma the hard way, it became routine for the cryptanalysts to try out the cillies, and their hunches would sometimes pay off. Cillies were not weaknesses of the Enigma machine, rather they were weaknesses in the way the machine was being used.

Human error at more senior levels also compromised the security of the Enigma cipher. Those responsible for compiling the codebooks had to decide which scramblers would be used each day, and in which positions. They tried to ensure that the scrambler settings were unpredictable by not allowing any scrambler to remain in the same position for two days in a row. So, if we label the scramblers 1, 2, 3, 4 and 5, then on the first day it would be possible to have the arrangement 134, and on the second day it would be possible to have 215, but not 214, because scrambler number 4 is not allowed to remain in the same position for two days in a row. This might seem a sensible strategy because the scramblers are constantly changing position, but enforcing such a rule actually makes life easier for the cryptanalyst. Excluding certain arrangements to avoid a scrambler remaining in the same position meant that the codebook compilers reduced by half the number of possible scrambler arrangements. The Bletchley cryptanalysts realized what was happening and made the most of it. Once they identified the scrambler arrangement for one day, they could immediately rule out half the scrambler arrangements for the next day. Hence, their workload was reduced by half.

Similarly, there was a rule that the plugboard settings could not include a swap between any letter and its neighbor, which meant that S could be swapped with any letter except R and T. The theory was that such obvious swappings should be deliberately avoided, but once again the implementation of a rule drastically reduced the number of possible keys.

When a piece of plaintext can be associated with a piece of ciphertext, this combination is known as a crib.

Jack Good, a veteran of Bletchley, commented: “Fortunately the authorities did not know that Turing was a homosexual. Otherwise we might have lost the war.”

Winston Churchill was fully aware of the importance of the Bletchley decipherments, and on September 6, 1941, he visited the codebreakers. On meeting some of the cryptanalysts, he was surprised by the bizarre mixture of people who were providing him with such valuable information; in addition to the mathematicians and linguists, there was an authority on porcelain, a curator from the Prague Museum, the British chess champion and numerous bridge experts. Churchill muttered to Sir Stewart Menzies, head of the Secret Intelligence Service, “I told you to leave no stone unturned, but I didn’t expect you to take me so literally.” Despite the comment, he had a great fondness for the motley crew, calling them “the geese who laid golden eggs and never cackled.”

Frank Birch, who headed the Naval section at Bletchley, recorded the reaction of Turing and his colleague Peter Twinn: “Turing and Twinn came to me like undertakers cheated of a nice corpse two days ago, all in a stew about the cancelation of Operation Ruthless.”

The historian David Kahn summarizes the impact of breaking Enigma: “It saved lives. Not only Allied and Russian lives but, by shortening the war, German, Italian, and Japanese lives as well. Some people alive after World War II might not have been but for these solutions. That is the debt that the world owes to the codebreakers; that is the crowning human value of their triumphs.”

Alan Turing was another cryptanalyst who did not live long enough to receive any public recognition. Instead of being acclaimed a hero, he was persecuted for his homosexuality. In 1952, while reporting a burglary to the police, he naively revealed that he was having a homosexual relationship. The police felt they had no option but to arrest and charge him with “Gross Indecency contrary to Section 11 of the Criminal Law Amendment Act 1885.” The newspapers reported the subsequent trial and conviction, and Turing was publicly humiliated. Turing’s secret had been exposed, and his sexuality was now public knowledge. The British Government withdrew his security clearance. He was forbidden to work on research projects relating to the development of the computer. He was forced to consult a psychiatrist and had to undergo hormone treatment, which made him impotent and obese. Over the next two years he became severely depressed, and on June 7, 1954, he went to his bedroom, carrying with him a jar of cyanide solution and an apple. Twenty years earlier he had chanted the rhyme of the Wicked Witch: “Dip the apple in the brew, Let the sleeping death seep through.” Now he was ready to obey her incantation. He dipped the apple in the cyanide and took several bites. At the age of just forty-two, one of the true geniuses of cryptanalysis committed suicide.

Although Purple and Enigma, the Japanese and German ciphers, were eventually broken, they did offer some security when they were initially implemented and provided real challenges for American and British cryptanalysts. In fact, had the cipher machines been used properly—without repeated message keys, without cillies, without restrictions on plugboard settings and scrambler arrangements, and without stereotypical messages which resulted in cribs—it is quite possible that they might never have been broken at all.

The true strength and potential of machine ciphers was demonstrated by the Typex (or Type X) cipher machine used by the British army and air force, and the SIGABA (or M-143-C) cipher machine used by the American military. Both these machines were more complex than the Enigma machine and both were used properly, and therefore they remained unbroken throughout the war.

Navajo tribal dialect is completely unintelligible to all other tribes and all other people, with the possible exception of as many as 28 Americans who have made a study of the dialect.

For the Navajos, committing everything to memory was trivial because traditionally their language had no written script, so they were used to memorizing their folk stories and family histories. As William McCabe, one of the trainees, said, “In Navajo everything is in the memory—songs, prayers, everything. That’s the way we were raised.”

a one-way function is easy to do but very difficult to undo. In other words, two-way functions are reversible, but one-way functions are not reversible. Once again, the best way to illustrate a one-way function is in terms of an everyday activity. Mixing yellow and blue paint to make green paint is a one-way function because it is easy to mix the paint, but impossible to unmix it. Another one-way function is the cracking of an egg, because it is easy to crack an egg but impossible then to return the egg to its original condition.

Returning to padlock analogies, asymmetric cryptography can be thought of in the following way. Anybody can close a padlock simply by clicking it shut, but only the person who has the key can open it. Locking (encryption) is easy, something everybody can do, but unlocking (decryption) can be done only by the owner of the key. The trivial knowledge of knowing how to click the padlock shut does not tell you how to unlock it. Taking the analogy further, imagine that Alice designs a padlock and key. She guards the key, but she manufactures thousands of replica padlocks and distributes them to post offices all over the world. If Bob wants to send a message, he puts it in a box, goes to the local post office, asks for an “Alice padlock” and padlocks the box. Now he is unable to unlock the box, but when Alice receives it she can open it with her unique key. The padlock and the process of clicking it shut is equivalent to the public encryption key, because everyone has access to the padlocks, and everyone can use a padlock to seal a message in a box. The padlock’s key is equivalent to the private decryption key, because only Alice has it, only she can open the padlock, and only she can gain access to the message in the box.

When Cocks did eventually realize what he had done, it struck him that his discovery might have disappointed G.H. Hardy, one of the great English mathematicians of the early part of the century. In his The Mathematician’s Apology, written in 1940, Hardy had proudly stated: “Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers.” Real mathematics means pure mathematics, such as the number theory that was at the heart of Cocks’s work. Cocks proved that Hardy was wrong.

In the past, if the government wanted to violate the privacy of ordinary citizens, it had to expend a certain amount of effort to intercept and steam open and read paper mail, or listen to and possibly transcribe spoken telephone conversations. This is analogous to catching fish with a hook and a line, one fish at a time. Fortunately for freedom and democracy, this kind of labor-intensive monitoring is not practical on a large scale. Today, electronic mail is gradually replacing conventional paper mail, and is soon to be the norm for everyone, not the novelty it is today. Unlike paper mail, e-mail messages are just too easy to intercept and scan for interesting keywords. This can be done easily, routinely, automatically, and undetectably on a grand scale. This is analogous to driftnet fishing-making a quantitative and qualitative Orwellian difference to the health of democracy.

In February 1993, two government investigators paid Zimmermann a visit. After their initial enquiries about patent infringement, they began to ask questions about the more serious accusation of illegally exporting a weapon. Because the U.S. Government included encryption software within its definition of munitions, along with missiles, mortars and machine guns, PGP could not be exported without a license from the State Department. In other words, Zimmermann was accused of being an arms dealer because he had exported PGP via the Internet. Over the next three years Zimmermann became the subject of a grand jury investigation and found himself pursued by the FBI.

One of the best-known cases of continuous unjustified wiretapping concerns Martin Luther King Jr., whose telephone conversations were monitored for several years. For example, in 1963 the FBI obtained information on King via a wiretap and fed it to Senator James Eastland in order to help him in debates on a civil rights bill. More generally, the FBI gathered details about King’s personal life, which were used to discredit him. Recordings of King telling bawdy stories were sent to his wife and played in front of President Johnson. Then, following King’s award of the Nobel Prize, embarrassing details about King’s life were passed to any organization that was considering conferring an honor upon him.

Whitfield Diffie states that individuals have enjoyed complete privacy for most of history: In the 1790s, when the Bill of Rights was ratified, any two people could have a private conversation-with a certainty no one in the world enjoys today-by walking a few meters down the road and looking to see no one was hiding in the bushes. There were no recording devices, parabolic microphones, or laser interferometers bouncing off their eyeglasses. You will note that civilization survived. Many of us regard that period as a golden age in American political culture.