Adi Shamir

Leonard M. Adleman, Ronald R. Rivest and Adi Shamir have been selected for their role in the creation of the world's most widely used public-key cryptography system, which has become known by their initials, RSA.

Their work was a significant advance in enabling secure communication among computers using public-key cryptography. Today, the RSA system is used in email systems, web browsers, secure shells, virtual private networks, mobile phones, and in many other applications requiring the secure exchange of information. The RSA algorithm made key management practical in public-key cryptography systems.

At the heart of the RSA encryption algorithm is the difficulty of factoring large integers. Factoring an integer involves finding the prime numbers which when multiplied together yield that integer. Despite the efforts of the world's most prominent mathematicians and computer scientists over the centuries, no one has yet found an effective way to factor large integers quickly.

To understand how RSA encryption works, suppose Alice and Bob want to communicate secretly without having to worry about Eve eavesdropping on their message exchanges. Alice secretly selects two prime numbers, usually at least one hundred digits long. She multiplies the two primes to create a "public key" which she can post on the Internet. If Bob wants to send a secret message to Alice, he fetches Alice's public key from the Internet and enters this key into the algorithm devised by Adleman, Rivest and Shamir to encrypt his message.

Here the essence of the RSA scheme manifests itself. Only Alice knows the prime factors that went into the creation of her public key and the RSA algorithm requires the recipient to know both factors to decipher the message. Since Alice chose the two factors, she of course can decrypt Bob's message and read it. Even though Eve can see the encrypted message and Alice's public key, Eve cannot decipher Bob's message so his communication to Alice remains secure.

Although the problem of factoring large integers into primes was suspected to be a computationally difficult problem, no one prior to the Adleman, Rivest and Shamir had understood how factoring could be effectively applied to the problem of generating public/private keys in the context of public-key cryptography.

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.