Monday, 29 May 2017

RSA algorithm


You can directly jump on to the implementation of RSA and miss the beautiful history behind the first asymmetric encryption algorithm but I would not recommend doing that. I have made it very small and simple. Hope you will like it.

A bit of history of RSA algorithm:

Ever since people began to write down events in their lives, there has been a need for cryptography. The first thing people came up with was a symmetric encryption algorithm. But there was a problem with this. Symmetric algorithms used the same key for encryption and decryption. This means both sender and receiver should have the key used in the algorithm.
Now the problem boiled down to sharing of the key. And this was the same problem which we started with. We wanted to share our data without anyone tempering it in between. If we encrypt the key using another key then we need to send the second key to the receiver with the same conditions. It forms an infinite loop.

This problem persisted until Whitfield Diffie and Martin Hellman came into the picture. Diffie in an interview himself said how he invented first asymmetric key-based cipher.

Whitfield Diffie: “I walked downstairs to get a Coke, and almost forgot about the idea. I remembered that I’d been thinking about something interesting, but couldn’t quite recall what it was. Then it came back in a real adrenaline rush of excitement. I was actually aware for the first time in my work on cryptography of having discovered something really valuable.”

Diffie and Hellman went on discovering an algorithm that could be used to exchange keys between sender and receiver. But they could not discover the cipher that could generate public and private keys. That discovery was made by another trio of researchers: Rivest, Shamir and Adleman.

Rivest, Shamir, and Adleman were a perfect team. Rivest is a computer scientist with an exemplary ability to apply new ideas in new places. Shamir, also a computer scientist, has a lightning intellect. Adleman is a mathematician and was largely responsible for spotting the flaws within the ideas of Rivest and Shamir, and he ensured that they did not follow false leads.

Rivest and Shamir spent a year coming up with ideas, and Adleman spent a year shooting them down. In April 1977, Rivest, Shamir, and Adleman spent Passover at the house of a student and consumed liberal quantities of Manischewitz wine before returning to their respective homes sometime around midnight. Rivest was unable to sleep, so he lay on his couch with a math textbook. 
He began to mull over the question that had been nagging him all year: Is it possible to find a one-way function that can be reversed only if the receiver has some special information (This is what is RSA)? 

Suddenly, the mists around began to clear and he had a revelation. He spent the rest of the night formalising his idea, and by daybreak, he had effectively written a complete mathematical paper. Rivest had a breakthrough, but it could not have come without the help of Shamir and Adleman. The system was later dubbed RSA, for Rivest, Shamir, and Adleman.
The basic technique behind RSA was first discovered in 1973 by Clifford Cocks of CESG. But his this thing was kept secret till 1997. 

Now let's come to the RSA algorithm: 

  1. Choose two distinct prime numbers say 'p' and 'q'.
  2. Compute n = p*q.
  3. Compute ɸ(n). It is equal to "ɸ(p) * ɸ(q)" = (p-1) * (q-1).
  4. Choose an integer 'e' such that 1 and e and ɸ(n) are relatively prime. (e,n) is called public key.
  5. Find out d such that e * d = 1(modɸ(n)). (d,n) is called as the private key.
Let's take an example to understand the algorithm properly.
  1. Let p = 61 and q = 53 be two distinct prime numbers.
  2. n = 61 * 53 = 3233.
  3. ɸ(3233) = ɸ(61) * ɸ(53) = 60 * 52 = 3120.
  4. We find e = 17, because 1﹤e﹤3120. (17,3233) is the public key.
  5. Next, we compute d. (2753 * 17) % 3120 = 1. So d = 2753. (2753,3233) is private key.

For encryption and decryption: 

To get the cipher c for message m, we use the formula → c = m^e mod n.
To decipher c to get m, we use the formula → m = c^d mod n.

Example: If m = 65, and public key (17,3233) , private key (2753,3233). Perform encryption and decryption on this.
→ m = 65.
     c = (65)^17 mod 3233.
     c = 2790 is the cipher.
     To get the message back from cipher we perform the following steps.
     m = (2790)^2753 mod 3233.
     m = 65 is the original message.

Hope this was helpful. Leave your questions, answers & suggestions in the comment section below. And make sure to like us on Facebook and follow on Google+.

Thank you!