An RSA algorithm is an important and powerful algorithm in cryptography. It is widely used in Digital Signature and in an SSL. The algorithm works in the following way

- Select at random two LARGE prime number $p$ and $q$.
- Multiply $p$ and $q$ i.e. $n = p*q$.
- Select a small odd integer $e$ which is relatively prime to $\phi(n)$, where $\phi(n) = (p-1) * (q - 1)$.
- Calculate the value of $d$ (explained below). $d$ is calculated as a modular multiplicative inverse of $e$ modulo $n$.
- Publish the pair $P = (e, n)$ as a public key.
- Keep secret the pair $S = (d, n)$ as a private key.

The message is encrypted using $P = (e, n)$ using following formula.

\[P(M) = M^e \text{ mod } n\]

The message can be decrypted using $P = (d, n)$ using following formula.

\[S(C) = C^d \text{ mod } n\]

Secret key pair $(d, n)$ should be kept secret.