# RSA Algorithm

The RSA algorithm is an asymmetric cryptography algorithm; this means that it uses a public key and a private key (i.e two different, mathematically linked keys). As their names suggest, a public key is shared publicly, while a private key is secret and must not be shared with anyone. It is named after those who invented it in 1978: Ron Rivest, Adi Shamir, and Leonard Adleman.

The sender encrypts the data with the receivers public key and creates cipher text which is send to the receiver. At receivers end the receiver decrypts the data with his own private key.

An example of asymmetric cryptography :
a) A client (for example browser) sends its public key to the server and requests for some data.
b) The server encrypts the data using clients public key and sends the encrypted data.
c) Client receives this data and decrypts it.

## How it works

1. Generating the keys

a) Select two large prime numbers, x and y. The prime numbers need to be large so that they will be   difficult for someone to figure out.

b) Calculate n = (x*y).

c) Calculate the totient function; phi(n) = (x-1)(y-1)

d) Select an integer e should not be a factor of n, such that e is co-prime to phi(n) and 1<e<phi(n)      . The pair of numbers (n,e) makes up the public key.

-Note : Two integers are co-prime if the only positive integer that divides them is 1.

e)  calculate phi(n): Such that phi(n) = (P-1)(Q-1)

f) Calculate d such that e.d = 1 mod phi(n). d can be found using the extended euclidean algorithm. The pair (n,d) makes up the private key.

g) Now private key d = (k*phi(n) + 1) / e for some integer k

2. Encryption

Given a plaintext P, represented as a number, the ciphertext C is calculated as:

C = P^e mod n

eg : "HE" H = 2 and E = 3

C = 23^e mod n

3. Decryption

Using the private key (n,d), the plaintext can be found using:

P = C^d mod n

## Implementation

#include <iostream>
#include <math.h>
using namespace std;

// find gcd
int gcd(int aint b)
{
int t;
while (1)
{
t = a % b;
if (t == 0)
return b;
a = b;
b = t;
}
}

int main()
{
//2 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
//e stands for encrypt
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(ephi);
if (track == 1)
break;
else
e++;
}

//private key
//d stands for decrypt
//choosing d such that it satisfies d*e = 1 mod phi
double d1 = 1 / e;
double d = fmod(d1phi);
double message = 99;
double c = pow(messagee); //encrypt the message
double m = pow(cd);

c = fmod(cn);
m = fmod(mn);

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;
}

## Output

Original Message = 99
p = 13
q = 11
n = pq = 143
phi = 120
e = 7
d = 0.142857
Encrypted message = 44
Decrypted message = 99