Cryptography Breakthrough Is 100th Milestone

Public-key cryptography receives its due

7 June 2010
tech Photo: Amanda Rohde/iStockphoto

Every time you buy something online, you can thank public-key cryptography for the security of the purchase. The 1970s breakthrough made possible safe communications and e-commerce, and it laid the groundwork for the digital revolution.

Public-key cryptography uses asymmetric algorithms in communications devices such as computers and mobile radios to encrypt and decrypt messages. The algorithm on the sender's end uses a code, or key, to encrypt a message, and the recipient uses a different key to decrypt it—hence the description "asymmetric."

But who is to thank for inventing the technology? The answer is not so straightforward. Many have credited a group of researchers at Stanford and MIT who made the discovery in 1975. Those Stanford researchers, Whitfield Diffie, Martin Hellman, and Ralph Merkle, are this year's recipients of the IEEE Richard W. Hamming Medal for their work on public-key cryptography.

But in the early 1970s, British researchers James Ellis, Clifford Cocks, and Malcolm Williamson secretly invented public-key cryptography while working at a British intelligence agency, the Government Communications Headquarters (GCHQ), in Cheltenham, England.

For decades their work went unknown. It was declassified in 1997. Ellis died shortly before he could enjoy the public recognition.

To make sure the inventors receive their due, a group of IEEE members from Region 8 nominated the invention by Ellis, Cocks, and Williamson for an IEEE Milestone in Electrical Engineering and Computing, IEEE's 100th.

SECRETS AND SPIES
Cryptography was once mostly used by companies to protect business confidentiality, by intelligence agencies coding their own messages and trying to decode intercepted phone and radio messages from other countries, and by military commanders during war to communicate orders to their troops.

Prior to public-key cryptography, the security of all encrypted messages depended on the exchange of a secret key, contained in a codebook, for example, that was in the possession of both the sender and the recipient. The challenge was getting the sender and receiver to agree on a secret key from among many possibilities in the book—without anyone else discovering it. If they were in separate locations, they entrusted a courier, a phone system, or some other transmission medium to share the secret key. Anyone who intercepted the key in transit could use it to decrypt the messages.

The vulnerability of those methods, as well as the high cost and inconvenience of sending the keys securely, led intelligence agencies in the late 1960s to seek alternatives. Most researchers studying cryptography at the time, however, said it wasn't possible to devise a better system. Enter Ellis, a physicist at GCHQ, who in 1969 set out to do just that.

PROVEN POSSIBLE
By the end of the year, Ellis had demonstrated to the agency's senior officials that public-key cryptography was attainable, but because he wasn't a mathematician, he did not know how to implement his concept.

In 1973, Cocks, a mathematician, was asked to join the effort. It is said that he found a solution in just 30 minutes, but it couldn't be used because the computers of the day weren't advanced enough. A year later, Williamson, also a mathematician, began investigating Cocks's solution and eventually found a method that did work, leading to public-key cryptography.

Each person uses a pair of keys; one is a public key to send messages, and the other is private, known only to the recipient. The need for the sender and receiver to share secret information is eliminated; all communications involve public keys, and no private key is ever transmitted or shared. Only the recipient's private key can decrypt the message. The keys are related mathematically, but the private key cannot feasibly be derived from the public key given current computational limits.

IEEE plans to mount a plaque on 5 October recognizing the Milestone at GCHQ's main operational building at Cheltenham. The plaque will read:

"At GCHQ, by 1975 James Ellis had proved that a symmetric secret-key system is unnecessary and Clifford Cocks with Malcolm Williamson showed how such 'public-key cryptography' could be achieved. Until then it was believed that secure communication was impossible without exchange of a secret key, with key distribution a major impediment. With these discoveries the essential principles were known but were kept secret until 1997."

Back at the Beginning
Now that IEEE has 100 Milestones, with more on the way, The Institute decided to look back at the very first ones.

In 1977, prior to the formation of the IEEE Milestones in Electrical Engineering and Computing, IEEE was a cosponsor of the American Society of Civil Engineers' milestones program, known as Landmarks. The organizations jointly honored the Mill Creek No. 1 Power Plant, a hydroelectric facility in Redlands, Calif., that began operating in 1893. It was the first in the United States to use commercial three-phase alternating current generators.

Later in 1977, IEEE codesignated another joint Landmark: the Vulcan Street Power Plant, in Appleton, Wis., which was the world's earliest hydroelectric central station when it began operation in 1882.

As IEEE prepared to celebrate its centennial in 1983, it created its own Milestones program. A year later, IEEE approved three Milestones. The first to be dedicated was the Westinghouse Atom Smasher, in May 1985. It was the world's first industrial atom smasher, built in 1937 at Forest Hills, Pa.

In June 1985 came the dedication of the Cable Landing at Heart's Content, Nfld., Canada, recognizing the inaugural placement of a transatlantic cable in 1866. The third Milestone honored reception of a radio signal at Signal Hill, also in Newfoundland, which was dedicated in October 1985 to recognize the first transatlantic radio signals, received by Guglielmo Marconi on 12 December 1901.

Learn More