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, and . Public key is used for encrypting the message and Private key is used for decrypting the message. public key private key 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 and . e 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 )
Share Your Thoughts