<- Virtual Exhibitions in Informatics

RSA Cryptosystem

The algorithm was described in 1977 by Ron Rivest, Adi Shamir and Len Adleman at MIT; the letters RSA are the initials of their surnames.

Clifford Cocks, a British mathematician working for GCHQ, described an equivalent system in an internal document in 1973. His discovery, however, was not revealed until 1997 due to its top-secret classification.

The algorithm was patented by MIT in 1983 in the United States of America as U.S. Patent 4405829. It expired 21 September 2000. Since the algorithm had been published prior to patent application, regulations in much of the rest of the world precluded patents elsewhere. Had Cocks' work been publicly known, a patent in the US would not have been possible either.

RSA works as follows:

1) Choose two large prime numbers p ≠ q randomly and independently of each other. Compute N = p*q.

2) Compute φ = (p-1)(q-1).

3) Choose an integer 1 < e < φ which is coprime to φ.

4) Compute d such that d*e ≡ 1 (mod φ).

e is the public key and d the private key. En-/Decryption is performed by computing x^e and x^d

 

Ron Rivest


Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science. He is most celebrated for his work on public-key encryption with Len Adleman and Adi Shamir, specifically the RSA algorithm, for which they won the 2002 ACM Turing Award.

He is also the inventor of the symmetric key encryption algorithms RC2, RC4, RC5, and co-inventor of RC6. The "RC" stands for "Rivest Cipher", or alternatively, "Ron's Code". (RC3 was broken at RSA Security during development; similarly, RC1 was never published.) Similarly, he also authored the MD2, MD4 and MD5 cryptographic hash functions.

Adi Shamir


Adi Shamir (born 1952) is an Israeli cryptographer. He was one of the inventors of the RSA algorithm (along with Ron Rivest and Len Adleman), and has made numerous contributions to the fields of cryptography and computer science.

n addition to RSA, Shamir's other numerous inventions and contributions to cryptography include the Shamir secret sharing scheme, the breaking of the Merkle-Hellman cryptosystem, visual cryptography, and the TWIRL and TWINKLE factoring devices. Together with Eli Biham, he discovered differential cryptanalysis, a general method for attacking block ciphers. (It later emerged that differential cryptanalysis was already known — and kept a secret — by both IBM and the NSA.)

Shamir has also made contributions to computer science outside of cryptography, such as showing the equivalence of the complexity classes PSPACE and IP.

Len Adleman

Leonard Adleman (born December 31, 1945) is a theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being the inventor of the RSA (Rivest-Shamir-Adleman) cryptosystem in 1977, and of DNA computing.

In 1994, his paper Molecular Computation of Solutions To Combinatorial Problems described the experimental use of DNA as a computational system. In it, he solved a seven-node instance of the Hamiltonian Graph problem, an NP-Complete problem similar to the traveling salesman problem. While the solution to a seven-node instance is trivial, this paper is the first known instance of the successful use of DNA to compute an algorithm. DNA computing has been shown to have potential as a means to solve several other large-scale combinatorial search problems.

Further Links