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.

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.