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

### 1. Generating the keys

- Select two large prime numbers, x
*x*and y*y*. The prime numbers need to be large so that they will be difficult for someone to figure out. - Calculate n = x * y
*n*=*x*∗*y*. - Calculate the
function; \phi(n) = (x-1)(y-1)**totient***ϕ*(*n*)=(*x*−1)(*y*−1). - Select an integer e
*e*, such that e*e*isto \phi(n)**co-prime***ϕ*(*n*) and 1 < e < \phi(n)1<*e*<*ϕ*(*n*). The pair of numbers (n,e)(*n*,*e*) makes up the public key.

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

- Calculate d
*d*such that e.d = 1*e*.*d*=1 mod*m**o**d*\phi(n)*ϕ*(*n*).

d*d* can be found using the * extended euclidean algorithm*. The pair (n,d)(

*n*,

*d*) makes up the private key.

### 2. Encryption

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

C = P^{e}*C*=*P**e* mod*m**o**d* n*n*.

### 3. Decryption

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

P = C^{d}*P*=*C**d* mod*m**o**d* n*n*.