RSA Cryptosystem

You can not tell me that you studied cryptography and not once this algorithm troubled you. Students always are troubled when they hear RSA. Coming from a subject where each and abbreviation expands to a meaningful full form of its own (such as DES: Data Encryption Standard or AES: Advanced Encryption Standard), RSA is sure a bummer. RSA is named after the three inventors Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.

In traditional cryptography, such as was available before the 1970s, the encryption and decryption operations are performed with the same key. This means that the party encrypting the data and the party decrypting it need to share the same decryption key. Establishing a shared key between the parties is an interesting challenge. If two parties already share a secret key, they could easily distribute new keys to each other by encrypting them with prior keys. But if they don’t already share a secret key, how do they establish the first one?

RSA is an asymmetric key cryptography algorithm, which means it uses two different keys for encryption and decryption namely public key and private key respectively. No doubt that the public key is known to everyone ("Public" duh!) and the private key is well private.

Let's get into the mechanism behind RSA now. There are three main steps :

• Key Generation
• Encryption
• Decryption

These three are inter-related processes. (Of course, you knew that!) Let us begin with the key generation:

Key Generation:

There are some steps that you must follow to generate public and private keys that will later be used for encryption and decryption processes.

1. Select two primes numbers p and q. Now, these two need to be large for higher security. For the sake of simplicity, I am taking smaller numbers but you don't dare make that mistake while implementing the algorithm.

The two primes I have chosen are 3 and 11.

2. Calculate the product of these two numbers and save the result in n.

n=p * q

3. Next, calculate the value of  Φ(n).

4. Choose a value for e i.e your public key. But, there are two conditions that you got to take care of:

• 1 < e <  Φ(n), i.e, the value of your public key should be greater than 1 and less than the value of  Φ(n) & gcd( Φ(n), e) = 1.

5. In this step, we will calculate the private key, denoted by d.

d= (e^-1) mod Φ(n).

The private key in this example is 3.

We are done with the key generating parts so let us move on to encryption.

Encryption:

Suppose M denotes the message that is to be encrypted, which must be less than n. And C denotes the ciphertext. For example, let us assume our message M is equal to 31, in that case,

C=(M^e )mod n,

c is the ciphertext and m is the message to be encrypted and e is the public key.

Decryption:

Came this far, how can we leave without decryption? So the formula for decryption is :

M = ((C^d) mod n )

Note that for decryption we are using the private key, d.

There we go completing the whole process of RSA. These three steps comprise RSA. It generates keys, with the help of those keys it encrypts and decrypts the message. Implementation of the algorithm is even more interesting but let's leave that for the next article. I hope this can help you with your exams at least. Peace out.