Originally created 02/14/98

Can a secret code stay secret?



Can a secret code be public and still stay secret?

It can. And it exists. Called public-key cryptography, the system makes practical secret communication among the multiple users of the Internet. In a recent memo published on the Net, a Briton claims to have been the first to propose the basic idea back in 1970.

The invention had been attributed to two California computer engineers, Martin Hellman at Stanford University and his student Whitfield Diffie, now at Sun Microsystems, who wrote an article in 1976 setting forth the public-key cryptography idea. But at a computer-security conference in San Francisco Jan. 12, Diffie publicly acknowledged the British priority. (The Americans' idea was independent of the Briton's.)

James H. Ellis, a cryptographer at the United Kingdom's code-making and -breaking agency, Government Communication Headquarters in Cheltenham, England, wrote that he got the idea while lying in bed one evening in 1969. He was trying to resolve the logistical problem of how to provide secret keys to each of the many communicators on a cryptographic net. He explained his idea in an internal report of January 1970.

When he died a few weeks ago, the U.K. agency issued his memorandum as a testament to "his imaginative and groundbreaking work." It was posted on the Internet Dec. 17 at www.cesg.gov.uk/ellisint.htm.

Public-key cryptography, which makes secrecy practical in cyberspace, also permits such seemingly impossible activities as long-distance electronic contracts. It does this in part by eliminating the essential need to have a secret channel, such as a trusted courier, to distribute keys between people before any secret communication can take place between them. (If such a channel were necessary, secrecy betwen the millions on the Net would be all but impossible.)

Public-key cryptography uses two keys for each person. One is public and can be used by anybody to send a secret message to someone else. The other key, held by that someone, is private and deciphers the message.

The two keys are related mathematically. But knowledge of the encrypting key does not enable third parties to ascertain the decrypting key and so solve the message. This differs from older forms of cryptography. In them, knowing the encrypting key means knowing the decrypting key, thereby enabling a third party who knows the former to read a message.

An analogy may explain how this works. The English half of an English-French dictionary to encode messages for one person, say, Alice, lies on a table for anyone to use. Bob uses it to put a message into secret form (translated into French) for Alice. Alice alone has the decoding book, the French half of this dictionary, so only she can decipher Bob's message, from French to English. Anyone else may use the English half to send a secret message to Alice. Other books on the table encode in different languages, so any pair can communicate secretly without prearrangement.

More importantly, public-key cryptography can authenticate messages, which was never before possible with electronic communications without prearrangement. If a sender encrypts a message with his private decrypting key, the recipient, who reads it with the sender's public key, can be sure that only that person could have encrypted the message. Likewise, the sender cannot repudiate the message, because only he knows the private key that encrypted it.

Public-key also makes possible other capabilities never before available, such as authenticating electronic purchases and long-distance contracts mathematically signed. It has revolutionized cryptography and has been called the most important invention in the field since the millennia-old creation of the two basic forms of cipher, substitution and transposition.

Can the messages be cracked? Not in practice. Solving the most widely used public-key system, the so-called RSA, is equivalent to factoring a huge number, up to 200 digits long, which would take eons, even with many modern computers working together.