RSA

RSA is a cryptography algorithm used for asymmetric encryption and signing. It is based on the practical difficulty of factoring the product of two large prime numbers. The algorithm for generating keys looks like below.

1. Pick two large prime numbers (large prime numbers are difficult to factor out once we multiple them together). Let us call them $p$ and $q$.
2. Let us compute N called the module by multiplying $p$ and $qN=p \times q$$
3. Compute Euler’s totient function $\varphi (N)=(p-1)\times (q-1)$
4. Choose an integer $e$ such that $1<e<\varphi (N)$ and $\gcd (e,\varphi (N))=1$
5. Compute $d$ as the modular multiplicative inverse of $e\mathrm{mod}\varphi (N$, i.e., $d\cdot e\equiv 1(\mathrm{mod}\varphi (N))$
6. The public key is $(N,e)$
7. The private key is $(N,d)$

Encryption

To encrypt a given data $m$ into ciphertext $c$ we use the following equation. $c=m^e\mathrm{mod}N$

Decryption

To decrypt ciphertext c into plaintext $M$ $M=c^d\mathrm{mod}N$