Rivest Shamir Adleman (RSA)

RSA is a public key cryptosystem for both encryption and authentication. It was invented in 1977. It is an encryption algorithm that uses very large prime numbers to generate the public key and the private key. RSA is typically used in conjunction with a secret key cryptosystem such as DES. DES would be used to encrypt the message as a whole and then use RSA to encrypt the secret key. Thus, RSA provides a digital envelope for the message. RSA is in wide use today, it is possibly the most commonly used public key algorithm used. Because of this it has undergone a lot of public scrutiny and there is much empirical evidence of its security. It can be used for both encryption and signing.

Although it would be possible to factor out the public key to get the private key (2 prime factors must be found out), the numbers are so large as to make it very impractical to do so. The encryption algorithm itself is very slow, which makes it impractical to use RSA to encrypt large data sets. In PGP (and most other RSA-based encryption programs), a symmetrical key is encrypted using the public key, then the remainder of the data is encrypted with a faster algorithm using the symmetrical key. The symmetrical key itself is randomly generated, so that the only way to get it would be by using the private key to decrypt the RSA-encrypted symmetrical key.

In the same year that RSA was developed, Ralph Merkle started working on another approach to public key exchange. This one would end up teaching the hard lesson of not trusting newly discovered cryptosystems. Merkle’s system resembled the mathematical game called the knapsack problem. The puzzle involves a knapsack and an odd assortment of objects of different sizes, and it had to be packed in a way such as there is no space wasted. The knapsack problem isn’t really that difficult in the smaller sizes, but as the knapsack gets increasingly bigger, and the objects increasingly numerous, so does the difficulty of the problem.

To simplify the mathematics, the size and shape of the objects were ignored, and only the weight was counted for. It turns out that there are two classifications of knapsack problems. Ordinary knapsacks, which are difficult to solve, and superincreasing knapsacks, which are simple to solve. Merkle found a way to turn superincreasing knapsacks into knapsacks that were not superincreasing. This serves to turn a simple problem into a nearly impossible one. Working with Martin Hellman, Merkle devised a way to encode information in a knapsack problem. How does this key system work? David and Antonia are getting tired, but they have to keep switching encryption systems to throw the other jealous ThinkQuest teams off.

David creates a superincreasing knapsack that is simple to solve, from that, he creates a non-superincreasing knapsack, and thus difficult to solve. David passes the regular knapsack to Antonia, who, in turn, encrypts a message and sends it back to David. David then uses the superincreasing knapsack to help solve the regular one. The mathematics are way beyond the scope of this site, but you can find it in Diffie’s paper.

On October 6, 1977, Martin Hellman and Ralph Merkle jointly filed for a patent on the algorithm. The patent, #4,218,582, titled, "Public-Key Cryptographic Apparatus and Method," was granted August 19, 1980, and assigned to the Board of Trustees of Stanford University. At the Crypto ’82 Conference, however, Len Adleman cracked Merkle’s single iteration (one cycle) knapsack problem. Merkle’s faith in his algorithm was unshaken, however, and he posted in Time Magazine a thousand dollar reward to anyone who could break a multiple iteration knapsack. Two years later, he paid the money to Ernie Brickell, who solved a knapsack system of 40 iterations and 100 weights in an hour of time on a Cray-1 supercomputer.

Meanwhile, back at the labs of MIT, in the spring of 1976, Rivest, Shamir, and Adelman read the Diffie-Hellman paper "New Directions in Cryptography." The three then decided to set out making a multi-user cryptography system. 545 Technology Square, eighth floor, the work place of the three professors for three months. Rivest came up with ideas, Adelman destroyed them, and Shamir did a little of both. It is said that you should never try to develop an encryption system unless you have gotten your feet wet in a little cipher breaking. Currently, there is no mathematical process to prove a cipher secure, and the only way we have to prove it insecure is to break it. In April of 1977, while lying on the couch with a headache, it suddenly hit Rivest, that it was easy to multiply two large prime numbers, but very difficult to find its prime factors. This new algorithm for key exchange was now known as RSA, the initials of its three inventors, and satisfies the origional Diffie-Hellman description of "multi-user cryptography" because it does not require two active participants when performing both the encryption and decryption.

Now, David and Antonia were sick and tired of the other public key exchange systems. The time difference between Singapore and Rockville, MD were incredible, and that meant that one of them, or both of them, had to stay up into the ungodly hours of the night in order to communicate. So, David found the RSA method of data exchange (we’ll use small numbers for the example). (special thanks goes out to Simson Garfinkle for not making me do more math, get his book, PGP: Pretty Good Privacy) David picks two prime numbers, we’ll use

a=47 and b=71

for now. Now David could calculate the value of c.

c= a x b = 47 x 71 = 3337

David also must make sure that the encryption key must be relatively prime, or has no common factors with the number

(a-1)(b-1) = 46 x 70 = 3220

David then chooses 79 for his encryption key, using the extended Euclid algorithm and the prime numbers (which are known only to David), he calculates the decryption key. (the algorithm for mod is beyond the scope of this web site, but you can find it in the PGP source code)

d = 79^-1(mod(3220))=1019

David then publishes his public key on his web site for people to encrypt messages with to send to him.

David’s RSA Key
C = 3337
encryption key = 79

The next day, Antonia wants to encrypt the number 688 and raises it to the 79th power and takes the modulo 3337 of the result.

(688^79)mod(3337) = 1570

David then gets the number 1570, and tries to decrypt it by replacing the encryption with the decryption key.

(1570^1019)mod(3337)= 688

Rivest, Shamir, and Adelman wrote a paper describing the invention and published it as a MIT artificial Intelligence Laboratory Technical Report. A challenge was placed in Martin Gardner’s column in Scientific American in which the readers were invited to crack.

C = 114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,
362,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,989,
075,147,599,290,026,879,543,541

encryption key = 9007

The message "first solver wins one hundred dollars" appeared in an A = 01, B=02, C=03 … format. This was solved in April 26, 1994, cracked by an international effort via the internet with the use of 1600 workstations, mainframes, and supercomputers attacked the number for eight months before finding its factors (the number above). Of course, the RSA algorithm is safe, as it would be incredibly difficult to gather up such international participation to commit malicious acts.

RSA patent filed on December 14, 1977, approved as #4,405,829 titled "Cryptographic Communications System and Method" to MIT, Rivest, Shamir, and Adelman. However, since it was published before the patent application, it could not be patented under European and Japanese law. (US coders, you still have hope, the RSA patent expires in 2000!) Rivest tried to put RSA onto a chip in order to help with the computing problem, but MIT at the time lacked the technical expertise to make chips. And no outside companies would do it either. A company was soon formed, called RSA Data Security, and was granted an exclusive license on the RSA patent as was and is the standard practice of MIT.