RSA Algorithm: Concepts and Implementation

Introduction

In this article we will do a deep-dive into RSA, which is a strong cryptography oriented algorithm. We will understand its origins, uses, and implementation in detail with examples along the way. Code provided will be in C++.

Modern technology  makes use of the RSA Algorithm to encrypt and decrypt data. The RSA algorithm generates two unique keys for encryption and decryption, making it an asymmetric cryptographic algorithm. Given that one of the keys involved is made public, it is public key cryptography.

Steps

To operate, RSA relies on prime numbers, which are illogically large numbers. Only the person carrying the private key can decrypt the encrypted message because the public key is made available publicly (i.e., to everyone).

Asymmetric cryptography illustration:

1. A client (such as a browser) contacts the server with a request for data while sending the server its public key.
2. Using the client's public key, the server encrypts the data before sending it.
3. The data is given to the client, who decrypts it.
   

The operation of RSA requires the use of both public and private keys. The following steps are used to generate the keys:-

1. Select two prime numbers (p and q)
2. Calculate the modulus for both the keys (n = pq)
3. Find the totient value [(p-1)(q-1)]
4. Select e such that it is greater than 1 and coincides with totient, requiring that gcd (e, totient) equal 1; e is the public key.
5. Select d so that it fulfills the equation de = 1 + k (totient), where d is the private key that only a select few people are aware of.
6. The formula c = me mod n is used to calculate ciphertext, where m is the message.
7. Equation m = cd mod n, where d is the private key, is used to decrypt the message with the assistance of c and d.

Code

Output:

Original Message = 9

p = 13

q = 11

n = pq = 143

phi = 120

e = 7

d = 0.142857

Encrypted message = 48

Decrypted message = 9