rsa algorithm

RSA Algorithm: Concepts and Implementation

Blog | Board Infinity
Blog | Board Infinity


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.


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.


using namespace std;
// find gcd
int gcd(int a, int b) {
  int t;
  while(1) {
      t= a%b;
      return b;
      a = b;
      b= t;
int main() {
  //take two random prime numbers
  double p = 13;
  double q = 11;
  double n=p*q;//calculate n
  double track;
  double phi= (p-1)*(q-1);//calculate phi
  //public key to be encrypted
  double e=7;
  //for checking that 1 < e < phi(n) and gcd(e, phi(n)) = 1; i.e., e and phi(n) are coprime.
  while(e<phi) {
      track = gcd(e,phi);
  //private key to be decrypted
  //choosing d such that it satisfies d*e = 1 mod phi
  double d1=1/e;
  double d=fmod(d1,phi);
  double message = 9;
  double c = pow(message,e); //encrypt the message
  double m = pow(c,d);
  cout<<"Original Message = "<<message;
  cout<<"\n"<<"p = "<<p;
  cout<<"\n"<<"q = "<<q;
  cout<<"\n"<<"n = pq = "<<n;
  cout<<"\n"<<"phi = "<<phi;
  cout<<"\n"<<"e = "<<e;
  cout<<"\n"<<"d = "<<d;
  cout<<"\n"<<"Encrypted message = "<<c;
  cout<<"\n"<<"Decrypted message = "<<m;
  return 0;


Original Message = 9

p = 13

q = 11

n = pq = 143

phi = 120

e = 7

d = 0.142857

Encrypted message = 48

Decrypted message = 9

write your code here: Coding Playground
Software DevelopmentAlgorithmData Structure

Blog | Board Infinity

At Board Infinity we have authors leading in their profession sharing their insights, ideas and inspiration. Here influential thinkers, creators, makers and doers are found in one place.