Wednesday, 12th May 2004
RSA founders give perspective on cryptography
M.E. Kabay, Network World

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.

[snip]

"software was invented after dynamite"

Really? :)

Ah, well, it all depends... Software was first conceived by Ada Byron (later, Lady Lovelace) around 1838-1843. These years mark her interchange of letters with Babbage over the translation of lectures and an article dscribing his Analytical Engine. In the paper she published in 1843, she outlined the concept of software as an exposition of how to use the engine.

Alfred Nobel invented dynamite in 1866, and patented it a year later.

An invention in words is not an invention in deed. It wasn't until the construction of the Bomba in WWII, a full 100 years later, that software entered the world of deeds. Hence, the Turing Prize, not the Ada Prize.

Hi Ian,

The "laws" of security as presented in Shamir's Turing lecture were already common knowledge in the security research community at the time.

Making them part of his Turing lecture, Shamir did that community a Great service. He used the standing, fame and authority of the Turing awards, to lend these truisms appreciation by a wider audience. Quoting from his own T
lecture: "Received the ultimate seal of approval".

At the same time, because of their elusive nature, he made it sound as a grant proposal for further research ;-)

gr