The Open Secret

Public key cryptography - the breakthrough that revolutionized email and ecommerce - was first discovered by American geeks. Right? Wrong.
The story of the invention of public key cryptography is a cypherpunk sacred text: In 1976, an iconoclastic young hacker named Whitfield Diffie hooked up with Stanford professor Martin Hellman, and together they devised what experts hailed as the most important development in crypto since the invention of polyalphabetic ciphers during the Renaissance. The duo produced a system that allowed an unlimited number of people to communicate with total privacy. A year later, three MIT mathematicians implemented the Diffie-Hellman theory, developing the landmark RSA algorithm, the mathematical formula that made public key feasible. Published in a landmark MIT paper and hailed by Scientific American, these capabilities would turn out to be a vital step in making network communications secure, and became a bulwark for personal privacy as the Internet grew. Like a lot of mythic accounts, this one turns out to be well off the mark. The problem lies not in its veracity, but in what the story leaves out. In fact, the situation is a little like a Hollywood remake of a foreign cult film. In this case, though, no one knew the earlier version existed - that the plot had been changed and characters replaced - because it was never released and the negatives were buried. The truth has emerged only because the surviving stars recently got permission from their "studio" to talk.
James Ellis, a British spook, hit upon the secret of public key crypto in the late '60s - but couldn't tell anyone. So roll back the time frame to a few years before the Diffie-Hellman/RSA saga. Change the setting from MIT and Stanford, places where you can nearly get sunburned from the heat of new ideas, to a cloistered British intelligence agency in the sleepy Cotswolds city of Cheltenham, about 100 miles from London. Instead of the famil- iar cast - a dashing hacker, his academic collaborator, a tight-knit team of mathematics researchers - imagine three nearly anonymous British civil servants laboring in the kind of obscurity possible only in the intelligence community's shadow world. One of the three - an engineer, not a mathematician - has been given what looks like a sidetrack assignment to solve a problem no one thinks can be solved. Mulling it over while in his pajamas one night, he has a startling insight, but he's not sure his math skills are strong enough to unravel its implications. Enter two Cambridge University math grads who have quit advanced-degree programs and come to work in the world of spooks because - well, because they need a job. Friendly rivals since they were schoolboys, they're fellow lodgers who, ruminating in their off hours, separately happen upon algorithms that would make the engineer's idea fly (the same algorithms published to astonishment and acclaim by the Americans a few years later). Then, after their agency tries and fails to knock down their work, it decides to sit on the findings and stay on the sidelines - even when the American discovery of public key touches off a cryptographic and commercial revolution. During the late '60s, intelligence agencies were giving much thought to the fast-breaking developments in computers and wireless technologies, and to ways to protect government data that traveled over these channels. While encryption hardware was evolving, one crucial part of the process hadn't changed since World War I: the need to distribute and use digital keys to scramble and unscramble messages. The process was a bottleneck. To ensure security, a unique key had to be generated for every pair of people who needed to conduct secret conversations; then those keys had to be delivered securely. Thousands of people were in the classified loop, and that meant generating millions of keys that needed to be protected. Managing the system was, to put it in a very un-British way, a bitch. At the UK's Government Communications Headquarters - a government spy bureau that is the rough equivalent of the US National Security Agency - senior scientist James Ellis was working on the problem. Ellis, an orphan who had been raised by his grandparents in London's East End, had joined the GCHQ in the '50s, then left for a time to work (presumably on security issues) at the post office. By 1969, in his 40s, Ellis was back at the GCHQ and, as part of its Communications-Electronics Security Group, was hunting for a way past the seemingly intractable conundrum of key management. It is difficult to peer into the office politics of his world, and doubly so at a distance of 30 years. Still, it's clear that this assignment placed him neither at the white-hot center of international intrigue nor at the forefront of research. "I think he was sort of sidetracked," a colleague says. Ellis had his doubts about finding a solution to the problem. "It was obvious to everyone, including me," he later wrote, "that no secure communication was possible without a secret key, some other secret knowledge, or at least some way in which the recipient was in a different position from an interceptor. After all, if they were in identical situations, how could one possibly be able to receive what the other could not? Thus there was no incentive to look for something so clearly impossible." But then Ellis came across a paper buried in the GCHQ's mountain of secret material. Written by an anonymous author, it described a project conceived by Bell Telephone toward the end of World War II. The scheme, labeled Project C43, was an ingenious method of analog voice scrambling that worked by the use of distortion. To conceptualize it, imagine you want to send a message over the phone line and you suspect someone is listening. How can you keep the message secure? The Bell scientist suggested that the person receiving the message simply add noise to the line. When the message arrives, message and noise are intermingled and eavesdroppers will hear only garbage. The recipient, knowing precisely how the noise was added, can subtract it from the transmission and wind up with the original, unscrambled message.
At GCHQ, disproving Ellis's heretical thesis would be striking a blow for the natural order. For modern cryptography, Project C43 was useless. For one thing, it was an analog model, and by the late '60s the world was going digital. But Ellis found it exciting nevertheless: The sender of a message didn't have to worry about an enemy listening in, even if the foe knew how the system worked. What made this possible was that, in contrast to conventional cryptography, the recipient is a collaborator in the encryption. "Secure communication," Ellis wrote, "was, at least, theoretically possible if the recipient took part in the encipherment." That raised a tantalizing question for Ellis: Could a secure, digitally encrypted message be sent without keys being exchanged in advance? This heretical idea popped into his head one night after he had gone to bed. Sitting in the dark in his Cheltenham bedroom, he decided it could, and he came up with an existence proof for the question. His name for it would embody the contradiction: nonsecret encryption. It worked by taking the digitized, nonsecret exchange between two parties - call them Alice and Bob - and submitting it to a series of three mathematical alterations. Let's say, for instance, that Bob wants to send a message to Alice. The problem is Eve, an unwelcome snoop who is familiar with the way this particular scrambling system works, down to the mathematical formulas themselves - since these rules are, in this scenario, public knowledge. Alice gets the ball rolling by generating a large number chosen at random. This, in effect, is a secret key that only she holds. Now comes a crucial act suggested to Ellis by Project C43: Alice, who is the intended recipient, actually initiates the scrambling process by executing a mathematical operation to transform the key to a new number. She sends the new number to Bob. The new number is analogous to what we know as a public key. Since an important property of the mathematical operation Alice uses is that it cannot be calculated in reverse, even by an outside observer who has this second, nonsecret number, and also knows what function produced it, cannot do an inverse calculation to retrieve the first, secret number. This is something that will remain known only to the recipient, Alice. Now that Bob has this nonsecret number, he uses a second operation to scramble the private message he has for Alice, which he then sends. With a third mathematical function, Alice uses her original, secret key to essentially strip the encryption from the message. She can now read the plain text, and Eve can do nothing but gnash her teeth as she watches a very public exchange of what, to her, will remain gibberish. The nonsecret key acts like the line noise in Project C43. Since such keys wouldn't have to be protected, it would be possible to have secure communications without all the prior arrangements necessary in conventional crypto, opening the way for protected communications on a vast scale. Ellis hadn't been assigned to unleash a revolution in cryptography, but the possibility that he had done so had to be dealt with. The very basis of the idea - its "nonsecret" element - seemed so heretical that, to some at the GCHQ, disproving his thesis would be striking a blow for the natural order of things. In July 1969, a draft of Ellis's paper - which, naturally, was classified - was sent to the GCHQ's chief mathematician, Shaun Wylie. Just before Christmas, he delivered his judgment: "Unfortunately, I can't see anything wrong with this." However, the mathematician noted, Ellis had presented only a proof that such a system could exist. The unknown remained: Was there really a way of generating a nonsecret key from the original private key? To make it work, you needed to be certain that the Eves of the world could not reverse the first mathematical process and get their hands on the key. Ellis had conjectured a set of lookup tables that would perform the various scrambling and descrambling calculations but had not developed the specific functions. Until they were formulated, nonsecret encryption would be nothing more than a theoretical curiosity. Ellis did not hide this state of affairs when he formally wrote up his idea in a January 1970 internal paper called "The Possibility of Secure Non-Secret Digital Encryption."
Clifford Cocks realized that big primes were the key to public key. "It is necessary to distinguish carefully between fact and opinion, i.e., between that which has actually been proved and that which seems likely," he wrote. "It is particularly difficult to do this in this case because we have established something which, to most people, seems inherently impossible." The remaining step in the creation of a secure, nonsecret key was not trivial. Even as he set about the search for the nonreversible functions that would make his scheme work, Ellis, an engineer by training, was concerned that his mathematics skills were not up to the task. And despite the possible importance of a nonsecret system, the GCHQ did not assign much brainpower to aid him in the quest. At times over the next few years, some Communications-Electronics Security Group cryptographers would read Ellis's paper and work for a while on potential solutions, and in 1971 a new chief scientist took an interest and assigned some people to the problem. But while those looking for the mystery functions developed ideas about what the characteristics of such things might be, they had no luck in actually finding one that worked. Then Clifford Cocks came along. In 1973, Cocks was a recent arrival in the electronics-security group. He had come to intelligence work from Kings College, Cambridge, where he earned an undergraduate degree in math, and Oxford, where he did graduate work in number theory before deciding to move on. Although Cocks didn't know much about the GCHQ and really hadn't thought about cryptography as a focus of his work, he knew the agency needed mathematicians. Also, a childhood friend, Malcolm Williamson, was already there. In September of that year, at age 22, Cocks went to work in Cheltenham. When people arrived at the GCHQ, they were assigned a mentor "to teach you the ropes and tell you what you needed to know," Cocks recalled in a recent lecture. His was Nick Patterson, another Cambridge alumnus. One day at teatime, about two months after Cocks's arrival, Patterson mentioned Ellis's idea to his protégé. "Nick explained it to me very mathematically, in terms of wanting a nonreversible function, with a property where you could encrypt and decrypt with the input of this function," Cocks said during his lecture, adding that not reading Ellis's paper before the conversation was an advantage. That allowed him to consider the problem without preconceptions. Since he had done his research the previous year in number theory - working with large primes and multiplication - it made sense to him to use that knowledge. "I suppose it was actually also helpful that I wasn't doing anything that evening," Cocks added blithely. After work he walked back to the modest house he rented in Cheltenham with Williamson, ate dinner, and sat down to think. Because of the secrecy imposed by the GCHQ, he had certain limitations: He could not bring anything home from his office, and if he pondered a work-related problem "in digs," he was not permitted to write anything down. The only medium he had was his brain. "Happily," he said, "the first idea seemed to work just fine." His idea was more than fine - it was elegant. "If you wanted a function that couldn't be inverted," he now says, "it seemed very natural to me to think of the concept of multiplying quite large prime numbers together." Cocks is pointing to a basic mathematical truth: The product of two large prime numbers is extremely difficult to factor - that is, to reverse to obtain the original primes. He figured that the secret key in his implementation would be two huge primes, generated by a message recipient. The primes would be multiplied, and the product would be the nonsecret key, the number given openly to a sender (who could, if need be, also get the number from a public directory). Cocks then figured out a simple mathematical formula that would allow the sender to encrypt a message in such a way that it could be decrypted only by someone who knows the original primes. "This is very interesting," Cocks remembers thinking. After mapping it out in his head, he went to sleep. "I went back to work the next morning and wrote it down," he recalls. Cocks, in one evening, had achieved a breakthrough that several years later would be repeated - in the form of the revolutionary RSA algorithm - after months of intensive trial and error by MIT researchers Ron Rivest, Adi Shamir, and Len Adleman.
Malcolm Williamson worried that such a "simple" scheme was vulnerable to attack. Word got around the electronics-security group that someone had found a way to implement James Ellis's idea. Cocks mentioned to his friend Malcolm Williamson that he had an internal paper coming out. This was a one-up move; it was unusual for a recruit to circulate a paper so soon. Cocks's announcement got Williamson's attention; he listened closely as Cocks explained the problem and his solution. Williamson had known Cocks since they were both 12 - they had attended the same grammar school in Manchester, and they had both gone to Cambridge. Williamson had done graduate work at Liverpool University, then one day saw an ad, posted by the GCHQ, calling for mathematicians. Without knowing much about the agency, he had applied - and soon found himself working on cryptographic problems. Williamson had not heard of the Ellis problem before, but it struck him as rather unreasonable. How could you do cryptography when you passed the key in the open? So he set about to shoot down the concept, but he couldn't. "I didn't manage to prove that there were any flaws in what he had," he recalls. But in the process, Williamson began considering ways that two collaborating parties could pass numbers back and forth to build a shared key that would be secure even if an eavesdropper was monitoring every bit of the exchange. It was very late when he got it - 8 or 12 hours after he sat down to think. His scheme involved a complex set of exchanges in which each party picks a random number, performs a calculation on it by a difficult-to-reverse formula, and arrives at a shared key. It's indicative of the project's relative unimportance at the GCHQ that Williamson didn't write up his work for a couple of months. Not long after he did, and after some conversations with Ellis, he came up with an idea that streamlined his concept. It was precisely the same formulation for what would later be known as the Diffie-Hellman algorithm. As far as Williamson is concerned, though, it was pretty much a consequence of his first paper, so obvious that he felt in no hurry to circulate it. "It really didn't feel like such a big step," he says. Now the GCHQ had two means of implementing Ellis's heresy. But just as the agency had been suspicious of the initial idea, it moved ultracautiously with Cocks's and Williamson's schemes. Ironically, one factor weighing against accepting the solutions was their sheer straightforwardness. "There's a basic principle that neat and tidy problems have neat and tidy solutions and messy problems don't have neat and tidy solutions," says Williamson. "Most of cipher design is essentially messy; it's not neat and tidy and mathematical. So we're pretty comfortable that people are not going to be able to break those things, because even if you hack away at it, you're not going to suddenly find a little magic screw there that, if you unscrew it, everything falls to pieces. But in all this stuff with public key, there absolutely may be a magic screw. Some graduate-student mathematician could really cause a disaster." So concerned was the GCHQ with this possibility that it not only looked at the schemes internally - finding no inherent flaws - but also took the unusual step in 1974 of going to a renowned outsider, Professor R. F. Churchhouse of the University of Wales, presenting him with the mathematical foundation of Cocks's idea, and asking whether it was secure. Churchhouse concluded that as long as no one figured out a fast way of factoring huge primes - something that no mathematician had ever come close to - the scheme was sound. The agency ultimately determined that between the two methods, Williamson's was preferable because its functions were easier to work with than the huge numbers Cocks's scheme required. Even so, the system was judged to be impractical. "The machines that would be used were expensive and very slow," explains Cocks. "It took minutes to generate a key. We looked at the circumstances under which you would find it useful to have a machine that took that long to produce keys and immediately thought the applications were too limited to make it worth floating." So the GCHQ's thinking had advanced from judging nonsecret encryption to be impossible to finding it overly cumbersome. Many people in the agency also remained concerned that such a radically new kind of cryptography might have weaknesses too subtle to detect, weaknesses that an enemy might use to crack the system.
Cocks's breakthrough was repeated, years later, after months of intensive effort at MIT. Even Williamson believed that the whole venture was too risky. When he finally wrote up a revised version of his key scheme, he cited these reservations as the reason for the two-year delay. "I find myself in an embarrassing position," he wrote. "I have come to doubt the whole theory of nonsecret encryption. The trouble is that I have no proof that the method ... is genuinely secure." He conceded he could not find anything wrong with the system, though, "and would be grateful if anyone else can." No one did. But by then the GCHQ had tacitly concluded it wasn't worth the effort to implement a public key crypto system. In 1976, of course, Diffie and Hellman presented their findings in two papers, which were followed in 1977 by a famous paper about RSA publicized by Scientific American. These developments made a huge splash; the news even found its way into the popular press, and the public key discoverers were widely heralded. One can only imagine how weird this all must have been for Ellis, Cocks, and Williamson, who could never, outside the walls of the GCHQ, even hint at what they knew about nonsecret encryption. Cocks says that when Ellis read Diffie and Hellman's first paper, which outlined the public key idea but suggested no implementation, he said simply, "They're where I was in 1969." The Stanford team's second paper did suggest a means of implementation - identical to the Williamson solution. Cocks had temporarily left the GCHQ for a stint at the Ministry of Defense and first learned of the Americans' work in Martin Gardiner's Scientific American column in mid-1977 - the one describing the RSA algorithm Cocks had first discovered three years earlier. He says, with some understatement, "I was surprised." In 1977, the British cryptographers were upset to learn that both Stanford University and MIT were planning to patent, respectively, the Diffie-Hellman and RSA algorithms. "I tried to get them to block the US patent," Williamson says. "We could have done that, but in fact the people higher up didn't want to. Patents are complicated." Specifically, there was a question as to whether one could obtain a patent under British law for what was essentially a mathematical algorithm. "The advice we received was, 'Don't bother,'" says Cocks. That stance apparently condemned the intelligence establishment - in the UK, at least - to the role of bystander during the cryptographic revolution Diffie and Hellman had sparked. The GCHQ and the NSA would eventually come to take public key seriously, but they no longer held their crypto monopoly. A new community of cryptographers, not bound by government constraints or prejudices, quickly began a process of furious innovation that would transform cryptography from a tool of secrecy to a technology of privacy. Chief among the developments that grew out of public key cryptography was the ability to authenticate message senders with digital signatures. There followed ideas for digital cash, including a system that preserved a spender's anonymity, just as with actual money. There were schemes for "secret sharing," in which information is divided among several people in such a way that it can be recovered only by consent of a given percentage of the keyholders. There were digital-certificate systems that allowed identities to be verified online or through smartcards. There were systems for digital time-stamping, electronic receipts, and all sorts of ecommerce activities. As a result of these efforts, public key is now ubiquitous, on every copy of Netscape and Lotus Notes - and may one day wind up in everyone's wallet as smartcards. It's easy to fault the intelligence community for not pursuing the development of nonsecret encryption, but from a national-security standpoint, its cautious approach was understandable. Using an untried technique to protect government secrets posed a risk. One of nonsecret crypto's inventors still makes this point. "The government has to be very cautious," says Williamson. "It's much more important to secure some of this stuff than, say, banking transactions or Internet communications, or what the next-model Ford is going to look like. If I were on the top of the pyramid then, would I have dared to implement it? What was the chance that somebody would find that magic screw that unlocks everything?" In the final reckoning, nonsecret encryption was too much a departure from what was known. "You've got to remember," says Williamson, "this is the civil service. I mean, this is something new and different. 'Let's ignore it. Let's sweep it under the carpet.'" A quarter of a century after they did their big work, the British trio insist that they didn't feel shortchanged when they saw others get all the credit for ideas they had come up with themselves. "Ellis got internal recognition," says Cocks, who himself is perfectly comfortable with his anonymity. "You accept that. Internal recognition is all you get."
The UK intelligence establishment's stance of secrecy condemned it to a spectator role during the cryptographic revolution. Of the three, only Ellis took steps to bring his work to public attention. In 1987, he wrote a paper directed to outsiders outlining how he had hit on the idea of nonsecret encryption. For anyone thick enough to have missed his point, he closed the paper by noting it was "some time after the basic work had been done" that Diffie and Hellman made what he called the "rediscovery of the NSE techniques." But the GCHQ classified his account and kept it secret. Williamson suggests release of the true story was held up by one official. The material was all ready to go, he says, but could not be published "until a certain person retired." Apparently, the "certain person" eventually left government service. In late 1997, the Communications-Electronics Security Group posted on its Web site Ellis's 1987 history along with the earlier papers he, Cocks, and Williamson had written. (The papers are available at www.cesg.gov.uk/about/nsecret.htm.) Some weeks earlier, on November 25, James Ellis had died. In 1979, National Security Agency chief Bobby Inman publicly stated that, all the noise about Diffie-Hellman and RSA aside, the intelligence establishment had known about public key cryptography for some time. To Diffie, the suggestion that someone, somewhere had discovered public key before him had long been troublesome, and he tried to find out what Inman meant. In the early '80s, he finally pried two names out of an NSA source: Clifford Cocks and James Ellis of the GCHQ in Cheltenham. At the time, Diffie was employed by the research affiliate of Canada's Northern Telecom. Working through a couple of connected associates, he asked to meet with Cocks and Ellis. Only Ellis agreed. They met in the fall of 1982 - more than six years since Ellis's discovery and almost a decade since Diffie had independently come up with the same idea. Ellis lived on a hill on Cheltenham's outskirts and had a beautiful view of the town. He raised bees in the backyard. The GCHQ senior scientist was in his late 50s - a tall man, going gray. After some small talk with Ellis and his wife, Diffie and his fellow cryptographer headed for a pub.
Diffie turned to Ellis as they pulled out of the driveway. "Tell me," he said, "how you invented nonsecret encryption."
"Who says I did?" Ellis asked.
Diffie said the name of his NSA source.
"Do you work for him?" asked Ellis. Diffie said he didn't. At the pub, as Diffie got tipsy, Ellis - a solid GCHQ man - talked about anything but the subject Diffie most wanted to discuss. Still, the meeting was the beginning of a long friendship between the Diffie and Ellis families. It was a relationship in which Diffie's wife, Mary Fischer, sensed something wistful in a man who never got credit for his truly revolutionary insight.
Thinking back to their first meeting, Diffie says that Ellis made a telling statement, one whose very obliqueness speaks volumes about the world he lived in as a spy. The British spook said it on the way to the pub - a seemingly random confession that stood out in contrast to the polite evasions that were Ellis's standard form of reply. Public key cryptography? "You did a lot more with it than we did," he said. Then he said no more. The nonsecret secret would stay a secret for the rest of his life.