What is the 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

1. Generating the keys

  1. Select two large prime numbers, xx and yy. The prime numbers need to be large so that they will be difficult for someone to figure out.
  2. Calculate n = x * yn=xy.
  3. Calculate the totient function; \phi(n) = (x-1)(y-1)ϕ(n)=(x−1)(y−1).
  4. Select an integer ee, such that ee is co-prime to \phi(n)ϕ(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.

  1. Calculate dd such that e.d = 1e.d=1 modmod \phi(n)ϕ(n).

dd can be found using the extended euclidean algorithm. The pair (n,d)(n,d) makes up the private key.

2. Encryption

Given a plaintext PP, represented as a number, the ciphertext CC is calculated as:

C = P^{e}C=Pe​​ modmod nn.

3. Decryption

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

P = C^{d}P=Cd​​ modmod nn.

Leave a reply