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 )

Setting Up Your Machine for ML

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

Generating RSA Private and Public Keys

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Google, Are you listening?

102 Stories To Learn About Encryption

153 Stories To Learn About Cryptography

5 Books You Can Read to Boost Your Computer Science Knowledge

6 Not-so-obvious Tech Predictions

Google, Are you listening?

102 Stories To Learn About Encryption

153 Stories To Learn About Cryptography

5 Books You Can Read to Boost Your Computer Science Knowledge

6 Not-so-obvious Tech Predictions

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps