http://mitworld.mit.edu/video/879It’s not every day that Euclid appears in public with “Alice and Bob,” but in a lecture spanning a few thousand years, Ronald Rivest summons these and other notables in his history of cryptography. While citing milestones of code-making and breaking, Rivest also brings his audience up to date on the latest systems for securing information and communication networks, which owe much to his own research.
Rivest makes quick work of the period before mid- 20th century, but credits the ancient Greeks for prime number factorization -- essential to cryptography -- and elementary ciphers. In the 18th and 19th century, mathematicians delved into number theory and extended techniques of factoring. The twentieth century, with its two world wars and technological advances, established the significance of cryptography on and off the battlefield. Alan Turing’s Enigma machine not only helped the allies win World War II, but catalyzed development of the first generation of computers. MIT professor Claude Shannon, who worked with Turing and other cryptanalysts, went on to father the field of information science, leading to the digital age.
In the 1970s came development of public data encryption methods. Academics prevailed against U.S. government efforts to conceal means for encrypting data. In 1977, Rivest’s group at MIT, which included Adi Shamir and Len Adleman, came up with RSA, an elegant algorithm for public-key cryptography that “relies on the difficulty of factoring” primes and which is still widely used. The group was so confident of its encryption method that they offered $100 for breaking a cipher-text based on a 129-digit product of primes. Rivest thought it would take “40 quadrillion years” to solve the challenge. “It was a bad estimate,” he admits.
In fact, a combination of new algorithms and brute computing power cracked the text in 1994 (“The Magic Words are Squeamish Ossifrage”). Technological and theoretical advances have made possible improved encryption methods, and ways of authenticating and securing data. Faster computers may someday “make factoring a million-digit number easy,” says Rivest. Work is even progressing on a quantum computer (it can only factor the number 15 so far). But code-breaking is also increasingly sophisticated, Rivest warns, as the internet opens up vast new areas of data to cyber-attack.
Rivest sees cryptography blossoming into applications for anonymity, password-based keys, and crypto for smart cards. He has been looking into probabilistic micropayment systems, and techniques to enhance the security and transparency of voting. “Maybe large prime numbers have a role to play in our democracy down the road,” he says.
