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

by Simon Singh

  Next, Alice picks another card from the pack, say the king of diamonds, but, again, she can measure only one property. This time she chooses to measure its value, which is “king,” and transmits the card down a phone line to Bob. Eve tries to measure the card, and she also chooses to measure its value, “king.” When the card reaches Bob, he decides to measure its suit, which is “diamonds.” Afterward, Alice calls Bob and asks him if he measured the card’s value, and he has to admit that he guessed wrong and measured its suit. Alice and Bob are not bothered because they can ignore this particular card completely, and try again with another card chosen at random from the pack. On this last occasion Eve guessed right, and measured the same as Alice, “king,” but the card was discarded because Bob did not measure it correctly. So Bob does not have to worry about his mistakes, because Alice and he can agree to ignore them, but Eve is stuck with her mistakes. By sending several cards, Alice and Bob can agree on a sequence of suits and values which can then be used as the basis for some kind of key.

  Quantum cryptography allows Alice and Bob to agree on a key, and Eve cannot intercept this key without making errors. Furthermore, quantum cryptography has an additional benefit: it provides a way for Alice and Bob to find out if Eve is eavesdropping. Eve’s presence on the line becomes apparent because every time that she measures a photon, she risks altering it, and these alterations become obvious to Alice and Bob.

  Imagine that Alice sends , and Eve measures it with the wrong detector, the +-detector. In effect, the +-detector forces the incoming photon to emerge as either a or a photon, because this is the only way the photon can get through Eve’s detector. If Bob measures the transformed photon with his ×-detector, then he might detect , which is what Alice sent, or he might detect , which would be a mismeasurement. This is a problem for Alice and Bob, because Alice sent a diagonally polarized photon and Bob used the correct detector, yet he might have measured it incorrectly. In short, when Eve chooses the wrong detector, she will “twist” some of the photons, and this will make Bob prone to errors, even when he is using the correct detector. These errors can be found if Alice and Bob perform a brief error-checking procedure.

  The error checking is done after the three preliminary stages, by which time Alice and Bob should have identical sequences of 1’s and 0’s. Imagine that they have established a sequence that is 1,075 binary digits in length. One way for Alice and Bob to check that their respective sequences match would be for Alice to call Bob and read out her complete sequence to him. Unfortunately, if Eve is eavesdropping she would then be able to intercept the entire key. Checking the complete sequence is clearly unwise, and it is also unnecessary. Instead, Alice merely has to pick 75 of the digits at random and check just these. If Bob agrees with the 75 digits, it is highly unlikely that Eve was eavesdropping during the original photon transmission. In fact, the chances of Eve being on the line and not affecting Bob’s measurement of these 75 digits are less than one in a billion. Because these 75 digits have been openly discussed by Alice and Bob, they must be discarded, and their onetime pad is thus reduced from 1,075 to 1,000 binary digits. On the other hand, if Alice and Bob find a discrepancy among the 75 digits, then they will know that Eve has been eavesdropping, and they would have to abandon the entire onetime pad, switch to a new line and start all over again.

  To summarize, quantum cryptography is a system that ensures the security of a message by making it hard for Eve to read accurately a communication between Alice and Bob. Furthermore, if Eve tries to eavesdrop then Alice and Bob will be able to detect her presence. Quantum cryptography therefore allows Alice and Bob to exchange and agree upon a onetime pad in complete privacy, and thereafter they can use this as a key to encrypt a message. The procedure has five basic steps:

  (1) Alice sends Bob a series of photons, and Bob measures them.

  (2) Alice tells Bob on which occasions he measured them in the correct way. (Although Alice is telling Bob when he made the correct measurement, she is not telling him what the correct result should have been, so this conversation can be tapped without any risk to security.)

  (3) Alice and Bob discard the measurements that Bob made incorrectly, and concentrate on those measurements he made correctly in order to create an identical pair of onetime pads.

  (4) Alice and Bob check the integrity of their onetime pads by testing a few of the digits.

  (5) If the verification procedure is satisfactory, they can use the onetime pad to encrypt a message; if the verification reveals errors, they know that the photons were being tapped by Eve, and they need to start all over again.

  Fourteen years after Wiesner’s paper on quantum money had been rejected by the science journals, it had inspired an absolutely secure system of communication. Now living in Israel, Wiesner is relieved that, at last, his work is being recognized: “Looking back, I wonder if I couldn’t have made more of it. People have accused me of being a quitter, for not having tried harder to get my idea published—I guess they’re right in a way—but I was a young graduate student, and I didn’t have that much confidence. In any case, nobody seemed interested in quantum money.”

  Cryptographers greeted Bennett and Brassard’s quantum cryptography with enthusiasm. However, many experimentalists argued that the system worked well in theory, but would fail in practice. They believed that the difficulty of dealing with individual photons would make the system impossible to implement. Despite the criticism, Bennett and Brassard were convinced that quantum cryptography could be made to work. In fact, they had so much faith in their system that they did not bother building the apparatus. As Bennett once put it, “there is no point going to the North Pole if you know it’s there.”

  However, the mounting skepticism eventually goaded Bennett into proving that the system could really work. In 1988 he began accumulating the components he would need for a quantum cryptographic system, and took on a research student, John Smolin, to help assemble the apparatus. After a year of effort they were ready to attempt to send the first message ever to be protected by quantum cryptography. Late one evening they retreated into their light-tight laboratory, a pitch-black environment safe from stray photons that might interfere with the experiment. Having eaten a hearty dinner, they were well prepared for a long night of tinkering with the apparatus. They set about the task of trying to send polarized photons across the room, and then measuring them using a +-detector and a ×-detector. A computer called Alice ultimately controlled the transmission of photons, and a computer called Bob decided which detector should be used to measure each photon.

  After hours of tweaking, at around 3 A.M., Bennett witnessed the first quantum cryptographic exchange. Alice and Bob managed to send and receive photons, they discussed the polarization schemes that Alice had used, they discarded photons measured by Bob using the wrong detector and they agreed on a onetime pad consisting of the remaining photons. “There was never any doubt that it would work,” recalls Bennett, “only that our fingers might be too clumsy to build it.” Bennett’s experiment had demonstrated that two computers, Alice and Bob, could communicate in absolute secrecy. This was a historic experiment, despite the fact that the two computers were separated by a distance of just 30 cm.

  Ever since Bennett’s experiment, the challenge has been to build a quantum cryptographic system that operates over useful distances. This is not a trivial task, because photons do not travel well. If Alice transmits a photon with a particular polarization through air, the air molecules will interact with it, causing a change in its polarization, which cannot be tolerated. A more efficient medium for transmitting photons is via an optic fiber, and researchers have recently succeeded in using this technique to build quantum cryptographic systems that operate over significant distances. In 1995, researchers at the University of Geneva succeeded in implementing quantum cryptography in an optic fiber that stretched 23 km from Geneva to the town of Nyon.

  More recently, a group of scientists at Los Alamos National Laboratory in New Me
