Public/Private Key Math

Heavily sourced from: Cryptography and Network Security, Fourth Edition by William Stallings.

Key Generation

Pick two prime numbers: p and q

p = 7
q = 13

Compute n=p.q

n=p.q
n=7 x 13
n=91

Compute the Euler Totient of n: Φ(n) = (p-1)(q-1)

Φ(n) = (7-1)(13-1)
Φ(n) = 6 x 12
Φ(n) = 72

Pick an integer e, such that the greatest common denominator between Φ(n) and e is 1, and e is greater than 1 but less than Φ(n)

gcd(Φ(n),e)=1 and e>1 and e<Φ(n) gcd(72,e)=1  Choosing e: 5 

Determine the value of d using the formula:

de mod Φ(n) = 1
dx5 mod 72 = 1

Possible values for dx5 need to be 72*(some integer) + 1:
73 (won't work)
145 (that will work)
145/5 = 29

Plugging into:
dx5 mod 72 = 1
29x5 mod 72 = 1

d = 29

With d, e, and n computed, we have our keys:

Public Key:  KU = {e, n} = {5, 91}
Private Key: KR = {d, n} = {29, 91}

Encryption and Decryption

Now, we're ready to encrypt. Assuming plaintext M, we compute ciphertext using the formula: C=(M^e)mod(n)

Assuming plaintext M=10
C = (M^e) mod(n)
C = (10^5) mod(91)
C = 82

Compute 10^5 mod 91 via wolframalpha.

Decryption uses the formula: M=(C^d)mod(n)

C = 82 (from above)
M = (C^29)mod(91)
M = (82^29)mod(91)
M = 10 (that worked!)

Compute 82^29 mod 91 via wolframalpha

What's remarkable is how monstrous the math gets using relatively tiny prime numbers to start with. We started with 7, and 13 to create our keys, and our final computation (the decryption) required us to compute 82^29, which is:

31666620625027474232451213268613396669946986162166956032

Our keys, were of a really trivial bit-length {5,91}, and {29,91}. Consider that most asymmetric algorithms talk about keys that are of lengths greater than 1000 bits. Now consider what the size of the exponents may look like, and the corresponding products which need to be modulo divided.