The famous cryptographers Leonard Adleman, Ronald Rivest, and Adi Shamir - the developers of the RSA encryption code - received the Association for Computing Machinery's 2002 Turing Award "for their seminal contributions to the theory and practical application of public-key cryptography." Their Turing Award lectures, given last June, are available online.
Rivest, Shamir and Adleman implemented public-key cryptography in the 1970s following the landmark work of Whitfield Diffie, Martin Hellman and Ralph Merkle. They then founded RSA Security, which became one of the most respected security companies in the world.
RSA organizes the immensely valuable annual RSA Conferences, perhaps the most significant security conference of the year now that the National Computer Security Center and the National Institute of Standards and Technology have stopped their late lamented National Computer Security Conferences.
While I'm mentioning RSA, I should remind readers that its FAQ is an excellent source of information about cryptography.
The distinguished scientists' lectures are available online in a variety of formats at: http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.html?code=nlsec121
Adleman started the event with a brief historical overview of three major areas of study that led to the public-key cryptosystem (PKC): number theory, the study of computational complexity, and cryptology.
Next, Rivest reviewed the events around the invention of the RSA PKC. They hit on the idea of depending on the difficulty of factoring as the basis for a public/private key cryptosystem, where one key would be public, the other private, and each key would decrypt what the other key encrypted. Martin Gardner of _Scientific American_ helped them by publishing an article with a US$100 challenge for factoring a 129-digit product of two large primes (RSA-129). They estimated that factoring this number would take 40 quadrillion years. But the RSA-129 challenge was finally factored using thousands of cooperating computers via the Internet 10 years ago, and a ciphertext was decrypted as, "The magic words are squeamish ossifrage."
Finally, Shamir reviewed the current state of cryptography. Despite initial fears among the law enforcement community that encryption would lead to serious impediments for investigations and anti-terrorism work, reports from the US Department of Justice show that no federal wiretaps encountered encryption in 2002. In state and local jurisdictions, investigators encountered encryption in 16 wiretaps out of approximately 1,300 cases; however, in none of these cases did encryption interfere with the ability of the investigators to gather the evidence needed for prosecution.
Shamir pointed out that cryptography is central to today's technology. One of the most important benefits of cryptography is the constant interaction of theory and practice; for example, abstract mathematical tools have been productively applied to cryptanalysis. Similarly, well-established practical concepts such as basic notions of security, complexity, logic and randomness have stimulated much theoretical creativity.
Shamir formulated three laws of security. First, "Absolutely secure systems do not exist." We have to accept that we should implement systems that are secure enough. For example, postage stamps are a ridiculous security measure, but they work for millions of people around the world. Vending machines where you put in a coin and choose one newspaper out of the pile available are weak security systems, but they're good enough.
The second law is, "To halve your vulnerability, you have to double your expenditure." This law implies that improvements in security become less and les cost-effective the further one goes in improving one's systems.
Finally, "Cryptography is typically bypassed, not penetrated." He said he is unaware of any major, world-class security failure in which hackers penetrated systems by using heavy-duty cryptanalysis. They usually use much easier methods.
The last part of Shamir's presentation is a review of six major areas of today's cryptography: theory; public-key encryption and signature schemes; secret-key cryptography using block ciphers; secret-key cryptography using stream ciphers; theoretical cryptographic protocols; and practical cryptographic protocols.
He predicted that:
- AES will remain secure for the foreseeable future.
- Some public-key schemes and key sizes will be successfully attacked in the next few years.
- Cryptography will be invisibly everywhere.
- Vulnerabilities will be visibly everywhere.
- Crypto research will remain vigorous, but only its simplest ideas will become practically useful.
- Non-crypto security will remain a mess.
It was exhilarating to listen to these brilliant people speaking to us, and I hope some of you will have an hour to spare to enjoy their lectures.