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) = 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
Verify d
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 )
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 )