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

by Simon Singh

  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 afterward 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 impinges on 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. Eve would be unable to disentangle the noise from the message. 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 authorized 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.

  At this point, Ellis revealed his breakthrough to his bosses. Their reactions are still classified material, but in an interview Richard Walton was prepared to paraphrase for me the various memoranda that were exchanged. Sitting with his briefcase on his lap, the lid shielding the papers from my view, he flicked through the documents:

  I can’t show you the papers that I have in here because they still have naughty words like TOP SECRET stamped all over them. Essentially, James’s idea goes to the top man, who farms it out, in the way that top men do, so that the experts can have a look at it. They state that what James is saying is perfectly true. In other words, they can’t write this man off as a crank. At the same time they can’t think of a way of implementing his idea in practice. And so they’re impressed by James’s ingenuity, but uncertain as to how to take advantage of it.

  For the next three years, GCHQ’s brightest minds struggled to find a oneway 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 at GCHQ.

  After about six weeks, Patterson told Cocks about “a really whacky 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 titillating 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 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 wonderkid, and began to congratulate him. One of the strangers was James Ellis, keen to meet the man who had turned his dream into a reality. Because Cocks still did not understand the enormity of his achievement, the details of this meeting did not make a great impact on him, and so now, over two decades later, he has no memory of Ellis’s reaction.

  Figure 67 Clifford Cocks. (photo credit 6.5)

  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. The intricacies of number theory could now be used to help generals plan their battles in complete secrecy. Because his work had implications for military communications, Cocks, like Ellis, was forbidden from telling anybody outside GCHQ about what he had done. Working at a top-secret government establishment meant that he could tell neither his parents nor his former colleagues at Cambridge University. The only person he could tell was his wife, Gill, since she was also employed at GCHQ.<
br />
  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 like DES. 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 were 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 went away, and 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.” Williamson was discovering Diffie–Hellman–Merkle key exchange, at roughly the same time that Martin Hellman discovered it. Williamson’s initial reaction reflected his cynical disposition: “This looks great, I thought to myself. I wonder if I can find a flaw in this one. I guess I was in a negative mood that day.”

  Figure 68 Malcolm Williamson. (photo credit 6.6)

  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. Curiously, GCHQ discovered RSA before Diffie–Hellman–Merkle key exchange, whereas in the outside world, Diffie–Hellman–Merkle key exchange came first. The scientific press reported the breakthroughs at Stanford and MIT, and the researchers who had been allowed to publish their work in the scientific journals became famous within the community of cryptographers. A quick look on the Internet with a search engine turns up 15 Web pages mentioning Clifford Cocks, compared to 1,382 pages that mention Whitfield Diffie. Cocks’s attitude is admirably restrained: “You don’t get involved in this business for public recognition.” Williamson is equally dispassionate: “My reaction was ‘Okay, that’s just the way it is.’ Basically, I just got on with the rest of my life.”

  Figure 69 Malcolm Williamson (second from left) and Clifford Cocks (extreme right) arriving for the 1968 Mathematical Olympiad.

  Williamson’s only qualm is that GCHQ failed to patent public key cryptography. When Cocks and Williamson first made their breakthroughs, there was agreement among GCHQ management that patenting was impossible for two reasons. First, patenting would mean having to reveal the details of their work, which would have been incompatible with GCHQ’s aims. Second, in the early 1970s it was far from clear that mathematical algorithms could be patented. When Diffie and Hellman tried to file for a patent in 1976, however, it was evident that they could be patented. At this point, Williamson was keen to go public and block Diffie and Hellman’s application, but he was overruled by his senior managers, who were not farsighted enough to see the digital revolution and the potential of public key cryptography. By the early 1980s Williamson’s bosses were beginning to regret their decision, as developments in computers and the embryonic Internet made it clear that RSA and Diffie-Hellman-Merkle key exchange would both be enormously successful commercial products. In 1996, RSA Data Security, Inc., the company responsible for RSA products, was sold for $200 million.

  Although the work at GCHQ was still classified, there was one other organization that was aware of the breakthroughs that had been achieved in Britain. By the early 1980s America’s National Security Agency knew about the work of Ellis, Cocks and Williamson, and it is probably via the NSA that Whitfield Diffie heard a rumor about the British discoveries. In September 1982, Diffie decided to see if there was any truth in the rumor, and he traveled with his wife to Cheltenham in order to talk to James Ellis face-to-face. They met at a local pub, and very quickly Mary was struck by Ellis’s remarkable character:

  We sat around talking, and I suddenly became aware that this was the most wonderful person you could possibly imagine. The breadth of his mathematical knowledge is not something I could confidently discuss, but he was a true gentleman, immensely modest, a person with great generosity of spirit and gentility. When I say gentility, I don’t mean old-fashioned and musty. This man was a chevalier. He was a good man, a truly good man. He was a gentle spirit.

  Diffie and Ellis discussed various topics, from archaeology to how rats in the barrel improve the taste of cider, but whenever the conversation drifted toward cryptography, Ellis gently changed the subject. At the end of Diffie’s visit, as he was ready to drive away, he could no longer resist directly asking Ellis the question that was really on his mind: “Tell me about how you invented public key cryptography?” There was a long pause. Ellis eventually whispered: “Well, I don’t know how much I should say. Let me just say that you people did much more with it than we did.”

  Although GCHQ were 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 would never have revealed their work, thus blocking a form of encryption that would enable the digital revolution to reach its full potential. Finally, the discovery by the academics was wholly independent of GCHQ’s discovery, and on an intellectual par with it. 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.

  When Diffie told Hellman about Ellis, Cocks and Williamson, his attitude was that the discoveries of the academics should be a footnote in the history of classified research, and that the discoveries at GCHQ should be a footnote in the history of academic research. However, at that stage nobody except GCHQ, NSA, Diffie and Hellman knew about the classified research, and so it could not even be considered as a footnote.

  By the mid-1980s, the mood at GCHQ was changing, and the management considered publicly announcing the work of Ellis, Cocks and Williamson. The mathematics of public key cryptography was already well established in the public domain, and there seemed to be no reason to remain secretive. In fact, there wo
uld be distinct benefits if the British revealed their groundbreaking work on public key cryptography. As Richard Walton recalls:

  We flirted with the idea of coming clean in 1984. We began to see advantages for GCHQ being more publicly acknowledged. It was a time when the government security market was expanding beyond the traditional military and diplomatic customer, and we needed to capture the confidence of those who did not traditionally deal with us. We were in the middle of Thatcherism, and we were trying to counter a sort of “government is bad, private is good” ethos. So, we had the intention of publishing a paper, but that idea was scuppered by that blighter Peter Wright, who wrote Spycatcher. We were just warming up senior management to approve this release, when there was all this hoo-ha about Spycatcher. Then the order of the day was “heads down, hats on.”

  Peter Wright was a retired British intelligence officer, and the publication of Spycatcher, his memoirs, was a source of great embarrassment to the British government. It would be another 13 years before GCHQ eventually went public-28 years after Ellis’s initial breakthrough. In 1997 Clifford Cocks completed some important unclassified work on RSA, which would have been of interest to the wider community, and which would not be a security risk if it were to be published. As a result, he was asked 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 would know 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 innocuous. 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.