Vendor Accent

The three decades of RSA

Atul Kahate writes about the growth of RSA as an encryption standard through three decades

The concepts of security and cryptography are quite simple in the basic form. Small children have the maximum number of secrets to keep. For example, a sister (the sender of a message) wants to secretly inform her brother (the intended recipient of the message) that there are two chocolates in the refrigerator, one of which is kept for him. However, the trouble is that the mother (the attacker/hacker) is also around, and therefore, this million-dollar secret cannot be given out as it is. So, what does the sister do? She transforms every alphabet in her sentence into a language she thinks is unbreakable. For example, she may use ch as the replacement for all the alphabets in the original sentence; thus transforming the word chocolate to sound as chochochate! Of course, the fact that the attacker can make this out very quickly and therefore, take the necessary action results in a sad ending to this story.

Although it may sound incredibly more complicated than the above example, real-life cryptography works in a similar manner. The sender has a message, which she wants to transform in such a manner that the result looks like gibberish. No one can make any sense out of it. This gibberish is then sent to the receiver, who should be able to make sense out of it by transforming the gibberish back into its original form. How can this happen? The sender must first transform the message into gibberish by using two things: an algorithm and a key. Now, what are these? Suppose that the sender decides that she would transform each alphabet in the original message with one that is three places ahead (i.e. replace every A with D, B with E, and so on). This scheme, known as Caesar Cipher, would mean the following:

• The algorithm is Replace each alphabet with an alphabet that is n places next
• 3 is the key

Therefore, the sender would transform the message ATUL into DWXO and send it to the recipient. This process is known as encryption. The receiver then uses the same algorithm and the same key (in the opposite direction) to transform the gibberish DWXO back into ATUL. This process is called decryption. This is where we come across the problem termed as the problem of key exchange or key agreement. How can the sender communicate the fact that key is 3 to the recipient? Obviously, the sender cannot send it in the same message in which the garbled text is sent: if the attacker has access to this communication link, the attacker would come to know about the key straightaway! The sender cannot send it via another message, because the attacker could be potentially watching the communication link at all times. Several such alternatives fail. Therefore, the problem of key exchange is the one that is the toughest to resolve.

When the Data Encryption Standard (DES) was developed by IBM under the supervision of the US Government’s National Security Agency (NSA), apart from several other criticisms, one of the major ones was this problem of key exchange. Although the algorithm was supposed to make data exchange quite secure, how would the key be communicated? This was when the search for a workable solution to the problem of key exchange began.

Two gentlemen named Whitfield Diffie and Martin Hellman thought about this problem for a number of years. Diffie had graduated from MIT in 1965. Hellman had done his graduation from New York University in 1966, followed by an MS and PhD from Stanford University.

Diffie and Hellman were intrigued by the problem and used to work on various approaches, only to discover that there were certain flaws in them. While Diffie had a solid background in Mathematics, Hellman specialized in Electrical subjects. In 1975, when Diffie was thinking about the problem after dinner, as usual, he suddenly thought that he had thought of something quite brilliant. In all excitement, he thought he had done it only to realize that he had lost his thoughts the next moment! He panicked, and thankfully, did not lose his cool so as to recollect his ideas the same night. His idea was something like this:

Do not have a single key. Instead, let the key consist of two parts: one part (called the public key) should be known to the sender (and maybe to others as well), and the other (called the private key) should be known only to the recipient. Whenever the sender (or anyone) wants to perform some message transformation so as to secure it, they use the well-known public key. When the recipient wants to transform the secured gibberish back into its original plaintext, he uses the private key.

In a hurry, Diffie went to Hellman’s house the same night and told him about his idea. Hellman soon told Horst Fiestel, the pioneer behind the DES algorithm, about this. Fiestel rubbished the idea. He said keys cannot be split. The whole idea in cryptography, according to Fiestel, was to keep the secret in the key; and if key itself is going to be split or shared, it would serve no purpose!

Diffie and Hellman’s ideas were to prove revolutionary, except that they were not able to practically demonstrate them. Ralph Mekle attempted to do some work based on the Diffie-Hellman ideas, but also could not succeed beyond a point. However, they remain pioneers of modern cryptography.

In 1976, Ron Rivest, a 29-year old Assistant Professor at MIT was also looking at the Diffie-Hellman theory. He believed that it was possible to translate their theory into practice. Interestingly, one of his students had handed over the Diffie-Hellman white paper to Rivest. This was the start of his interest in the Diffie-Hellman scheme.

