Public key cryptography is widely used to secure online transactions. The maths behind the technology was invented by UK Government Communications Headquarters scientists in the late 1960s and early 1970s.
The discovery was kept secret to avoid revealing how closely Government Communications Headquarters (GCHQ) was working with the US National Security Agency (NSA) at the time. The breakthrough by GCHQ scientists James Ellis, Clifford Cocks and Matthew Williamson only came to light in 1997, when their work was declassified.
In public key cryptography, data is encrypted using a widely distributed public key, and can be decrypted using a private key. GCHQ mathematician Clifford Cocks, who invented the practical method of public key cryptography in 1973, and Ralph Benjamin, who was GCHQ's chief scientist from 1971 to 1982, told ZDNet UK about their pioneering work.
Q: How did you identify the need for public key cryptography?
Ralph Benjamin (pictured on left): At the time it was not self-evident by any means. When I became GCHQ chief scientist in 1971, I was briefed by Dr Gerald Touch, my predecessor, that, two years previously, James Ellis had produced papers about what [Ellis] called 'non-secret encryption'. Touch had consulted Hugh Alexander, the head of cryptography and Shaun Wylie, the chief mathematician, and I believe Denis Mardle, who was designated to succeed Wylie, and they said 'non-secret cryptography' was garbage.
James Ellis had previously done good work, developing his insights by instinct, with limited capability of explaining how to get them by rigorous logic, and hence Touch wondered whether there was something in Ellis's proposition after all.
I had been director of research, Admiralty Surface Weapons Establishment, and director and chief scientist, Admiralty Underwater Weapons Establishment, so I didn't have any preconceived ideas or prejudices about cryptology. Touch and the three people he had consulted had spent 30 to 40 years in a community which for centuries thought that encryption and decryption were equal and opposite — it was doctrine.
James Ellis's was a philosophical presentation claiming that encryption and decryption could be completely different processes — people could use a public key to send their messages, which only you can decrypt. Ellis's second paper discussed the mathematical requirements to achieve this, but had no practical suggestions to offer. I got the kernel of Ellis's idea, and I went to Nick Patterson, and said, "Can you look at this and devise a suitable function?" In due course, Patterson came back with Cliff Cocks with a viable option.
Encryption had existed for decades with progressive enhancements. There had been dramatic enhancements within the decades with computer technologies and the need for higher security. All through that period, that encryption and decryption were opposites was a certainty. Non-secret encryption, which came to be known as public key cryptography, was quite revolutionary.
Clifford Cocks (pictured on right): Encryption had been done like that for centuries. James [Ellis] had come up with the concept to say you didn't have to do it this way. People weren't sure, which shows the extent of the revolution.
RB: It was revolutionary in the intellectual schema, and eventually in its operational impact. We didn't then foresee the full eventual operational impact. My conclusion was that the process would be so cumbersome, especially considering the computing ability of the time, it might have been useful for the occasional short message, but its main use would be a short message to transmit a key for conventional cryptography.
I judged it most important for military use. In a fluid military situation you may meet unforeseen threats or opportunities. To cope with threats or exploit opportunities you have to quickly reconfigure your forces, so they are in a position to form an effective task group. You can't do that unless you share secure communications. This means...
... if you can share your key rapidly and electronically, you have a major advantage over your opponent.
Only at the end of the evolution from Berners-Lee [in 1989] designing an open internet architecture for CERN, its adaptation and adoption for the Arpanet for networking with universities, and then fibre-optic and satellite communications permitting the concept to spread to the internet and world wide web — and its use for financial transactions — did public key cryptography realise its full potential.
CC: Public key cryptography is increasingly significant for financial transactions over the internet. Public key infrastructures have much promise but are proving more challenging than you might think.
Q: How long did it take from the publication of Ellis's idea to a working model?
CC: There was quite a gap. James published in 1969 and 1970, and I didn't join GCHQ until 1973. During this time various people had looked at it, and I was briefed by Nick Patterson. When I joined, Nick was supervisor, and I was fortunate that Nick explained the problem in mathematical terms. James's work was not the easiest to find out what was going on.
Q: How did you think of the method?
CC: My thinking was that you need something that is easy to do, and difficult to undo, so I thought of the product of two primes. It's essential that you have a one-way function which can only be inverted if you know the factors — and raising numbers to a power with the product as modulus is something you can unpick only if you know the factors.
Q: How long did it take, and did you use any technology to help you?
CC: It was done in my head overnight.
Q: Did you write it down?
CC: No, I kept it in my head and hoped to remember it in the morning.
Q: How closely was GCHQ working with the NSA at the time?
RB: GCHQ had a close two-way working relationship with the NSA. We immediately passed on the non-secret encryption process to them, and the secret of how to do it. We had produced an algorithm that demonstrably worked. This produced enormous professional excitement in the cryptography community. They [the US] probably appreciated the military concept less than we.
Q: Was there a link between GCHQ passing 'non-secret encryption' algorithms to the NSA, and researchers at Stanford having success at public key cryptography research?
RB: NSA, like GCHQ, were working on signals intelligence and communications, or more generally data security. In terms of data security, the aim was to get a more secure computer design. NSA collaborated with Stanford and MIT to develop a secure computing architecture. There was a steady flow of people travelling between Fort Meade [NSA headquarters] and Stanford as part of the project. Our 'non-secret encryption' was then such a lively subject of discussion at NSA that it would be surprising if some hint of our line of thought had not been inadvertently passed to Stanford, thus stimulating them independently to develop the same ideas and algorithm in their 'public-key cryptography'. However, I certainly do not believe that there was any deliberate leakage by NSA or any conscious plagiarism by Stanford.
Q: What happened to the research into secure computing architecture?
RB: Computer manufacturers in America got fed with the conclusions of this research, and computers couldn't be approved for government use unless they conformed to the secure architecture [specifications], and they could prove they weren't emitting Tempest radiation [that could be intercepted].
Q: Did GCHQ make use of public key cryptography in the 1970s?
CC: In the 70s public key cryptography was too expensive. Even the American work wasn't used. All of the ideas were well ahead of their time. No one was implementing public key cryptography in the 70s. The UK government didn't use it until the late 1980s with the [CESG-developed] Brent telephone. By the time things were implemented, public key cryptography was quite a mature subject.
Q: Your work wasn't officially acknowledged until 1997, and IEEE recently marked the GCHQ invention of public key cryptography with an award. Would it have been good to get recognition at the time of the invention?
CC: GCHQ gives recognition largely internally. People do feel very happy who they are working for.
RB: The NSA nominated me for the top US civil award, but this was vetoed by the Foreign Office because this would have revealed our close association with the NSA at the time. The NSA later presented me with a special medal to show their admiration. The value of GCHQ is recognised within government, but there is reluctance to give publicity too. A lot of work GCHQ can't publicise.
CC: It's very nice and gratifying when you have recognition [from a body like IEEE].