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 nGenerate two prime numbers.Prime number 1, p = 7Prime number 2, q = 17n = p x qn = 7 x 17 = 119Thus n = 119Generation of eCompute 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 = 96Prime 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, 89Lets us choose a random prime number that has a GCD of 1 with 96We 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 = 13Public 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 dd is the multiplicative inverse of (e) with ϕ(n)ie, find d, which is the multiplicative inverse of e (13) with 96e = 13, ϕ(n) = 96d * e ≡ 1 mod ϕ(n)d * 13 ≡ 1 mod 96i.e., ( d * 13 )% 96 should yield a remainder of 1This 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 Programe = 13m = 96print(modInverse(e, m))37Computed value of d is 37Verify dd * e ≡ 1 mod ϕ(n)d = 37d * e = 37 * 13 = 48196 * 5 = 480481 % 96 = 1thus d * e ≡ 1 mod ϕ(n)Private Key ( d, n ) = ( 37, 119 )So FarWe have generated a public key and private key, using simple mathematics.Public Key ( e, n ) = ( 13, 119)Private Key ( d, n ) = ( 37, 119 )Generating RSA Private and Public Keys was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.