RSA Encryption: Encryption and Decryption Overview

RSA encryptions are easily one of the most well known encryption standards available out there . RSA stands for Rivest-Shamir-Adleman and the name is derived from the surnames of the founders who initially described the algorithm in 1973.

In a public-key cryptosystem, the encryption key is public and distinct from the decryption key, which is kept secret (private). An RSA user creates and publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers are kept secret. Messages can be encrypted by anyone, via the public key, but can only be decoded by someone who knows the prime numbers

The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers, the “factoring problem”. The process of tackling a RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem is an open question(not anywhere to the level of P=NP conundrum of course).There are no published methods to defeat the system if a large enough key is used.

RSA is a relatively slow algorithm. Because of this, it is not commonly used to directly encrypt user data. More often, RSA is used to transmit shared keys for symmetric key cryptography, which are then used for bulk encryption-decryption.

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

Here is an example of RSA encryption and decryption . The parameters used here are artificially small ,and it is to be noted that in practical applications prime numbers of much higher magnitudes are used.

1)Chose two distinct prime numbers p and q such that p and q are similar in magnitude but differ in length by at least a few digits. Their values should be kept a secret.

1p=61 and q=53

2) Compute n=pq.

1n= 61*53= 3233

3)Compute the Carmichael’s totient function of the product given by λ(n)=lcm (p-1,q-1)

1λ(n)=lcm (60,52)=780

4) Chose any number 1<e<λ(n) that is co-prime to λ(n).

1Let e=17

5)Compute d, the modular multiplicative inverse of e(mod λ(n)).

12d=413 as 1= (17*413)mod 780

The public key for the given example is (n=3233,e=17). For a padded plaintext message m, the encryption function is

1c(m)= (m^17) mod 3233

The private key is (n = 3233, d = 413). For an encrypted ciphertext c, the decryption function is

1m(c)=(c^413) mod 3233

Take any value of m and try encrypting it and then decrypting it.

Although RSA encryption is considered one of the most secure encryptions available out there, it can easily be broken down if we aren’t careful with taking the values of p and q. The mathematical proof for the same exists, but is beyond the scope of this introductory post.