According to Dr. Alfred Menezes, Professor of Mathematics at the University of Waterloo and co-author—with Dr. Darrel Hankerson and Dr. Scott Vanstone—of the Guide to Elliptic Curve Cryptography, the history of public-key cryptography has had four phases thus far:

1975-1979: the early years
1980-1989: protocols
1990-1999: deployments
2000-present: new developments

Phase I: The Early Years

The first major event in this history was the definition of the concept of public-key cryptography itself. Prior to the 1970s, symmetric-key cryptography had been the only cryptographic mode: parties involved in covert communications would agree on a shared secret key and then use that key to encrypt and authenticate their exchanges.

In the early 1970s, a new idea began to take shape. One of its originators was Ralph Merkle. Today, Dr. Merkle is a Distinguished Professor of Computing at Georgia Tech’s Information Security Center; back in the fall of 1974 he was an undergraduate student looking for a topic for his ‘quarter project’, and eventually settled on a problem of cryptography.

As he says, “I came to cryptography as an outsider, which had its advantages and disadvantages. The advantage was that I was uncommitted to prior schemes. The disadvantage is that I had a hard time describing to people what I actually meant.”

Merkle’s work—which originated around questions of how to recover security in a compromised system—led him to develop the Puzzles Method, a technique that showed it was possible to create problems of controllable difficulty using puzzles.

In his example, A begins creating random puzzles and sends them to B. B also creates puzzles and compares them to those of A, looking for a collision. When that collision occurs, B sends the common puzzle back to A. Since A and B both generated that puzzle, they can easily find its solution (in Merkle’s scenario, a 40-bit number). This solution is their shared key.

While it might take A and B 220=1,000,000 puzzles to hit a match, an eavesdropper would have to try all 240possibilities to solve the common puzzle and deduce the shared key. In other words, the eavesdropper would have to do a lot more work to reach the same conclusion.

Contained within this realization were the seeds of public-key cryptography: the idea that puzzles—or keys—could be publicly known while the contents of the information exchanges they relate to would remain essentially secure.

In the beginning, Merkle found little support for his ideas and their application to cryptography. Fortunately, he wasn’t the only one thinking along these lines. One day, someone said to him, “You know, there are these guys down in Berkeley who sound just like you.” Those guys, it turns out, were Whit Diffie and Martin Hellman, with whom Merkle soon became an associate and collaborator. And it was Diffie and Hellman’s 1976 paper, New Directions in Cryptography, that finally caused the concept of public-key cryptography to ‘click’ with readers.

Phase II: The Protocols

Two basic types of public-key schemes emerged in the 1970s: Diffie-Hellman for key agreement in 1975, and key transport and digital signing schemes proposed by Rivest, Shamir and Adleman (RSA) in 1977.

The Diffie-Hellman key agreement scheme derives its security from the hardness of the discrete logarithm problem: given pg, and ga, find a. RSA takes its security from the hardness of the integer factorization problem: given a number n that is the product of two primes, p and q, find p and q.

Yet by the 1980s, researchers realized that despite the hardness of these problems, the basic cryptographic functions themselves did not provide sufficient security. Careful protocol design was needed together with a methodology for defining precisely the security objective and proving that a protocol met that objective.
The first step was to imagine the most powerful adversary possible; the next, to assign that adversary a goal or set of goals as weak as possible. A protocol could be deemed secure if an ultra-potent adversary could not achieve his or her ultra-weak goals. This model evolved eventually into the notion of ‘provable security’, which invokes specific computational assumptions that can be used to prove that a proposed protocol meets the requirements of its security definition.

It wasn’t until the mid-1990s that provably secure protocols actually began to be efficient enough to warrant real-world application. However, other developments occurred before then. Most prominently, the ElGamal public-key encryption and signature schemes emerged in 1984 to rival those of RSA. Rather than integer factorization, the ElGamal techniques were based on the discrete logarithm problem.

So too was elliptic curve cryptography (ECC), which appeared on the scene in 1985.

• This Issue

This issue of Code & Cipher reviews the first annual Certicom ECC Conference and summarizes some of the key discussions at the event.