**Register Now!**

12,987 reads

by Nambi SankaranFebruary 1st, 2019

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 is made up of two numbers called **e** and **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**

- 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 )*

We have already generated n, which is 119. Now, we need to generate **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) = 96d * 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 xreturn 1

# Driver Programe = 13m = 96print(modInverse(e, m))37

Computed value of **d is 37**

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

d = 37d * e = 37 * 13 = 48196 * 5 = 480

481 % 96 = 1

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

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

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

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

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

L O A D I N G

. . . comments & more!

. . . comments & more!