5
Alice and Bob Go Public
Modern cryptography,
the solution to the so-called
key-distribution problem
and the secret history of
nonsecret encryption
During the Second World War, British codebreakers had the upper hand over German codemakers, mainly because the men and women at Bletchley Park, following the lead of the Poles, developed some of the earliest codebreaking technology. In addition to Turing’s bombes, which were used to crack the Enigma cipher, the British also invented another codebreaking device, Colossus, to combat an even stronger form of encryption, the German Lorenz cipher. Of the two types of codebreaking machine, it was Colossus that would determine the development of cryptography during the latter half of the twentieth century.
The Lorenz cipher was used to encrypt communications between Hitler and his generals. The encryption was performed by the Lorenz SZ40 machine, which operated in a similar way to the Enigma machine, but the Lorenz was far more complicated, and it provided the Bletchley codebreakers with an even greater challenge. However, two of Bletchley’s codebreakers, John Tiltman and Bill Tutte, discovered a weakness in the way that the Lorenz cipher was used, a flaw that Bletchley could exploit and thereby read Hitler’s messages.
Breaking the Lorenz cipher required a mixture of searching, matching, statistical analysis and careful judgement, all of which was beyond the technical abilities of the bombes. The bombes were able to carry out a specific task at high speed, but they were not flexible enough to deal with the subtleties of Lorenz. Lorenz-encrypted messages had to be broken by hand, which took weeks of painstaking effort, by which time the messages were largely out of date. Eventually, Max Newman, a Bletchley mathematician, came up with a way to mechanize the cryptanalysis of the Lorenz cipher. Drawing heavily on the ideas of Alan Turing, Newman designed a machine that was capable of adapting itself to different problems, what we today would call a programmable computer.
Implementing Newman’s design was deemed technically impossible, so Bletchley’s senior officials shelved the project. Fortunately, Tommy Flowers, an engineer who had taken part in discussions about Newman’s design, decided to ignore Bletchley’s scepticism and went ahead with building the machine. Flowers took Newman’s blueprint and spent ten months turning it into the Colossus machine, which he delivered to Bletchley Park on December 8, 1943. It consisted of fifteen hundred electronic valves, which were considerably faster than the sluggish electromechanical relay switches used in the bombes. But more important than Colossus’ speed was the fact that it was programmable. It was this fact that made Colossus the precursor to the modern digital computer.
Colossus, as with everything else at Bletchley Park, was destroyed after the war, and those who worked on it were forbidden to talk about it. When Tommy Flowers was ordered to dispose of the Colossus blueprints, he obediently took them down to the boiler room and burned them. The plans for the world’s first computer were lost for ever. In 1945, J. Presper Eckert and John W. Mauchly of the University of Pennsylvania completed ENIAC (Electronic Numerical Integrator and Calculator), consisting of eighteen thousand electronic valves, capable of performing five thousand calculations per second. For decades, ENIAC, not Colossus, was considered the mother of all computers.
Having contributed to the birth of the modern computer, codebreakers continued after the war to develop and employ computer technology in order to break all sorts of ciphers. They could now exploit the speed and flexibility of programmable computers to search through all possible keys until the correct one was found. In due course, the codemakers began to fight back, exploiting the power of computers to create increasingly complex ciphers. In short, the computer played a crucial role in the postwar battle between codemakers and codebreakers.
Using a computer to encipher a message is, to a large extent, very similar to traditional forms of encryption. Indeed, there are only three significant differences between computer encryption and the sort of mechanical encryption that was the basis for ciphers such as Enigma. The first difference is that a mechanical cipher machine is limited by what can be practically built, whereas a computer can mimic a hypothetical cipher machine of immense complexity. For example, a computer could be programmed to mimic the action of a hundred scramblers, some spinning clockwise, some counterclockwise, some vanishing after every tenth letter, others rotating faster and faster as encryption progresses. Such a mechanical machine would be practically impossible to build, but its virtual computerized equivalent would deliver a highly secure cipher.
The second difference is simply a matter of speed. Electronic circuits can operate far more quickly than mechanical scramblers: a computer programmed to mimic the Enigma cipher could encipher a lengthy message in an instant. Alternatively, a computer programmed to perform a vastly more complex form of encryption could still accomplish the task within a reasonable time.
The third, and perhaps most significant, difference is that a computer scrambles numbers rather than letters of the alphabet. Computers deal only in binary numbers – sequences of ones and zeros known as binary digits, or bits for short. Before encryption, any message must therefore be converted into binary digits. This conversion can be performed according to various protocols, such as the American Standard Code for Information Interchange, known familiarly by the acronym ASCII, pronounced “az-key”. ASCII assigns a seven-digit binary number to each letter of the alphabet. For the time being, it is sufficient to think of a binary number as merely a pattern of ones and zeros that uniquely identifies each letter (Table 13), just as Morse code identifies each letter with a unique series of dots and dashes. There are 128 (27) ways to arrange a combination of seven binary digits, so ASCII can identify up to 128 distinct characters. This allows plenty of room to define all the lowercase letters (e.g., a = 1100001) and all necessary punctuation (e.g., ! = 0100001) as well as other symbols (e.g., & = 0100110). Once the message has been converted into binary, encryption can begin.
Even though we are dealing with computers and numbers, and not machines and letters, the encryption still proceeds in the traditional way.
For example, imagine that we wish to encrypt the message HELLO by employing a simple computer version of a substitution cipher. Before encryption can begin, we must translate the message into ASCII according to Table 13. Each letter of the message is replaced with the appropriate seven-bit ASCII binary number.
As usual, substitution relies on a key that has been agreed between sender and receiver. In this case the key is the word DAVID translated into ASCII, and it is used in the following way. Each element of the plaintext is “added” to the corresponding element of the key. Adding binary digits can be thought of in terms of two simple rules. If the elements in the plaintext and the key are the same, the element in the plaintext is substituted for 0 in the ciphertext. But if the elements in the message and key are different, the element in the plaintext is substituted for 1 in the ciphertext:
The resulting encrypted message is a single string of thirty-five binary digits that can be transmitted to the receiver, who uses the same key to reverse the substitution, thus re-creating the original string of binary digits. Finally, the receiver reinterprets the binary digits via ASCII to regenerate the message HELLO.
Table 13 ASCII binary numbers for the capital letters.
Computer encryption was restricted to those who had computers, which in the early days meant the government and the military. However, a series of scientific, technological and engineering breakthroughs made computers, and computer encryption, far more widely available. In 1947, AT&T Bell Laboratories invented the transistor, a cheap alternative to the electronic valve. Commercial computing became a reality in 1951 when companies such as Ferranti began to make computers to order. In 1953 IBM launched its first computer, and four years later it introduced Fortran, a programming language that allowed ordinary people to write computer programs. Then, in 1959, the invention of the integrated circuit heralded a new era of computing.
During the 1960s, computers became more powerful, and at the same time they became much cheaper. Businesses were increasingly able to afford computers, and could use them to encrypt important communications such a money transfers or delicate trade negotiations. However, as more businesses bought computers, and as encryption between businesses spread, cryptographers were confronted with a major problem known as key distribution.
Imagine that a bank wants to send some confidential data to a client via a telephone line but is worried that there might be somebody tapping the wire. The bank picks a key (remember that the key defines the exact recipe for scrambling the message) and uses some encryption software to scramble the message. In order to decrypt the message, the client needs not only to have a copy of the encryption software on its computer, but also to know which key was used to encrypt the message. How does the bank inform the client of the key? It cannot send the key via the telephone line, because it suspects that there is an eavesdropper on the line. The only truly secure way to send the key is to hand it over in person, which is clearly a time-consuming task. A less secure but more practical solution is to send the key via a courier. In the 1970s, banks attempted to distribute keys by employing special dispatch riders who had been investigated and who were among the company’s most trusted employees. These dispatch riders would race across the world with padlocked briefcases, personally distributing keys to everyone who would receive messages from the bank over the next week. As business networks grew in size, as more messages were sent, and as more keys had to be delivered, the banks found that this distribution process became a horrendous logistical nightmare, and the overhead costs became too high.
The problem of key distribution has plagued cryptographers throughout history. For example, during the Second World War the German high command had to distribute the monthly book of day keys to all its Enigma operators, which was an enormous logistical problem. Also, U-boats, which tended to spend extended periods away from base, had to somehow obtain a regular supply of keys. In earlier times, users of the Vigenère cipher had to find a way of getting the keyword from the sender to the receiver. No matter how secure a cipher is in theory, in practice it can be undermined by the problem of key distribution.
Key distribution might seem a trivial issue, but it became the overriding problem for postwar cryptographers. If two parties wanted to communicate securely, they had to rely on a third party to deliver the key, and this became the weakest link in the chain of security.
Despite claims that the problem of key distribution was unsolvable, a team of mavericks triumphed against the odds and came up with a brilliant solution in the mid-1970s. They devised an encryption system that appeared to defy all logic. Although computers transformed the implementation of ciphers, the greatest revolution in twentieth-century cryptography was the development of techniques to overcome the problem of key distribution. Indeed, this breakthrough is considered to be the greatest cryptographic achievement since the invention of the monoalphabetic cipher, over two thousand years ago.
GOD REWARDS FOOLS
Whitfield Diffie is one of the most enthusiastic cryptographers of his generation. The mere sight of him creates a striking and somewhat contradictory image. His impeccable suit reflects the fact that for most of the 1990s, he has been employed by one of Americas giant computer companies – currently his official job title is Distinguished Engineer at Sun Microsystems. However, his shoulder-length hair and long white beard betray the fact that his heart is still stuck in the 1960s. He spends much of his time in front of a computer workstation, but he looks as if he would be equally comfortable in a Bombay ashram. Diffie is aware that his dress and personality can have quite an impact on others, and comments, “People always think that I am taller than I really am, and I’m told it’s the Tigger effect – ‘No matter his weight in pounds, shillings and ounces, he always seems bigger because of the bounces.’”
Diffie was born in 1944 and spent most of his early years in Queens, New York. As a child, he became fascinated by mathematics, reading books ranging from The Chemical Rubber Company Handbook of Mathematical Tables to G. H. Hardy’s Course of Pure Mathematics. He went on to study mathematics at the Massachusetts Institute of Technology, graduating in 1965. He then took a series of jobs related to computer security, and by the early 1970s he had matured into one of the few truly independent security experts, a freethinking cryptographer, not employed by the government or by any of the big corporations. In hindsight, he was the first cypherpunk.
Diffie was particularly interested in the key-distribution problem, and he realized that whoever could find a solution would go down in history as one of the all-time great cryptographers. Diffie was so captivated by the problem of key distribution that it became the most important entry in his special notebook entitled “Problems for an Ambitious Theory of Cryptography”. Part of Diffie’s motivation came from his vision of a wired world. Back in the 1960s, the U.S. Department of Defense began funding a cutting-edge research organization called the Advanced Research Projects Agency (ARPA), and one of ARPA’s frontline projects was to find a way of connecting military computers across vast distances. The ARPANet steadily grew in size, and in 1982 it spawned the Internet. At the end of the 1980s, nonacademic and nongovernmental users were given access to the Internet, and thereafter the number of users exploded. Today, millions of people all over the world use the Internet to exchange all sorts of information, often by sending each other emails.
While the ARPANet was still in its infancy, Diffie was farsighted enough to forecast the advent of the information superhighway and the digital revolution. Ordinary people would one day have their own computers, and these computers would be interconnected via phone lines. Diffie believed that if people then used their computers to exchange emails, they deserved the right to encrypt their messages in order to guarantee their privacy. However, encryption required the secure exchange of keys. If governments and large corporations were having trouble coping with key distribution, then the public would find it impossible, and would effectively be deprived of the right to privacy.
Diffie imagined two strangers meeting via the Internet, and wondered how they could send each other an encrypted message. He also considered the scenario of a person wanting to buy something on the Internet. How could that person send an email containing encrypted credit-card details so that only the Internet retailer could decipher them? In both cases, it seemed that the two parties needed to share a key, but how could they exchange keys securely? The number of casual contacts and the amount of spontaneous emails among the public would be enormous, and this would mean that key distribution would be impractical. Diffie was fearful that the necessity of key distribution would prevent the public from having access to digital privacy, and he became obsessed with the idea of finding a solution to the problem.
In 1974, Diffie, still an independent cryptographer, paid a visit to IBM’s Thomas J. Watson Laboratory, where he had been invited to give a talk. He spoke about various strategies for attacking the key-distribution problem, but all his ideas were very tentative, and his audience was sceptical about the prospects for a solution. The only positive response to Diffie’s presentation was from Alan Konheim, one of IBM’s senior cryptographic experts, who mentioned that someone else had recently visited the laboratory and given a lecture that addressed the issue of key distribution. That speaker was Martin Hellman, a professor from Stanford University in California. That evening Diffie got in his car and began the 5000 km journey to the West Coast to meet the only person who seemed to share his obsession. The alliance of Diffie and Hellman would become one of the most dynamic partnerships in cryptography.
Martin Hellman was born in 1945 in a Jewish neighbourhood in the Bronx, New York, but when he was four his family moved to a predominantly Irish Catholic neighbourhood. According to Hellman, this permanently changed his attitude to life: “The other kids went to church and they learned that the Jews killed Christ, so I got called ‘Christ killer’. I also got beat up. To start with, I wanted to be like the other kids, I wanted a Christmas tree and I wanted Christmas presents. But then I realized that I couldn’t be like all the other kids, and in self-defense I adopted an attitude of ‘Who would want to be like everybody else?’”
Hellman traces his interest in ciphers to this enduring desire to be different. His colleagues had told him he was crazy to do research in cryptography, because he would be competing with the National Security Agency (NSA) and their multibillion-dollar budget. How could he hope to discover something that they did not know already? And if he did discover anything, the NSA would classify it.
In September 1974 he received an unexpected phone call from Whitfield Diffie. Hellman had never heard of Diffie, but grudgingly agreed to a half-hour appointment later that afternoon. By the end of the meeting, Hellman realized that Diffie was the best-informed person he had ever met. The feeling was mutual. Hellman recalls: “I’d promised my wife I’d be home to watch the kids, so he came home with me and we had dinner together. He left at around midnight. Our personalities are very different – he is much more counterculture than I am – but eventually the personality clash was very symbiotic. It was just such a breath of fresh air for me. Working in a vacuum had been really hard.”
Since Hellman did not have a great deal of funding, he could not afford to employ his new soul mate as a researcher. Instead, Diffie was enrolled as a graduate student. Together, Hellman and Diffie began to study the key-distribution problem, desperately trying to find an alternative to the tiresome task of physically transporting keys over vast distances. In due course they were joined by Ralph Merkle. Merkle had left another research group where the professor had no sympathy for the impossible dream of solving the key-distribution problem. Says Hellman:
Ralph, like us, was willing to be a fool. And the way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited, and it flops. Then you have idea number 2, you get excited, and it flops. Then you have idea number 99, you get excited, and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you’re foolish enough to be continually excited, you won’t have the motivation, you won’t have the energy to carry it through. God rewards fools.
The whole problem of key distribution is a classic catch-22 situation. If two people want to exchange a secret message over the phone, the sender must encrypt it. To encrypt the secret message the sender must use a key, which is itself a secret, so then there is the problem of transmitting the secret key to the receiver in order to transmit the secret message. In short, before two people can exchange a secret (an encrypted message) they must already share a secret (the key).
When thinking about the problem of key distribution, it is helpful to consider Alice, Bob and Eve, three fictional characters who have become the industry standard for discussions about cryptography. In a typical situation, Alice wants to send a message to Bob, or vice versa, and Eve is trying to eavesdrop. If Alice is sending private messages to Bob, she will encrypt each one before sending it, using a separate key each time. Alice is continually faced with the problem of key distribution because she has to convey the keys to Bob securely, otherwise he cannot decrypt the messages. One way to solve the problem is for Alice and Bob to meet up once a week and exchange enough keys to cover the messages that might be sent during the next seven days. Exchanging keys in person is certainly secure, but it is inconvenient, and if either Alice or Bob is taken ill, the system breaks down. Alternatively, Alice and Bob could hire couriers, which would be less secure and more expensive, but at least they have delegated some of the work. Either way, it seems that the distribution of keys is unavoidable. For two thousand years, this was considered to be an axiom of cryptography – an indisputable truth. However, there is a scenario that seems to defy the axiom.
Imagine that Alice and Bob live in a country where the postal system is completely immoral, and postal employees will read any unprotected correspondence. One day, Alice wants to send an intensely personal message to Bob. She puts it inside an iron box, closes it and secures it with a padlock and key. She puts the padlocked box in the mail and keeps the key. However, when the box reaches Bob, he is unable to open it because he does not have the key. Alice might consider putting the key inside another box, padlocking it and sending it to Bob, but without the key to the second padlock he is unable to open the second box, so he cannot obtain the key that opens the first box. The only way around the problem seems to be for Alice to make a copy of her key and give it to Bob in advance when they meet for coffee. So far, I have just restated the same old problem in a new way. Avoiding key distribution seems logically impossible – surely, if Alice wants to lock something in a box so that only Bob can open it, she must give him a copy of the key. Or, in terms of cryptography, if Alice wants to encipher a message so that only Bob can decipher it, she must give him a copy of the key. Key exchange is an inevitable part of encipherment – or is it?
Now picture the following situation. As before, Alice wants to send an intensely personal message to Bob. Again, she puts her secret message in an iron box, padlocks it and sends it to Bob. When the box arrives, Bob adds his own padlock and sends the box back to Alice. When Alice receives the box, it is now secured by two padlocks. She removes her own padlock, leaving just Bob’s padlock to secure the box. Finally she sends the box back to Bob. And here is the crucial difference: Bob can now open the box, because it is secured only with his own padlock, to which he alone has the key.
The implications of this little story are enormous. It demonstrates that a secret message can be securely exchanged between two people without necessarily exchanging a key. For the first time there is some hope that key exchange might not be an inevitable part of cryptography. We can reinterpret the story in terms of encryption. Alice uses her own key to encrypt a message to Bob, who encrypts it again with his own key and returns it. When Alice receives the doubly encrypted message, she removes her own encryption and returns it to Bob, who can then remove his own encryption and read the message.
It seems that the problem of key distribution might have been solved, because the doubly encrypted scheme requires no exchange of keys. However, there are several obstacles to implementing a system in which Alice encrypts, Bob encrypts, Alice decrypts and Bob decrypts. One problem is the order in which the encryptions and decryptions are performed. In general, the order of encryption and decryption is crucial, and should obey the rule “last on, first off”. In other words, the last stage of encryption should be the first to be decrypted. In the above scenario, Bob performed the last stage of encryption, so this should have been the first to be decrypted, but it was Alice who removed her encryption first, before Bob removed his. Unfortunately, many encryption systems are far more sensitive than padlocks when it comes to order. The importance of order is most easily grasped by examining something we do every day. In the morning we put on our socks, and then we put on our shoes, and in the evening we remove our shoes before removing our socks – it is impossible to remove the socks before the shoes. The locked box scenario works because padlocks can be added and removed in any order, but for most cipher systems the order of encryption and decryption is critical. The rule “last on, first off” must be obeyed.
Although the doubly padlocked box approach would not work for real-world cryptography, it inspired Diffie and Hellman to search for a practical method of circumventing the key-distribution problem. Then, in 1975, Diffie had a truly brilliant idea. He can still recall how the idea flashed into his mind and then almost vanished: “I walked downstairs to get a Coke, and almost forgot about the idea. I remembered that I’d been thinking about something interesting, but couldn’t quite recall what it was. Then it came back in a real adrenaline rush of excitement. I was actually aware for the first time in my work on cryptography of having discovered something really valuable. Everything that I had discovered in the subject up to this point seemed to me to be mere technicalities.” It was mid-afternoon, and he had to wait a couple of hours before his wife, Mary, returned. “Whit was waiting at the door,” she recalls. “He said he had something to tell me, and he had a funny look on his face. I walked in and he said, ‘Sit down, please, I want to talk to you. I believe that I have made a great discovery – I know I am the first person to have done this.’ The world stood still for me at that moment. I felt like I was living in a Hollywood film.”
Diffie had concocted a new type of cipher, one that incorporates a so-called asymmetric key. So far, all the encryption techniques described in this book have been symmetric, which means that the unscrambling process is simply the opposite of scrambling. For example, the Enigma machine uses a certain key setting to encipher a message, and the receiver uses an identical machine in the same key setting to decipher it. Both sender and receiver effectively have equivalent knowledge, and they both use the same key to encrypt and decrypt – their relationship is symmetric. In an asymmetric key system, as the name suggests, the encryption key and the decryption key are not identical. In an asymmetric cipher, if Alice knows the encryption key, she can encrypt a message, but she cannot decrypt a message. In order to decrypt, Alice must have access to the decryption key. This distinction between encryption and decryption keys is what makes an asymmetric cipher special.
Although Diffie had come up with the general concept of an asymmetric cipher, he did not actually have a specific example of one. However, the mere concept of an asymmetric cipher was revolutionary. If cryptographers could find a genuine working asymmetric cipher, a system that fulfilled Diffie’s requirements, then the implications for Alice and Bob would be enormous. Alice could create her own pair of keys: an encryption key and a decryption key. If we assume that the asymmetric cipher is a form of computer encryption, then Alice’s encryption key is a number, and her decryption key is a different number. Alice keeps the decryption key secret, so it is commonly referred to as Alice’s private key. However, she publishes the encryption key so that everybody has access to it, which is why it is commonly referred to as Alice’s public key. If Bob wants to send Alice a message, he simply looks up her public key, which would be listed in something akin to a telephone directory. Bob then uses Alice’s public key to encrypt the message. He sends the encrypted message to Alice, and when it arrives Alice can decrypt it using her private decryption key. Similarly, if Charlie or Dawn want to send Alice an encrypted message, they too can look up Alice’s public encryption key, and in each case only Alice has access to the private decryption key required to decrypt the message.
The great advantage of this system is that it overcomes the problem of key distribution. Alice does not have to transport the public encryption key securely to Bob; in fact, she wants to publicize her public encryption key so that anybody can use it to send her encrypted messages. At the same time, even if the whole world knows Alice’s public key, nobody, including Eve, can decrypt any messages encrypted with it, because knowledge of the public key is no help in decryption. In fact, once Bob has encrypted a message using Alice’s public key, even he cannot decrypt it. Only Alice, who alone possesses her private key, can decrypt the message.
This is the exact opposite of a traditional symmetric cipher, in which Alice has to go to great lengths to transport the encryption key securely to Bob. In a symmetric cipher the encryption key is the same as the decryption key, so Alice and Bob must take the utmost precautions to ensure that the key does not fall into Eve’s hands. This is the root of the key-distribution problem.
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 equip you 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, along with everyone else, 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 padlocks 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.
The system seems simple when it is explained in terms of padlocks, but it is far from trivial to find a mathematical function that does the same job, something that can be incorporated into a workable cryptographic system. To turn asymmetric ciphers from a great idea into a practical invention, somebody had to discover an appropriate mathematical function to act as a mathematical padlock. A function is any mathematical operation that turns one number into another number. For example, doubling is a type of function because it turns the number 3 into 6, or the number 9 into 18. Furthermore, we can think of all forms of computer encryption as functions because they turn one number (the plaintext) into another number (the ciphertext).
Most mathematical functions are classified as two-way functions because they are easy to do and easy to undo. For example, doubling is a two-way function, because it is easy to double a number to generate a new number and just as easy to undo the function and get from the doubled number back to the original number. If we know that the result of doubling is 26, then it is trivial to reverse the function and deduce that the original number was 13. The easiest way to understand the concept of a two-way function is in terms of an everyday activity. We can think of the act of turning on a light switch as a function, because it turns an ordinary lightbulb into an illuminated one. This function is two-way because if a switch is turned on, it is easy enough to turn it off and return the lightbulb to its original state.
However, Diffie and Hellman were not interested in two-way functions. They focused their attention on one-way functions. As the name suggests, 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. For this reason, one-way functions are sometimes called Humpty Dumpty functions.
Padlocks are also real-world examples of a one-way function, because they are easy to lock but very difficult to unlock. Diffie’s idea relied on a mathematical padlock, and this is why the Stanford team of Diffie, Hellman and Merkle focused their attention on studying one-way functions.
Modular arithmetic, sometimes called clock arithmetic in schools, is an area of mathematics that is rich in one-way functions. It deals with a finite group of numbers arranged in a loop, rather like the numbers on a clock. For example, Figure 47 shows a clock for modular 7 (or mod 7), which has only the seven numbers from 0 to 6. To work out 2 + 3, we start at 2 and move around three places to reach 5, which is the same answer as in normal arithmetic. To work out 2 + 6, we start at 2 and move around six places, but this time we go around the loop and arrive at 1, which is not the result we would get in normal arithmetic. These results can be expressed as:
2 + 3 = 5 (mod 7) and 2 + 6 = 1 (mod 7)
Figure 47 Modular arithmetic is performed on a finite set of numbers, which can be thought of as numbers on a clock face. In this case, we can work out 6 + 5 in modular 7 by starting at 6 and moving around five spaces, which brings us to 4.
Modular arithmetic is relatively simple, and in fact we do it every day when we talk about time. If it is nine o’clock now, and we have a meeting eight hours from now, we would say that the meeting is at five o’clock, not seventeen o’clock. We have mentally calculated 9 + 8 in mod 12. Imagine a clock face, look at 9, and then move around eight spaces, ending up at 5:
9 + 8 = 5 (mod 12)
Rather than visualizing clocks, mathematicians often take the shortcut of performing modular calculations according to the following recipe. First, perform the calculation in normal arithmetic. Second, if we want to know the answer in mod x, we divide the normal answer by x and note the remainder. This remainder is the answer in mod x. For example, to find the answer in modular arithmetic to the question What is 11 x 9 (mod 13), we do the following:
Functions performed in the modular arithmetic environment tend to behave erratically, which in turn sometimes makes them one-way functions. This becomes evident when a simple function in normal arithmetic is compared with the same simple function in modular arithmetic. In the former environment the function will be two-way and easy to reverse; in the latter environment it will be one-way and hard to reverse. As an example, let us take the function 3x. This means take a number x, then multiply 3 by itself x times in order to get the new number. For example, if x = 2 and we perform the function, then:
In other words, the function turns 2 into 9. In normal arithmetic, as the value of x increases so does the result of the function. So if we were given the result of the function, it would be relatively easy to work backwards and deduce the original number. For example, if the result is 81, we can deduce that x is 4, because 34 = 81. If we made a mistake and guessed that x is 5, we could work out that 35 = 243, which tells us that our choice of x is too big. We would then reduce our choice of x to 4, and we would have the right answer. In short, even when we guess wrongly, we can home in on the correct value of x and thereby reverse the function.
However, in modular arithmetic this same function does not behave so sensibly. Imagine that we are told that 3x in mod 7 is 1, and we are asked to find the value of x. No value springs to mind, because we are generally unfamiliar with modular arithmetic. We could take a guess that x = 5, and we could work out the result of 35 (mod 7). The answer turns out to be 5, which is too big, because we are looking for an answer of just 1. We might be tempted to reduce the value of x to 4 and try again. But we would be heading in the wrong direction, because the actual answer is x = 6.
In normal arithmetic we can test numbers and can sense whether we are getting warmer or colder. The environment of modular arithmetic gives no helpful clues, and reversing functions is much harder. Often the only way to reverse a function in modular arithmetic is to compile a table by calculating the function for many values of x until the right answer is found. Table 14 shows the result of calculating several values of the function in both normal arithmetic and modular arithmetic. It clearly demonstrates the erratic behaviour of the function when calculated in modular arithmetic.
Although drawing up such a table is only a little tedious when we are dealing with relatively small numbers, it would be excruciatingly painful to build a table to deal with a function such as 453x (mod 21,997). This is a classic example of a one-way function, because I could pick a value for x and calculate the result of the function, but if I gave you a result, say, 5,787, you would have enormous difficulty in reversing the function and deducing the value of x. It would take you hours to draw up the table and thereby work out the correct value of x.
Table 14 Values of the function 3x calculated in normal arithmetic (row 2) and modular arithmetic (row 3). The function increases continuously in normal arithmetic, but is highly erratic in modular arithmetic.
However, this particular one-way function is not adequate to act as a mathematical padlock, because padlocks exhibit a special type of one-way functionality. It is easy to click a padlock and lock it, but it is very difficult to unlock the padlock … unless, of course, you have the key! The key is what makes a padlock a special type of one-way function. The true mathematical equivalent of a padlock is a function that is always easy to perform in one direction but generally hard to perform in the opposite direction unless you have some special piece of information, namely, the key.
If such a function existed, then Alice would personalize it, which would give her the special piece of information for reversing the function. She would keep this information secret but distribute the personalized function so that Bob and everyone else can use it to encrypt messages to her. She can decrypt these messages by using the special piece of information. She unlocks the encrypted messages sent to her by using her secret key. Similarly, Bob would personalize the function so that he has his own piece of special secret information. He too distributes his mathematical padlock so that Alice and anybody else can encrypt and send messages to him. Only Bob has the special piece of information required to decrypt the messages sent to him, which have been encrypted using his personalized padlock.
The team of Diffie, Hellman and Merkle had invigorated the world of cryptography. They had persuaded the rest of the world that a solution to the key-distribution problem lay just over the horizon. They had proposed the concept of an asymmetric cipher – a perfect but as yet unworkable system. They continued their research at Stanford University, attempting to find a special one-way function that would make asymmetric ciphers a reality. However, they failed to make the discovery. They were overtaken in the race to find an asymmetric cipher by another trio of researchers, based nearly five thousand kilometres away on the East Coast of America.
PRIME SUSPECTS
“I walked into Ron Rivest’s office,” recalls Leonard Adleman, “and Ron had this paper in his hands. He started saying, ‘These Stanford guys have this really blah, blah, blah.’ And I remember thinking, ‘That’s nice, Ron, but I have something else I want to talk about.’ I was entirely unaware of the history of cryptography, and I was distinctly uninterested in what he was saying.” The paper that had made Ron Rivest so excited was by Diffie and Hellman, and it described the concept of asymmetric ciphers. Eventually Rivest persuaded Adleman that there might be some interesting mathematics in the problem, and together they resolved to try to find a one-way function that fit the requirements of an asymmetric cipher. They were joined in the hunt by Adi Shamir. All three men were researchers on the eighth floor of the MIT Laboratory for Computer Science.
Rivest, Shamir and Adleman formed a perfect team. Rivest is a computer scientist with a tremendous ability to absorb new ideas and apply them in unlikely places. He always kept up with the latest scientific papers, which inspired him to come up with a whole series of weird and wonderful candidates for the one-way function at the heart of an asymmetric cipher. However, each candidate was flawed in some way. Shamir, another computer scientist, has a lightning intellect and an ability to see through the debris and focus on the core of a problem. He too regularly generated ideas for formulating an asymmetric cipher, but his ideas were also inevitably flawed. Adleman, a mathematician with enormous stamina, rigour and patience, was largely responsible for spotting the flaws in the ideas of Rivest and Shamir, ensuring that they did not waste time following false leads. Rivest and Shamir spent a year coming up with new ideas, and Adleman spent a year shooting them down. The threesome began to lose hope, but they were unaware that this process of continual failure was a necessary part of their research, gently steering them away from sterile mathematical territory and towards more fertile ground. In due course, their efforts were rewarded.
In April 1977, Rivest, Shamir and Adleman spent Passover at the house of a student, returning to their respective homes sometime around midnight. Rivest, unable to sleep, lay on his couch reading a mathematics textbook. He began mulling over the question that had been puzzling him for weeks: is it possible to build an asymmetric cipher? Is it possible to find a one-way function that can be reversed only if the receiver has some special information? Suddenly, the mists began to clear and he had a revelation. He spent the rest of that night formalizing his idea, effectively writing a complete scientific paper before daybreak. Rivest had made a breakthrough, but it had grown out of a year-long collaboration with Shamir and Adleman, and it would not have been possible without them. Rivest finished off the paper by listing the authors alphabetically: Adleman, Rivest, Shamir.
Figure 48 Ronald Rivest, Adi Shamir and Leonard Adleman.
The next morning, Rivest handed the paper to Adleman, who went through his usual process of trying to tear it apart, but this time he could find no faults. His only criticism was with the list of authors. “I told Ron to take my name off the paper,” recalls Adleman. “I told him that it was his invention, not mine. But Ron refused, and we got into a discussion about it. We agreed that I would go home and contemplate it for one night, and consider what I wanted to do. I went back the next day and suggested to Ron that I be the third author. I recall thinking that this paper would be the least interesting paper that I will ever be on.” Adleman could not have been more wrong. The system, dubbed RSA (Rivest, Shamir, Adleman) as opposed to ARS, went on to become the most influential cipher in modern cryptography.
Before exploring Rivest’s idea, here is a quick reminder of what scientists were looking for in order to build an asymmetric cipher:
1. Alice must create a public key, which she would then publish so that Bob (and everybody else) can use it to encrypt messages to her. Because the public key is a one-way function, it must be virtually impossible for anybody to reverse it and decrypt Alice’s messages.
2. However, Alice needs to decrypt the messages being sent to her. She must therefore have a private key, some special piece of information, which allows her to reverse the effect of the public key. Therefore, Alice (and Alice alone) has the power to decrypt any messages sent to her.
At the heart of Rivest’s asymmetric cipher is a one-way function based on the sort of modular function described earlier in the chapter. Rivest’s one-way function can be used to encrypt a message – the message, which is effectively a number, is put into the function, and the result is the ciphertext, another number. I shall not describe Rivest’s one-way function in detail here (instead, see Appendix E), but I shall explain one particular aspect of it, known simply as N, because it is N that makes this one-way function reversible under certain circumstances, and therefore ideal for use as an asymmetric cipher.
N is important because it is a flexible component of the one-way function, which means that each person can choose a different value of N and personalize the one-way function. In order to choose her personal value of N, Alice picks two prime numbers, p and q, and multiplies them together. A prime number is one that has no divisors except itself and 1. For example, 7 is a prime number because no numbers except 1 and 7 will divide into it without leaving a remainder. Likewise, 13 is a prime number because no numbers except 1 and 13 will divide into it without leaving a remainder. However, 8 is not a prime number, because it can be divided by 2 and 4.
So Alice could choose her prime numbers to be p = 17,159 and q = 10,247. Multiplying these two numbers together gives N = 17,159 x 10,247 = 175,828,273. Alice’s choice of N effectively becomes her public encryption key, and she could print it on her business card, post it on the Internet or publish it in a public-key directory along with everybody else’s value of N. If Bob wants to encrypt a message to Alice, he looks up Alice’s value of N (175,828,273) and then inserts it into the general form of the one-way function, which would also be public knowledge. Bob now has a one-way function tailored with Alice’s public key, so it could be called Alice’s one-way function. To encrypt a message to Alice, he takes Alice’s one-way function, inserts the message, notes down the result and sends it to Alice.
At this point the encrypted message is secure because nobody can decipher it. The message has been encrypted with a one-way function, so reversing the one-way function and decrypting the message is, by definition, very difficult. However, the question remains – how can Alice decrypt the message? In order to read messages sent to her, Alice must have a way of reversing the one-way function. She needs to have access to some special piece of information that allows her to decrypt the message. Fortunately for Alice, Rivest designed the one-way function so that it is reversible to someone who knows the values of p and q, the two prime numbers that are multiplied together to give N. Although Alice has told the world that her value for N is 175,828,273, she has not revealed her values for p and q, so only she has the special information required to decrypt her own messages.
We can think of N as the public key, the information that is available to everybody, the information required to encrypt messages to Alice, whereas p and q are the private key, the information required to decrypt these messages. This private key is only available to Alice.
The exact details of how p and q can be used to reverse the one-way function are outlined in Appendix E. However, there is one question that must be addressed immediately. If everybody knows N, the public key, then can’t people deduce p and q, the private key, and read Alice’s messages? After all, N was created from p and q. In fact, it turns out that if N is large enough, it is virtually impossible to deduce p and q from N, and this is perhaps the most beautiful and elegant aspect of the RSA asymmetric cipher.
Alice created N for her one-way function by choosing p and q and then multiplying them together. The fundamental point is that this is in itself a one-way function. To demonstrate the one-way nature of multiplying primes, we can take two prime numbers, such as 9,419 and 1,933, and multiply them together. With a calculator it takes a few seconds to get the answer, 18,206,927. However, if instead we were given 18,206,927 and asked to find the prime factors (the two numbers that were multiplied to give 18,206,927) it would take much longer. If you doubt the difficulty of finding prime factors, then try the following: it took me just seconds to generate the number 1,709,023, but it will take you and a calculator the best part of an afternoon to work out the prime factors.
This system of asymmetric cryptography, known as RSA, is said to be a form of public-key cryptography. To find out how secure RSA is, we need to see how difficult it is to factor N, because this is what Eve would have to do to find p and q and thereby work out the private key needed to decipher messages.
For high security, Bob would choose very large values of p and q. For example, he could choose primes that are as big as 1065 (this means 1 followed by sixty-five zeros, or one hundred thousand million million million million million million million million million million). This would have resulted in a value for N that would have been roughly 1065 x 1065, which is 10130. A computer could multiply the two primes and generate N in just a second, but if Eve wanted to reverse the process and work out p and q, it would take inordinately longer. Exactly how long depends on the speed of Eve’s computer. Security expert Simson Garfinkel estimated that a 100 MHz Intel Pentium computer with 8 MB of RAM would take roughly fifty years to factor a number as big as 10130. Cryptographers tend to have a paranoid streak and consider worst-case scenarios, such as a worldwide conspiracy to crack their ciphers. So Garfinkel considered what would happen if a hundred million personal computers (the number sold in 1995) ganged up together. The result is that a number as big as 10130 could be factored in about fifteen seconds. Consequently, it is now generally accepted that for genuine security it is necessary to use even larger primes. For important banking transactions, N tends to be at least 10308, which is ten million billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion billion times bigger than 10130. The combined efforts of a hundred million personal computers would take more than a thousand years to crack such a cipher. With sufficiently large values of p and q, RSA is impenetrable.
The only caveat for the security of RSA public-key cryptography is that at some time in the future somebody might find a quick way to factor N. It is conceivable that a decade from now, or even tomorrow, somebody will discover a method for rapid factoring, and thereafter RSA will become useless. However, for over two thousand years mathematicians have tried and failed to find a shortcut, and at the moment factoring remains an enormously time-consuming calculation. Most mathematicians believe that factoring is an inherently difficult task and that there is some mathematical law that forbids any shortcut. If we assume they are right, then RSA seems secure for the foreseeable future.
The great advantage of RSA public-key cryptography is that it does away with all the problems associated with traditional ciphers and key exchange. Alice no longer has to worry about securely transporting the key to Bob, or that Eve might intercept the key. In fact, Alice does not care who sees the public key – the more the merrier, because the public key helps only with encryption, not decryption. The only thing that needs to remain secret is the private key used for decryption, and Alice can keep this with her at all times.
RSA was first announced in August 1977, when Martin Gardner wrote an article entitled “A New Kind of Cipher that Would Take Millions of Years to Break” for his “Mathematical Games” column in Scientific American. After explaining how public-key cryptography works, Gardner issued a challenge to his readers. He printed a ciphertext and also provided the public key that had been used to encrypt it:
The challenge was to factor N into p and q, and then use these numbers to decrypt the message. The prize was $100. Gardner did not have space to explain the nitty-gritty of RSA, and instead he asked readers to write to MIT’s Laboratory for Computer Science, which in turn would send back a technical memorandum that had just been prepared. Rivest, Shamir and Adleman were astonished by the three thousand requests they received. However, they did not respond immediately, because they were concerned that public distribution of their idea might jeopardize their chances of getting a patent. When the patent issues were eventually resolved, the trio held a celebratory party at which professors and students consumed pizza and beer while stuffing envelopes with technical memoranda for the readers of Scientific American.
As for Gardner’s challenge, it would take seventeen years before the cipher would be broken. On April 26, 1994, a team of six hundred volunteers announced the factors of N:
Using these values as the private key, they were able to decipher the message. The message was a series of numbers, but when converted into letters, it read, “The magic words are squeamish ossifrage.” The factoring problem had been split among volunteers, who came from countries as far apart as Australia, Britain, the United States and Venezuela. The volunteers used spare time on their workstations, mainframes and supercomputers, each of them tackling a fraction of the problem. In effect, a network of computers around the world were uniting and working simultaneously in order to meet Gardner’s challenge. Even bearing in mind the mammoth parallel effort, some readers may still be surprised that RSA was broken in such a short time, but it should be noted that Gardner’s challenge used a relatively small value of N – it was only of the order of 10129. Today, users of RSA would pick a much larger value to secure important information. It is now routine to encrypt a message with a sufficiently large value of N so that all the computers on the planet would need longer than the age of the universe to break the cipher.
THE SECRET HISTORY OF PUBLIC-KEY CRYPTOGRAPHY
Over the past twenty years, Diffie, Hellman and Merkle have become world-famous as the cryptographers who invented the concept of public-key cryptography, while Rivest, Shamir and Adleman have been credited with developing RSA, the most beautiful implementation of public-key cryptography. However, a recent announcement means that the history books have to be rewritten. According to the British government, public-key cryptography was originally invented at the Government Communications Headquarters (GCHQ) in Cheltenham, the top-secret establishment that was formed from the remnants of Bletchley Park after the Second World War. This is a story of remarkable ingenuity, anonymous heroes and a government cover-up that endured for decades.
On April 1, 1965, James Ellis had moved to Cheltenham to join the newly formed Communications-Electronics Security Group (CESG), a special section of GCHQ devoted to ensuring the security of British communications. At the beginning of 1969, the military asked Ellis, by now one of Britain’s foremost government cryptographers, to look into ways of coping with the key-distribution problem. Because he was involved in issues of national security, Ellis was sworn to secrecy throughout his career. Although his wife and family knew that he worked at GCHQ, they were unaware of his discoveries and had no idea that he was one of the nations most distinguished codemakers.
Figure 49 James Ellis.
One of Ellis’ greatest qualities was his breadth of knowledge. He read any scientific journal he could get his hands on, and never threw anything away. For security reasons, GCHQ employees must clear their desks each evening and place everything in locked cabinets, which meant that Ellis’ cabinets were stuffed full with the most obscure publications imaginable. He gained a reputation as a cryptoguru, and if other researchers found themselves with impossible problems, they would knock on his door in the hope that his vast knowledge and originality would provide a solution. It was probably because of this reputation that he was asked to examine the key-distribution problem.
Ellis began his attack on the problem by searching through his treasure-trove of scientific papers. Many years later, he recorded the moment when he discovered that key distribution was not an inevitable part of cryptography:
The event which changed this view was the discovery of a wartime Bell Telephone report by an unknown author describing an ingenious idea for secure telephone speech. It proposed that the recipient should mask the sender’s speech by adding noise to the line. He could subtract the noise afterwards since he had added it and therefore knew what it was. The obvious practical disadvantages of this system prevented it being actually used, but it has some interesting characteristics. The difference between this and conventional encryption is that in this case the recipient takes part in the encryption process … So the idea was born.
Noise is the technical term for any signal that interferes with a communication. Normally it is generated by natural phenomena, and its most irritating feature is that it is entirely random, which means that removing noise from a message is very difficult. If a radio system is well designed, then the level of noise is low and the message is clearly audible, but if the noise level is high and it swamps the message, there is no way to recover the message. Ellis was suggesting that the receiver, Alice, deliberately create noise, which she could measure before adding it to the communication channel that connects her with Bob. Bob could then send a message to Alice, and if Eve tapped the communications channel, she would be unable to read the message because it would be swamped in noise. The only person who can remove the noise and read the message is Alice, because she is in the unique position of knowing the exact nature of the noise, having put it there in the first place. Ellis realized that security had been achieved without exchanging any key. The key was the noise, and only Alice needed to know the details of the noise.
In a memorandum, Ellis detailed his thought processes: “The next question was the obvious one. Can this be done with ordinary encipherment? Can we produce a secure encrypted message, readable by the authorised recipient without any prior secret exchange of the key? This question actually occurred to me in bed one night, and the proof of the theoretical possibility took only a few minutes. We had an existence theorem. The unthinkable was actually possible.” An existence theorem shows that a particular concept is possible but is not concerned with the details of the concept. In other words, until this moment, searching for a solution to the key-distribution problem was like looking for a needle in a haystack, with the possibility that the needle might not even be there. However, thanks to the existence theorem, Ellis now knew that the needle was in there somewhere.
Ellis’s ideas were very similar to those of Diffie, Hellman and Merkle, except that he was several years ahead of them. However, nobody knew of Ellis’s work because he was an employee of the British government and therefore sworn to secrecy. By the end of 1969, Ellis appears to have reached the same impasse that the Stanford trio would reach in 1975. He had proved to himself that public-key cryptography (or nonsecret encryption, as he called it) was possible, and he had developed the concept of separate public keys and private keys. He also knew that he needed to find a special one-way function, one that could be reversed if the receiver had access to a piece of special information. Unfortunately, Ellis was not a mathematician. He experimented with a few mathematical functions, but he soon realized that he would be unable to progress any further on his own.
For the next three years, GCHQ’s brightest minds struggled to find a one-way function that satisfied Ellis’s requirements, but nothing emerged. Then, in September 1973, a new mathematician joined the team. Clifford Cocks had recently graduated from Cambridge University, where he had specialized in number theory, one of the purest forms of mathematics. When he joined GCHQ he knew very little about encryption and the shadowy world of military and diplomatic communication, so he was assigned a mentor, Nick Patterson, who guided him through his first few weeks as a cryptographer.
After about six weeks, Patterson told Cocks about “a really wacky idea”. He outlined Ellis’s theory for public-key cryptography, and explained that nobody had yet been able to find a mathematical function that fitted the bill. Patterson was telling Cocks because this was the most exciting cryptographic idea around, not because he expected him to try to solve it. However, as Cocks explains, later that day he set to work: “There was nothing particular happening, and so I thought I would think about the idea. Because I had been working in number theory, it was natural to think about one-way functions, something you could do but not undo. Prime numbers and factoring was a natural candidate, and that became my starting point.” Cocks was beginning to formulate what would later be known as the RSA asymmetric cipher. Rivest, Shamir and Adleman discovered their formula for public-key cryptography in 1977, but four years earlier the young Cambridge graduate was going through exactly the same thought processes. Cocks recalls: “From start to finish, it took me no more than half an hour. I was quite pleased with myself. I thought, Ooh, that’s nice. I’ve been given a problem, and I’ve solved it.’”
Cocks did not fully appreciate the significance of his discovery. He was unaware of the fact that GCHQ’s brightest minds had been struggling with the problem for three years, and he had no idea that he had made one of the most important cryptographic breakthroughs of the century. Cocks’s naivety may have been part of the reason for his success, allowing him to attack the problem with confidence, rather than timidly prodding at it. Cocks told his mentor about his discovery, and it was Patterson who then reported it to the management. Cocks was quite diffident and very much still a rookie, whereas Patterson fully appreciated the context of the problem and was more capable of addressing the technical questions that would inevitably arise. Soon complete strangers started approaching Cocks, the wonder kid, and began to congratulate him. One of the strangers was James Ellis, eager to meet the man who had turned his dream into a reality. Because Cocks still did not understand the magnitude of his achievement, the details of this meeting did not make a great impact on him, and so now, three decades later, he has no memory of Ellis’s reaction.
Although Cocks’s idea was one of GCHQ’s most potent secrets, it suffered from the problem of being ahead of its time. Cocks had discovered a mathematical function that permitted public-key cryptography, but there was still the difficulty of implementing the system. Encryption via public-key cryptography requires much more computer power than encryption via a symmetric cipher. In the early 1970s, computers were still relatively primitive and unable to perform the process of public-key encryption within a reasonable amount of time. Hence, GCHQ was not in a position to exploit public-key cryptography. Cocks and Ellis had proved that the apparently impossible was possible, but nobody could find a way of making the possible practical.
At the beginning of the following year, 1974, Cocks explained his work on public-key cryptography to Malcolm Williamson, who had recently joined GCHQ as a cryptographer. The men happened to be old friends. They had both attended Manchester Grammar School, whose school motto is Sapere aude, “Dare to be wise”. While at school in 1968, the two boys had represented Britain at the Mathematical Olympiad in the Soviet Union. After attending Cambridge University together, they went their separate ways for a couple of years, but now they were reunited at GCHQ. They had been exchanging mathematical ideas since the age of eleven, but Cocks’s revelation of public-key cryptography was the most shocking idea that Williamson had ever heard. “Cliff explained his idea to me,” recalls Williamson, “and I really didn’t believe it. I was very suspicious, because this is a very peculiar thing to be able to do.”
Williamson began trying to prove that Cocks had made a mistake and that public-key cryptography did not really exist. He probed the mathematics, searching for an underlying flaw. Public-key cryptography seemed too good to be true, and Williamson was so determined to find a mistake that he took the problem home. GCHQ employees are not supposed to take work home, because everything they do is classified, and the home environment is potentially vulnerable to espionage. However, the problem was stuck in Williamson’s brain, so he could not avoid thinking about it. Defying orders, he carried his work back to his house. He spent five hours trying to find a flaw. “Essentially I failed,” says Williamson. “Instead I came up with another solution to the problem of key distribution.” He had discovered a protocol now known as Diffie-Hellman-Merkle key exchange (because it was discovered independently and in the public realm by the Americans).
By 1975, James Ellis, Clifford Cocks and Malcolm Williamson had discovered all the fundamental aspects of public-key cryptography, yet they all had to remain silent. The three Britons had to sit back and watch as their discoveries were rediscovered by Diffie, Hellman, Merkle, Rivest, Shamir and Adleman over the next three years.
The scientific press reported the breakthroughs at Stanford and MIT, so the researchers who had been allowed to publish their work in the scientific journals became famous within the community of cryptographers. Cocks’ attitude is admirably restrained: “You don’t get involved in this business for public recognition.” Williamson is equally dispassionate: “My reaction was ‘OK, that’s just the way it is.’ Basically, I just got on with the rest of my life.”
Figure 50 Malcolm Williamson (second from left) and Clifford Cocks (extreme right) arriving for the 1968 Mathematical Olympiad.
Although GCHQ was the first to discover public-key cryptography, this should not diminish the achievements of the academics who rediscovered it. It was the academics who were the first to realize the potential of public-key encryption, and it was they who drove its implementation. Furthermore, it is quite possible that GCHQ never would have revealed its work, thus blocking the encryption protocol that has enabled what we now call the digital revolution. Finally, the discovery by the American academics was wholly independent of GCHQ’s discovery, and on an intellectual par. The academic environment is completely isolated from the top-secret domain of classified research, and academics do not have access to the tools and secret knowledge that may be hidden in the classified world. On the other hand, government researchers always have access to the academic literature. One might think of this flow of information in terms of a one-way function – information flows freely in one direction, but it is forbidden to send information in the opposite direction.
It is difficult to overestimate the level of secrecy maintained by establishments like GCHQ. Even when the academics published RSA, GCHQ remained silent. Even in the late 1980s, when public use of RSA was becoming widespread, GCHQ refused to acknowledge its own invention of public-key cryptography.
Eventually, twenty-eight years after Ellis’ initial breakthrough, GCHQ went public. In 1997, Clifford Cocks completed some important work on RSA that was of interest to the wider community and would not be a security risk if it was published. As a result, he planned to present a paper at the Institute of Mathematics and its Applications Conference to be held in Cirencester. The room would be full of cryptography experts. A handful of them, very senior members of the security world, had heard rumours that Cocks, who would be talking about just one aspect of RSA, was actually its unsung inventor. There was a risk that somebody might ask an embarrassing question, such as “Did you invent RSA?” If such a question arose, what was Cocks supposed to do? According to GCHQ policy, he would have to deny his role in the development of RSA, thus forcing him to lie about an issue that was totally harmless. The situation was clearly ridiculous, and GCHQ decided that it was time to change its policy. Cocks was given permission to begin his talk by presenting a brief history of GCHQ’s contribution to public-key cryptography.
On December 18, 1997, Cocks delivered his talk. After almost three decades of secrecy, Ellis, Cocks and Williamson received the acknowledgement they deserved. Sadly, James Ellis had died just one month earlier, on November 25, 1997, at the age of seventy-three. Ellis joined the list of British cipher experts whose contributions would never be recognized during their lifetimes. Charles Babbage’s breaking of the Vigenère cipher was never revealed while he was alive, probably because his work was invaluable to British forces in the Crimea. Instead, credit for the work went to Friedrich Kasiski. Similarly, Alan Turing’s contribution to the war effort was unparalleled, and yet government secrecy demanded that his work on Enigma not be revealed.
In 1987, GCHQ declassified a document that Ellis had written. It records his contribution to public-key cryptography and includes his thoughts on the secrecy that so often surrounds cryptographic work:
Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work, because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography is realised by minimising the information available to potential adversaries. Thus professional cryptographers normally work in closed communities to provide sufficient professional interaction to ensure quality while maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests of historical accuracy after it has been demonstrated that no further benefit can be obtained from continued secrecy.