Skip to main content

Public and Private key encryption/decryption

Cryptography 101

Asymmetric key encryption is key to many things, especially for TLS handshake in HTTPS protocol. How it works is that you first generate a pair of key, one is referred to the public key, and the other is referred to as the private key.

Public and private key just consists of some numbers and uses modular exponentiation to do the actual encryption and decryption. You have several member at play here:

  • e is the encryption exponent. This is a public value that everybody basically uses the same value, usually 65537
  • d is the decryption exponent. You will be generating this and need to be kept as a secret, as part of your private key
  • n is the modulus, same as e it is also public and is generated

How these numbers are generated aren't that important to the context of explaining cryptography, but if you would like to know refer to the bottom section

 

 

 

More info please! How are e, d, n generated?

1. First you pick two prime numbers as p and q, any is fine

p = 7
q = 13

2. Multiply them together

n = p * q
n = 7 * 13
n = 91

3. Then find the Euler's totient function of n

φ(n) = (p - 1) * (q - 1)
φ(91) = (7 - 1) * (13 - 1)
φ(91) = 6 * 12
φ(91) = 72

4. Then pick a random e such that it is between φ(n) and 1 and is coprime with φ(n), meaning no common factors between e and φ(n)

1 < e < φ(91)
1 < e < 72

Let's say e=23

5. Finally compute d which is the modular multiplicative inverse of e

e^-1 = d (mod φ(n))
23^-1 = d (mod φ(91))
23^-1 = d (mod 72)
23 * d = 1 (mod 72)
23 * 47 = 1 (mod 72)
d = 47

Then public key is (n = 91, e=23)

And private key is (n=91, d=47)

Big thanks to https://www.onebigfluke.com/2013/11/public-key-crypto-math-explained.html for simply explaining the math behind asymmetric key generation.

 

 

 

Back to top