[LINK] Maybe large prime numbers have a role to play in our democracy down the road a bit.

Tom Koltai tomk at unwired.com.au
Tue Feb 22 14:16:52 AEDT 2011

>From the latest MIT World Video series

About: MIT World is a free and open site that provides on demand video
of significant public events at MIT. MIT World's video index contains
more than 800 videos 

http://mitworld.mit.edu/video/879   (one hour and nine minutes.. Get a
coffee first.)

It'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

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. 

More information about the Link mailing list