Ronald (Ron) Linn Rivest

Ron Rivest grew up in Niskayuna, New York, a suburb of Schenectady. He attended public schools and graduated from the Niskayuna High School in 1965. He graduated from Yale University in 1969 with a B.A. in mathematics, and from Stanford University in 1973 with a PhD in Computer Science. He learned from the best: his PhD supervisor was Turing Award recipient Robert Floyd, and he worked closely with Turing Award laureate Don Knuth.

Following graduate study he accepted a post-doctoral position at INRIA in Rocquencourt, France before taking a job at MIT, where he has been ever since. He currently holds the Andrew and Erna Viterbi professorship in the Department of Electrical Engineering and Computer Science.

At MIT he met Leonard M. Adleman and Adi Shamir, who collaborated with Ron on their fundamental advance in cryptography. They were inspired by a 1976 paper [4] by cryptographers Whitfield Diffie and Martin Hellman discussing several new developments in cryptography. It described ways for the sender and receiver of private messages to avoid needing a shared secret key, but it did not provide any realistic way to implement these concepts. Rivest, Shamir, and Adleman presented practical implementations in their 1977 paper, “A method for obtaining digital signatures and public-key cryptosystems,” [1] which showed how a message could easily be encoded, sent to a recipient, and decoded with little chance of it being decoded by a third party who sees it.

The method, known as Public Key Cryptography, uses two different but mathematically linked keys: one public key used to encrypt the message, and a completely different private key used to decrypt it. The encrypting key is made public by individuals who wish to receive messages, but the secret decrypting key is known only them. The two keys are linked by some well-defined mathematical relationship, but determining the decryption key from its publically available counterpart is either impossible or so prohibitively expensive that it cannot be done in practice. The “RSA” method (from the first letters of the names of the three authors) relies on the fact that nobody has yet developed an efficient algorithm for factoring very large integers. There is no guarantee, however, that it will be difficult forever; should a large quantum computer ever be built, it might be able to break the system.

A detailed discussion of the theory and practice behind RSA can be found here. The computer code to implement it is quite simple, and as long as suitably large integer keys are used, no one knows how to break an encoded message.

RSA is used in almost all internet-based commercial transactions. Without it, commercial online activities would not be as widespread as they are today. It allows users to communicate sensitive information like credit card numbers over an unsecure internet without having to agree on a shared secret key ahead of time. Most people ordering items over the internet don’t know that the system is in use unless they notice the small padlock symbol in the corner of the screen. RSA is a prime example of an abstract elegant theory that has had great practical application.

After developing the basic method in 1977, the three Turing Award recipients founded RSA Data Security in 1983. The company was later acquired by Security Dynamics, which was in turn purchased by EMC in 2006. It has done cryptographic research, sponsored conferences, shown how earlier encryption systems could be compromised, and spun off other companies such as Verisign. Rivest thus demonstrated that he could move easily between theory and practice. When the 1983 patent on RSA [2] was about to expire, RSA Data Security published all the details of its implementation so that there would be no question that anyone could create products incorporating the method.

The three Turing Award recipients were not aware that a similar method had been developed years before by British mathematician Clifford Cocks, who extended the even earlier work of James H. Ellis. Cocks was doing his encryption work at the Government Communications Headquarters (GCHQ), so it was classified as secret and not released until 1997, twenty years after Rivest, Adleman, and Shamir had published their independent discovery.

In addition to the well-known RSA scheme, Rivest designed several other encoding methods for special applications. RC2, or “Ron’s Code 2,” was designed in 1987 as an encoding method for Lotus Corporation to use in the international version of their Lotus Notes product. The US National Security Agency (NSA) had prohibited the export of software unless it met restrictions designed to ensure that sensitive technology did not fall into unfriendly hands; RC2 was effective but still met those restrictions. Details of all six (two of which were never released) of Ron’s RC algorithms can be found here.

Rivest’s interests in security are not limited to encryption. For example, he is a member of the US government technical committee that develops election guidelines, and he published a 2006 paper [5] describing a novel three-ballot voting scheme. The paper is posted on his MIT website and is modified occasionally to eliminate problems that others have noted. As Rivest notes at the end:

ThreeBallot is hereby placed in the public domain—I am not filing for any patents on this approach, and we encourage others who work on extensions, improvements, or variations of this approach to act similarly. Our democracy is too important...

Ron is also an inspirational teacher. His co-written influential textbook Introduction to Algorithms [3], based on his undergraduate and graduate courses, has become a classroom standard. More than 500,000 copies were sold in 20 years.