In conversation with Clifford Cocks

We chat to the crypto chief about inventing RSA… but not being able to tell anyone

post

Clifford Cocks

Throughout history, people have wanted to communicate in secret. But for a long time, the need for sender and recipient to agree on a way to encode their message (a ‘key’) meant that secure communication was costly, and mostly used by the military. But in the 1970s new mathematical ideas paved the way for public-key cryptography, a communication strategy that doesn’t rely on a mutually agreed key. If you’ve ever banked or shopped online then you’ve used public-key cryptography, most probably a type called the Diffie–Hellman protocol. (If you want to brush up on Diffie–Hellman, this is a great time to dig out Axel Kerbec’s article Hiding in plain sight from Chalkdust issue 09.) One of the lesser-known figures in the story of public-key cryptography is Clifford Cocks, a former chief mathematician at Britain’s GCHQ (the Government Communication Headquarters). Cliff’s relative anonymity is because, due to the secretive nature of his employer, his contribution was not made public for 24 years. We caught up with him via video call to find out what it felt like to have cracked the code, but kept it secret.

Finding the right factors

In 1973, Cliff Cocks had just joined GCHQ in Cheltenham. He had completed his undergraduate degree at Cambridge and had begun a PhD at Oxford, working in number theory, before deciding that academia was not right for him. One afternoon Cocks’ mentor at GCHQ, Nick Patterson, introduced him to the concept of public-key cryptography as a “really cool problem, but one that nobody had really got anywhere on.” The idea had first been conceived a few years earlier by James Ellis, another GCHQ employee, and the concept was simple yet groundbreaking. What if the intended recipient of the secure message (say, Alice) has two keys, a public one that she gives out freely to anybody, and a private key that nobody else knows. The sender, Bob, can use the public key to encrypt his message, then send it on to Alice, who can decode it using her private key. Since one needs the private key to decode the message, only Alice can read it, but her and Bob never have to agree on what the private key is. As Cocks puts it, “the two sides can have a secure conversation starting with absolutely nothing in common.” The issue that Ellis had faced was, how could this ‘asymmetric’ encryption work in practice?

Mixed paint

Multiplying large primes is like mixing paint; once it’s done it’s hard to undo it or to tell which colours were used. Image: Flickr user Rhian, CC BY 2.0

Cocks was intrigued by the problem, and found himself turning it over in his head at home that evening. He quickly made progress. “Luckily, Patterson had described the problem to me in a very mathematical way… I knew that what I needed was a mathematical function that was easy to do one way but hard to undo. I’d been working in number theory, so factorising seemed like something that could work.” Overnight, he had laid the groundwork for a feasible method. The basic idea behind Cocks’ method is that the private key is two large prime numbers, and the public key is their product (which Alice can easily compute). To decrypt the message, one needs to spot the original primes just by looking at the product. If the primes are large enough, then this is very hard to do.

With great modesty, Cocks describes his discovery as a case of being “in the right place at the right time, and having the problem explained to me in the right way.” He suggests that his freshness at GCHQ was an advantage: “I hadn’t quite realised how many people had worked on it in the past and not really got anywhere.” Some of those people who hadn’t got anywhere thought that Ellis’ unconventional idea was “crazy”, and that there had to be “some reason why it wasn’t possible”, and it wasn’t until Cocks approached the problem in a more mathematical way that any progress was made.

Once the work had been done, Cocks says he had no idea how significant it would prove. “In those days, cryptography was only really used by governments. Very few people were interested in it professionally outside that.” Of course, all of that changed with the internet and with the need to exchange encrypted information—in particular, information relating to online payments—between people that have never met. “I certainly did not foresee where technology would go in the future!”

Coming in from the cold

GCHQ were impressed with Cocks’ idea and shared it with their intelligence allies but, due to the secrecy of the organisation, it was never made public. A couple of years later MIT engineers Ron Rivest, Adi Shamir and Leonard Adleman independently came up with the same solution, and published their work in the journal Communications of the Association for Computing Machinery. The algorithm is now known as RSA in their honour, and is still one of the most widely-used encryption methods today. Astonishingly, the Diffie–Hellman protocol was also discovered at GCHQ in secret, by Malcolm Williamson, Cocks’ colleague and childhood friend.

