University of Southern California (2002)
Citation
"For their ingenious contribution for making public-key cryptography useful in practice."

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.

Adleman attended the University of California, Berkeley, where he received his Bachelor's degree in 1968 and his Ph.D. in 1976.

In 1994, his paper Molecular Computation of Solutions To Combinatorial Problems described the experimental use of DNA as a computational system. In it, he solved a seven-node instance of the Hamiltonian Graph problem, an NP-Complete problem similar to the traveling salesman problem. While the solution to a seven-node instance is trivial, this paper is the first known instance of the successful use of DNA to compute an algorithm. DNA computing has been shown to have potential as a means to solve several other large-scale combinatorial search problems.

For his contribution to the invention of the RSA cryptosystem, Adleman was a recipient along with Ron Rivest and Adi Shamir of the 2002 ACM Turing Award, often called the Nobel Prize of Computer Science.

Fred Cohen, in his 1984 paper, Experiments with Computer Viruses has credited Adleman with coining the term "virus".

Adleman was the mathematical consultant on the movie Sneakers.

• Complete Lecture with Slides quicktime | shockwave
• Lecture only quicktime
• Audio only mp3 | wma
• Slide Show only slide show