The Code Book (48 page)

Despite his skills as a codemaker, Ellis was never put in charge of any of the important GCHQ research groups. He was brilliant, but he was also unpredictable, introverted and not a natural team worker. His colleague Richard Walton recalled:

He was a rather quirky worker, and he didn’t really fit into the day-to-day business of GCHQ. But in terms of coming up with new ideas he was quite exceptional. You had to sort through some rubbish sometimes, but he was very innovative and always willing to challenge the orthodoxy. We would be in real trouble if everybody in GCHQ was like him, but we can tolerate a higher proportion of such people than most organizations. We put up with a number of people like him.

Figure 66
James Ellis. (
photo credit 6.4
)

One of Ellis’s 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’s 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.

The cost of key distribution was already enormous, and would become the limiting factor to any expansion in encryption. Even a reduction of 10 per cent in the cost of key distribution would significantly cut the military’s security budget. However, instead of merely nibbling away at the problem, Ellis immediately looked for a radical and complete solution. “He would always approach a problem by asking, ‘Is this really what we want to do?’ ” says Walton. “James being James, one of the first things he did was to challenge the requirement that it was necessary to share secret data, by which I mean the key. There was no theorem that said you had to have a shared secret. This was something that was challengeable.”

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.

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.”