Learn the most widely used encryption algorithm in a more easiest way with examples

RSA encryption algorithm is named after its inventors Rivest, Shamir, and Adleman. It is an asymmetric or public-key cryptographic algorithm which generates two keys a public and a private key.

🎁Resources: At the end of this writeup I have share most useful online tool that can be utilized to generate the public & private keys for RSA algorithm

Key terms

p & q are any large prime numbers
N is the product of p & q (p*q)

e is the public key exponent
(e, N) is the public key

d is the private key exponent
(d, N) is the private key

M is the plaintext
C is the ciphertext

Here is the full detailed and step by step process using examples on how RSA algorithm generates the public & private keys

Steps to generate Public key & Private key

1️⃣Choose two distinct large prime numbers p & q

First step is to choose two different and large prime numbers p & q, because the security of RSA depends on the difficulty of factoring (N) into its prime components (p) and (q), the more large prime components are the more secure it is .

Factoring a large number N(hundreds or thousands of bits long) back into its p and q is computationally hard which makes it secure

Example:
To make these steps easy to understand you can choose small prime numbers as following:

p = 13
q = 7

2️⃣Compute (N)

n is the product of the prime number p and q:

N = p*q

Use online tool https://www.tausquared.net/pages/ctf/rsa.html to compute n product of the prime number p and q

Example:

N = 91

3️⃣Calculate φ(N)

This can be calculate as the product of (p-1) & (q-1):

φ(N) = (p-1)*(q-1)

Use online tool https://rsa-calculator.netlify.app/ to compute the θ(N)

Example:

φ(N) = 72

4️⃣Choose ‘e’

Find the value of e that meets the following condition:

1<e<φ(n) & gcd( e,φ(n) ) = 1

Multiple values of e can be generated that meets the condition given above, use any one of them

Use online tool https://rsa-calculator.netlify.app/ to generate all the possible values of e

Example:

Choosing 11 as the value of e for this example

e = 11

5️⃣Calculate ‘d’

Calculate d such that:

(d*e) mod φ(n) = 1

This can be done using the modular inverse method:

modular inverse of (e mod φ(n) )

Use online tool inverse-modulo to generate d

Example:

modular inverse of (11 mod 72) = 59

6️⃣Compute public key & private key

Public key can be computed as:

 {e , N}

Private key can be computed as:

{d , N}

Example:

Public key = {11, 91}
Private key = {59, 91}