2002 – Adi ShamirThe Weizmann Institute CitationLeonard 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. Lecture [Home] [ACM Awards] [A. M. Turing Award] |