xico has once again begun to experiment with quantum cryptography in air. Their ultimate aim is to create a quantum cryptographic system that can operate via satellites. If this could be achieved, it would enable absolutely secure global communication. So far the Los Alamos group has succeeded in transmitting a quantum key through air over a distance of 1 km.

  Security experts are now wondering how long it will be before quantum cryptography becomes a practical technology. At the moment there is no advantage in having quantum cryptography, because the RSA cipher already gives us access to effectively unbreakable encryption. However, if quantum computers were to become a reality, then RSA and all other modern ciphers would be useless, and quantum cryptography would become a necessity. So the race is on. The really important question is whether quantum cryptography will arrive in time to save us from the threat of quantum computers, or whether there will be a privacy gap, a period between the development of quantum computers and the advent of quantum cryptography. So far, quantum cryptography is the more advanced technology. The Swiss experiment with optic fibers demonstrates that it would be feasible to build a system that permits secure communication between financial institutions within a single city. Indeed, it is currently possible to build a quantum cryptography link between the White House and the Pentagon. Perhaps there already is one.

  Quantum cryptography would mark the end of the battle between codemakers and codebreakers, and the codemakers emerge victorious. Quantum cryptography is an unbreakable system of encryption. This may seem a rather exaggerated assertion, particularly in the light of previous similar claims. At different times over the last two thousand years, cryptographers have believed that the monoalphabetic cipher, the polyalphabetic cipher and machine ciphers such as Enigma were all unbreakable. In each of these cases the cryptographers were eventually proved wrong, because their claims were based merely on the fact that the complexity of the ciphers outstripped the ingenuity and technology of cryptanalysts at one point in history. With hindsight, we can see that the cryptanalysts would inevitably figure out a way of breaking each cipher, or developing technology that would break it for them.

  However, the claim that quantum cryptography is secure is qualitatively different from all previous claims. Quantum cryptography is not just effectively unbreakable, it is absolutely unbreakable. Quantum theory, the most successful theory in the history of physics, means that it is impossible for Eve to intercept accurately the onetime pad key established between Alice and Bob. Eve cannot even attempt to intercept the onetime pad key without Alice and Bob being warned of her eavesdropping. Indeed, if a message protected by quantum cryptography were ever to be deciphered, it would mean that quantum theory is flawed, which would have devastating implications for physicists; they would be forced to reconsider their understanding of how the universe operates at the most fundamental level.

  If quantum cryptography systems can be engineered to operate over long distances, the evolution of ciphers will stop. The quest for privacy will have come to an end. The technology will be available to guarantee secure communications for governments, the military, businesses and the public. The only question remaining would be whether or not governments would allow us to use the technology. How would governments regulate quantum cryptography, so as to enrich the Information Age, without protecting criminals?

  The Cipher Challenge

  The Cipher Challenge is a set of ten encrypted messages, which I placed at the end of The Code Book when it was first published in 1999. In addition to the intellectual reward of cracking all ten messages, there was a prize of $15,000 for the first person to solve the Challenge. The Challenge was eventually solved on October 7, 2000, after one year and one month of arduous effort by codebreakers, amateur and professional, around the world.

  The Cipher Challenge remains as part of this book. There is no longer a prize associated with its solution, but I would encourage readers to decipher some of the messages. The ten stages were intended to grow in difficulty, although many codebreakers have felt that stage 3 is harder than stage 4. The ciphers used in the stages differ and progress through the ages, so the early ciphers are ancient and easy to break, whereas the latter stages employ modern ciphers and require a great deal more effort. In short, stages 1 to 4 are for the amateur, stages 5 to 8 are for the real enthusiast, and 9 and 10 are for those who are dedicated codebreakers.

  If you want to know more about the Cipher Challenge, you can visit my own Web site (www.simonsingh.com), which offers a variety of information, including a link to a report written by the Cipher Challenge winners, Fredrik Almgren, Gunnar Andersson, Torbjorn Granlund, Lars Ivansson and Staffan Ulfberg. The report makes excellent reading, but please be aware that it, and other material on the Web site, does include spoilers that you might not want to see just yet.

  The main aim of the Cipher Challenge was to excite people, to get them interested in cryptography and codebreaking. The fact that thousands of people took up the challenge is tremendously satisfying. Officially the Cipher Challenge is now over, but I hope that it will continue to generate some interest among new readers who want to test their codebreaking skills.

  Good luck,

  Simon Singh

  Stage 1: Simple Monoalphabetic Substitution Cipher

  Stage 2: Caesar Shift Cipher

  Stage 3: Monoalphabetic Cipher with Homophones

  Stage 4: Vigenère Cipher

  Stage 5

  Stage 6

  Stage 7

  Stage 8

  Stage 9

  Stage 10

  Shorter message

  Longer message

  Appendices

  Appendix A

  The Opening Paragraph of A Void by Georges Perec, translated by Gilbert Adair

  Today, by radio, and also on giant hoardings, a rabbi, an admiral notorious for his links to masonry, a trio of cardinals, a trio, too, of insignificant politicians (bought and paid for by a rich and corrupt Anglo-Canadian banking corporation), inform us all of how our country now risks dying of starvation. A rumor, that’s my initial thought as I switch off my radio, a rumor or possibly a hoax. Propaganda, I murmur anxiously-as though, just by saying so, I might allay my doubts-typical politicians’ propaganda. But public opinion gradually absorbs it as a fact. Individuals start strutting around with stout clubs. “Food, glorious food!” is a common cry (occasionally sung to Bart’s music), with ordinary hardworking folk harassing officials, both local and national, and cursing capitalists and captains of industry. Cops shrink from going out on night shift. In Mâcon a mob storms a municipal building. In Rocadamour ruffians rob a hangar full of foodstuffs, pillaging tons of tuna fish, milk and cocoa, as also a vast quantity of corn-all of it, alas, totally unfit for human consumption. Without fuss or ado, and naturally without any sort of trial, an indignant crowd hangs 26 solicitors on a hastily built scaffold in front of Nancy’s law courts (this Nancy is a town, not a woman) and ransacks a local journal, a disgusting right-wing rag that is siding against it. Up and down this land of ours looting has brought docks, shops and farms to a virtual standstill.

  First published in France as La Disparition by Editions Denöel in 1969, and in Great Britain by Harvill in 1994. Copyright © by Editions Denöel 1969; in the English translation © Harvill 1994. Reproduced by permission of the Harvill Press.

  Appendix B

  Some Elementary Tips for Frequency Analysis

  (1) Begin by counting up the frequencies of all the letters in the ciphertext. About five of the letters should have a frequency of less than 1 per cent, and these probably represent j, k, q, x and z. One of the letters should have a frequency greater than 10 per cent, and it probably represents e. If the ciphertext does not obey this distribution of frequencies, then consider the possibility that the original message was not written in English. You can identify the language by analyzing the distribution of frequencies in the ciphertext. For example, typically in Italian there are three letters with a frequency greater than 10 per cent, and n
ine letters have frequencies less than 1 per cent. In German, the letter e has the extraordinarily high frequency of 19 per cent, so any ciphertext containing one letter with such a high frequency is quite possibly German. Once you have identified the language you should use the appropriate table of frequencies for that language for your frequency analysis. It is often possible to unscramble ciphertexts in an unfamiliar language, as long as you have the appropriate frequency table.

  (2) If the correlation is sympathetic with English, but the plaintext does not reveal itself immediately, which is often the case, then focus on pairs of repeated letters. In English the most common repeated letters are ss, ee, tt, ff, ll, mm and oo. If the ciphertext contains any repeated characters, you can assume that they represent one of these.

  (3) If the ciphertext contains spaces between words, then try to identify words containing just one, two or three letters. The only one-letter words in English are a and I. The commonest two-letter words are of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am. The most common three-letter words are the and and.

  (4) If possible, tailor the table of frequencies to the message you are trying to decipher. For example, military messages tend to omit pronouns and articles, and the loss of words such as I, he, a and the will reduce the frequency of some of the commonest letters. If you know you are tackling a military message, you should use a frequency table generated from other military messages.