Weizmann Indtitute of Science (1996)
Citation

Public-Key Cryptography

Leonard Adleman, Whitfield Diffie, Martin Hellman, Ralph Merkle, Ronald Rivest, Adi Shamir

The idea of a public-key cryptosystem was conceived in 1976 by Diffie, Hellman, and Merkle, while Rivet, Shamir, and Adleman provided its first effective realization in 1977. The original conception of the idea was a remarkable achievement, as it simultaneously addressed two key security questions: (1) key exchange over insecure communication channels and (2) message authentication. Classical cryptography, also know as private-key cryptography, depends on the ability of legitimate parties to exchange keys without anyone else finding out what the keys are. Previously it had seemed that to do this one needed a secure channel between the parties, something that would be hard to find for an arbitrary pair wishing to communicate over a large public network. Message authentication is the problem of verifying that a given message was sent by the claimed author.

In a public-key cryptosystem as originally envisioned, the encryption keys would come in easy-to-generate pairs such that (1) anything encrypted using one key could be decrypted using the other and (2) given one key, the "public" key, it is infeasible to decrypt messages encoded with that key without knowledge of the other "secret" key. Using such a system, anyone wishing to receive encrypted messages need only generate a pair of keys and broadcast the public key over the network. Moreover, you can generate a message that demonstrably must come from you simply by encoding it with your secret key. Note also that such a system reduces the potential number of keys needed for N parties to communicate with each other from N^2 to N.

The idea of a public-key cryptosystem was a major conceptual breakthrough that continues to stimulate research to this day, as theoreticians and others attempted to devise such systems, deduce the consequences of their existence, and invent new variants and applications. The first effective realization of its full potential was the "RSA" scheme of Rivest, Shamir, and Adleman, which made crucial use of number theory to provide the encryption and decryption mechanisms. This turned out not only to be a theoretical "proof in principle" but also an eminently practical scheme and the one that is still most widely used today.

The use of public-key cryptography "in practice" is currently both widespread and rapidly growing. It is now generally recognized that computing and communications technology are merging in a way that makes data available not only to intended recipients, but unintended ones as well. We see this in email and web access where data flowing through many computers is vulnerable to interception. The growth of wireless communications for voice and computer communications leads to greater connectivity, but also to much greater opportunity to intercept data and forge messages. We are moving to a world of high connectivity where each user can see other users' data. The only practical way to maintain privacy and integrity of information is by using public-key cryptography.

The effects of this technology are evident today in a number of products. World Wide Web browsers and servers from Netscape and Microsoft use public- key cryptography for client/server authentication and for key management in support of confidentiality. Standards for secure electronic transactions in the credit card industry embody the use of public-key cryptography, and a wide range of hardware and software products are emerging to support these standards. Products providing email services (e.g., Microsoft Exchange, Qualcomm Eudora, Netscape Navigator, etc.) are adding security based on public-key cryptography with release of these mainstream products. Lotus Notes, the most successful groupware products, is an early example of the use of public-key cryptography, since its introduction in the later half of the 1980s.

Today, millions of people are doing home banking and credit-car purchases over the Internet, and both the number of people and the variety of applications are growing rapidly, all made possible by the security offered by public-key cryptography. Indeed, electronic commerce on the Internet would not be possible without the flexible, robust security offered by public-key cryptography. It is reasonable to believe that a decade from now public-key cryptography will be an integral component of all information systems - and their software components - for which integrity of content is essential, for which security of transactions is paramount, for which certainty of user identification is legally required, for which high value (in the dollar sense) events occur electronically. No other single concept in the history of cryptography has been as far reaching.