Then there was Leonard Adleman, Rivest’s colleague at MIT. Rivest was quite good in mathematical theory. Adleman was good in testing theoretical ideas by applying logic and testing the same in practical, real world, situations. Thus, their pairing was sound. Rivest would propose some ideas, and Adleman would systematically break them! They were both thinking about the Diffie-Hellman ideas. At about the same time, Adi Shamir, an Israeli guest lecturer arrived at MIT. He was brilliant in mathematics and quickly became interested in the work of Rivest and Adleman, and the pair became a threesome. They would discuss various ideas, possible implementations and their pitfalls. Rivest and Adleman would constantly dig out new theories, and present them to Adleman; who, like a seasoned pro, would squash them with unbeatable logic. Interestingly, all three were quite good in mathematics, but not so good in cryptography, or for that matter, even in computers! They were not aware of DES beyond a point, for example.

One day after he returned from a party, Rivest thought of a unique idea. He had known that (a) it was easy to multiply two large prime numbers, but (b) given a very large number that has only two prime numbers as its factors, it was almost impossible to find out those factors in a reasonable period of time. This was also stated by Donald Knuth in his famous series of books on computer algorithms and related areas. Rivest’s thoughts went something like this:

• Choose the public key to be the result of the multiplication of two very large prime numbers (each 100 digits or longer).
• Choose another large random number. This would be the encryption key.
• The public key would now be the above encryption key of step 2, plus the multiplication of the two large prime numbers of step 1.
• The private key would be calculated by using the original prime numbers of step 1 (before they were multiplied).

Obviously, to resolve this challenge, the attacker must factor the public key into the original prime numbers. This was indeed impossible (in finite time), as per the theory.

Rivest was convinced that he had achieved something remarkable. As was customary, he rushed to Adleman. Adleman tried to disprove the theory as usual. But to his surprise, for the first time, he thought that Rivest had indeed discovered something truly amazing. He could not break Rivest’s scheme. Shamir also added his ideas. The three were now almost sure that they had achieved another landmark in the history of cryptography. At this stage, Adleman said that the whole work was done by Rivest. So, the credit should go completely to him. Shamir also had similar views. However, Rivest was quite clear that without the contributions from and discussions with both Adleman and Shamir, it would have been impossible to succeed. Hence, they agreed on an abbreviation that was made up of the first letter of their surnames—Rivest, Shamir, and Adleman or RSA.

They quickly wrote a paper based on their ideas and talked about securing e-mail, files, funds transfer messages, etc. For the first time, they introduced a few characters such as Alice, Bob, Carol, etc instead of the dry A, B, and C in their description of the scheme. Rivest sent this paper to many people, including Martin Gardner, who used to write a very popular column for Scientific American. Gardner saw tremendous potential in the RSA scheme. He wrote an article describing the RSA algorithm in the magazine in August 1977. That article propelled the popularity of RSA to unbelievable heights. To make matters more interesting, a challenge was published, whereby a message was encrypted using a 129-digit key; and readers were invited to break it. Whosoever managed to do so would get a prize of $100! Nobody did, and soon RSA was considered as the solution to the problem of key exchange. In other words, it soon became the world’s leading cryptographic protocol.

This really upset the NSA. All along, they were supposed to be the experts in cryptography. Now, three professors had challenged their supremacy! They threatened Rivest, Shamir, and Adleman in various ways. The RSA team was confused. Their employers (MIT) took a stand that they did not want to invite the government’s wrath. Therefore, the RSA team was discouraged from spreading know-how regarding the algorithm. The RSA team was devastated! Should they keep spreading the word, or should they hold on to it? Would they be jailed for their actions if they did not follow the instructions of MIT, and therefore of NSA? For several months, this cat-and-mouse game went on. Finally, in December 1977, MIT granted permission for distributing this algorithm to the general public. This effectively squashed the authoritative supremacy of NSA. MIT filed a patent on this algorithm on behalf of the RSA team.

Later, to make the algorithm commercially successful, the RSA team decided to form a company. This paved the way for the company named RSA Security Inc. However, the RSA team was not good at marketing its ideas. It did not know how to draw up business plans, work out financials, and sell. Hence, it had to recruit and rely upon a few others, who had mastered this art. After a few initial hiccups, the company did well, and has now emerged as one of the strongest companies in this space. The RSA algorithm continues to stand tall and is widely used in all sorts of security applications across the world.

The author is the Head – Technology Practice, PrimeSourcing Division, i-flex solutions limited akahate@gmail.com