NY Times on history of public key crypto

[Anonymous <nobody@REPLAY.COM>]

      By PETER WAYNER
      
   T o the list of institutions that Tony Blair's Labor Party is shaking
   up, add the British Secret Service. Last week, the British
   government's eavesdropping organization known as the Government
   Communications Headquarters, or GCHQ, posted a document to its Web
   site describing its role in the discovery of public key cryptography.
   
   The set of algorithms, equations and arcane mathematics that make up
   public key cryptography are a crucial technology for preserving
   computer privacy in and making commerce possible on the Internet. Some
   hail its discovery as one of the most important accomplishments of
   20th-century mathematics because it allows two people to set up a
   secure phone call without meeting beforehand. Without it, there would
   be no privacy in cyberspace.
   
   The move by the once dusty and secretive organization is clearly an
   attempt to recast its image as a pioneering leader of cyberspace.

   For the last 20 years, the public gave credit for the discovery to
   Martin Hellman, a professor at Stanford University, and two graduate
   students who worked with him at the time, Ralph Merkle and Whitfield
   Diffie. They started publishing their work in 1976.
   
   Three professors at the Massachusetts Institute of Technology at the
   time, Ron Rivest, Adi Shamir and Len Adleman soon followed with
   another similar approach known by their initials, RSA, which went on
   to become one of the dominant solutions used on the Internet.
   
   Before public key cryptography, anyone who wanted to use a secret code
   needed to arrange for both sides to have a copy of the key used to
   scramble the data, a problem that requires either trusted couriers or
   advance meetings. PKC, as it is sometimes known, erased this problem
   by making it possible for two people, or more properly their
   computers, to agree upon a key by performing some complicated
   mathematics. There is no publicly known way for an eavesdropper to
   pick up the key by listening in.
   
   T he new document details how three employees of the British
   government discovered the same approach several years earlier, but
   kept it a secret for reasons of national security. A spokesman for the
   British government's GCHQ, said that the document's release is part of
   a "pan-governmental drive for openness" pushed by the Labor party.
   
   The document describing the steps of invention taken by the spies was
   written by James Ellis, a mathematician and cryptographer who died
   less than a month ago. In it, Ellis describes how he suggested the
   existence of what he called "non-secret encryption" in 1970s.
   
   Ellis says that Clifford Cocks followed with a more practical solution
   in 1973 that was essentially the same thing as the algorithm published
   by Rivest, Shamir and Adleman. The paper also says that Malcolm
   Williamson discovered an algorithm in 1974 that was very similar to
   the work of Diffie and Hellman. They did not replicate the work done
   by Merkle and Hellman.
   
   In a telephone interview from his office in La Jolla, Calif., Malcolm
   Williamson said that he felt bad when others discovered the solution,
   but concluded, "I was working at the British government and that's
   just one of the restrictions you work under when you work for the
   government."
   
   Hellman said in a telephone interview that he agrees. "It must be
   really difficult for them to watch other people get the credit," he
   said. "But that's the agreement they made when they agreed to work in
   secret." He was also quick to point out that the secret branches of
   the government have the help of large budgets and classified
   knowledge.
   
   "Diffie, I and Merkle were working in a vacuum." he said. "If we had
   access to all of the classified literature of the previous 30 years,
   it would really be an advantage."
   
   For his part, Diffie said in a telephone interview from Cirencester,
   England, that he thinks that GCHQ never realized the deep importance
   of what the mathematicians discovered. He said that he met James Ellis
   several years ago and "within an hour of meeting me, Ellis said, 'You
   did much more with this than we did.'"
   
   Diffie also suggested that the history of ideas is hard to write
   because many people often find solutions to different problems only to
   later determine they've discovered the same thing.
   
   T he story keeps going farther back. Recently, Matt Blaze, a
   cryptographer employed at Bell Labs, got a copy of a memorandum from
   the desk of John F. Kennedy about the problem of securing nuclear
   weapons with launch codes. Steve Bellovin, a colleague of Blaze's at
   Bell Labs, said: "When I read this memo, I don't see anything that
   would require public key cryptography. But I think they're in the
   neighborhood. For so many things, the answer is the easy part. Asking
   the question is the hard part. I think this got them asking the
   questions."
   
   Historians of science will certainly spend time sorting out the
   various claims. David Kahn, the author of the best selling history The
   Codebreakers, said that he recently asked the National Security Agency
   to declassify some documents so he could write the proper history of
   public key cryptography. He said an NSA staff member told him, "I've
   spoken to the guys who did this, but they don't want to be interviewed
   now." This suggests that the NSA also may have discovered public-key
   systems or had a hand in exploring them. Kahn hopes that the NSA will
   follow in Britain's lead so an accurate history can be written.
   
   Jim Bidzos, the chief executive of RSA Data Security, the division of
   the publicly traded Security Dynamics that holds the patent on the
   RSA, said that the announcement in Britain will have no effect on the
   company's business. Patent law is based on the notion that the
   inventors trade knowledge about the invention in return for an
   exclusive license to practice it.
   
   In fact, it is an interesting question to wonder whether Britain could
   have changed the history of cyberspace by disclosing the invention and
   encouraging the development of widespread cryptographic security for
   the public.

   This may have been a wise move during the height of the cold war in
   the 70's when there were thousands of Soviet tanks poised on the edge
   of western Europe. Williamson also hastens to note that mathematical
   equations weren't considered patentable in Britain at the time and
   without a patent anyone could have used the invention. The RSA patent
   in the United States was one of the first and it is generally accepted
   to have expanded the definition.
   
   Others are pushing a similar question. In a debate on cryptography
   policy at the University of Maryland, Baltimore County, John Gilmore,
   one of the founders of the Electronic Frontier Foundation, said the
   NSA should be more open. While national defense is very valuable, he
   suggested that the need for security in cyberspace for all citizens is
   going to be essential in the future.
   
   In the long run, the history of the discovery of public key
   cryptography is certain to be written and rewritten often in the next
   several years as more documents emerge from secret government
   laboratories. The spokesman from GCHQ promises that more documents are
   on the way.
   
   Hellman is philosophical. "In a way, these things are like gold
   nuggets that God left in the forest." he said. "If I'm walking along
   in the forest and I stubbed my toe on it, who's to say I deserve
   credit for discovering it?"
   
   He is quick to point out, however, that he shared the discovery with
   everyone.
     _________________________________________________________________
                 Copyright 1997 The New York Times Company