In fact, GCHQ decided not to implemented Cocks’ idea at that time. “They thought very seriously about how to do it, but came to the conclusion, quite correctly at the time, that it was too expensive.” Ellis had originally conceived of public-key cryptography as a way to save money on the cost of sharing keys between senders and recipients, which was fast becoming the stumbling block to secure communication. “If you think about what computers were capable of at the time, (public-key encryption) would have to have been implemented on special-purpose hardware, and even then it would have been very slow. Given that the aim was to save money, it wouldn’t have been feasible.”

Fast forward to 1997, 24 years after Cocks first made the discovery. “I was going to give a talk in Cirencester, presenting some new idea about public-key cryptography. We thought inevitably there was going to be questions like ‘had I been involved in developing early versions of the algorithm?'” To avoid this speculation, it was decided that GCHQ would declassify Cocks’ work. After Cirencester, Cocks gave a talk to the British Society for the History of Mathematics. The story was picked up by the author Simon Singh, and it went on from there.

But how did it feel to finally ‘go public’? “I wasn’t sure how it was going to go. There’s some reassurance about being in the shadows.” Perhaps Cocks’ announcement was made easier by the fact that, for many years, rumours had been circulating about GCHQ’s work. “A lot of academics who I’d worked with would ask me the question, and it was a bit awkward really! So it was more about clearing the air.”

Not-so-secret communication

Cocks with a copy of Chalkdust issue 09.

Cocks with a copy of Chalkdust issue 09.

Although Cocks always maintained a close relationship with the academic world, he soon realised that there just wasn’t enough time to keep up-to-date with all of the relevant theoretical work. This is exemplified by the fact that he only learned of Rivest, Shamir and Adleman’s rediscovery of public-key encryption when he happened to read a feature on it in a copy of Scientific American one lunchtime. It’s for this reason—the need to bring in fresh ideas from academics with their finger on the pulse of current research—that he pushed hard to strengthen links between the intelligence community and academia during his time as chief mathematician, first sponsoring research positions at British universities and later setting up the Heilbronn Institute for Mathematical Research in Bristol, where academics spend half their time pursuing projects directed by GCHQ. As somebody who made the transition from university to government, he was keen that the institute was compatible with academia and “that there was the right balance of career development and providing pointers on difficult problems.”

There are, however, some important differences between working at GCHQ and a university. “GCHQ is much more collaborative, although academia is getting better. You don’t stand up in a seminar and say, ‘I’ve got this half-baked idea that I can’t make work’. But at GCHQ you want to get solutions, and you don’t really care if they’re yours, or a colleague’s.” And once you’ve solved the problem, there’s no chance of getting public recognition for it (at least, not for a few years). “The focus of what you do is internal, but it’s not like we’re going to solve the Riemann hypothesis and keep it to ourselves. It’s more about the applications.” So learning to give up the glory, and in particular to share work that isn’t finished, is something that academics need to be trained to do when they make the move into intelligence. But there are some positive aspects to the secretive life of a GCHQ employee. “You can’t take your work home with you, so there’s a separation between work and home life. Well, apart from those problems that stick in your head and you can’t get rid of them!”

Hinged Old History Padlock Building Rusty Door

Public-key cryptography has made online security possible.

Does Cocks ever wonder what his life would have been like if he’d continued with his PhD at Oxford, working on elliptic curves under Bryan Birch? “It’s interesting to speculate. It certainly would have been a slower career.” Upon leaving Oxford, GCHQ seemed like a natural choice for a job, being one of the only places that recruited people to do “something approximating pure mathematics”. His decision to leave his PhD was prompted by the realisation that, in his field of number theory, it would have taken a lot of work until he could start doing something ‘useful’. “I didn’t want to spend three years just getting to the coal face.” Having come up with a solution to public-key encryption within six weeks of starting his new job, it’s fair to say that he had cracked that coal face wide open, and taken the first peek at a rich seam that is still being mined today.

Sean is a PhD student researching geophysical fluid dynamics at UCL. He studies coastal outflows, but so far has been unable to persuade the department to send him on a research trip to the beach.
@sean_jamshidi    + More articles by Sean

More from Chalkdust