We use SSH, HTTPS, etc., on a daily basis. These programs depend on RSA asymmetric key encryption and decryption for providing security.

Asymmetric key encryption involves two keys, **public key** and **private key**. Public key is used for encrypting the message and Private key is used for decrypting the message.

In this post, we will look into how a public key and private key pair are generated using simple mathematics.

We will use small numbers for simplicity.

### Public Key ( e, n )

Public key is made up of two numbers called **e** and **n**.

#### Generation of n

Generate two prime numbers.

Prime number 1, p = 7

Prime number 2, q = 17

n = p x q

n = 7 x 17 = 119

Thus **n = 119**

#### Generation of e

- Compute totient of n, ϕ(n) = ( p -1) x (q -1)
- Choose a random prime number that has a greatest common divisor (gcd) of 1 with ϕ(n)

ϕ(n) = ( 7 — 1 ) x ( 17–1 ) = 6 x 16 = 96

Prime numbers between 1 and 96 are,

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89

Lets us choose a random prime number that has a GCD of 1 with 96

We cannot use 2, since 2 is the GCD for 96 and 2.

We cannot use 3, since 3 is the GCD for 96 and 3.

13 is a good number, since 1 is the GCD for 96 and 13.

Now, we have got, **e = 13**

*Public Key ( e, n ) = ( 13, 119 )*

### Private Key ( d, n )

We have already generated n, which is 119. Now, we need to generate **d**.

#### Generation of d

*d is the multiplicative inverse of (e) with ϕ(n)*

ie, find d, which is the multiplicative inverse of e (13) with 96

`e = 13, ϕ(n) = 96`

d * e ≡ 1 mod ϕ(n)

d * 13 ≡ 1 mod 96

i.e., ( d * 13 )% 96 should yield a remainder of 1

This requires computing numbers one by one, until we find the right number. This is hard to do by hand, so let’s use a small python program to generate d,

# Python program to find modular

# inverse of a under modulo m

# A naive method to find modulor

# multiplicative inverse of 'e' under modulo 'm'

def modInverse(e, m) :

e = e % m;

for x in range(1, m) :

if ((e * x) % m == 1) :

return x

return 1

# Driver Program

e = 13

m = 96

print(modInverse(e, m))

37

Computed value of **d is 37**

#### Verify d

`d * e ≡ 1 mod ``ϕ(n)`

d = 37

d * e = 37 * 13 = 481

96 * 5 = 480

481 % 96 = 1

thus

d * e ≡ 1 mod`ϕ(n)`

*Private Key ( d, n ) = ( 37, 119 )*

### So Far

We have generated a public key and private key, using simple mathematics.

Public Key ( e, n ) = ( 13, 119)

Private Key ( d, n ) = ( 37, 119 )