I was following the examples in a post but rewrote the mathematical terminology so that it read a little bit easier.
A simple RSA example showing how to generate a public and private key pair for asymmetric encryption.
Start with prime numbers 13 and 7. Use their product as a maximum value, or the
RSA modulus, denoted by n:
p = 13
q = 7
n = pq = (13)(7) = 91
Find the number of integers less than 91 that are co-primes of 91 (n). We
can do this using Euler's totient function. The function is multiplicative,
meaning we can do the following since the factors are prime:
φ(n) = φ(p)φ(q)
φ(91) = 12 * 6 = 72
Since 7 and 13 are prime numbers we can use φ(n) = n - 1 when operating on
on them.
Solve for φ(7) or φ(q)
φ(7) = 7 - 1
φ(7) = 6
Solve for φ(13) or φ(p)
φ(13) = 13 - 1
φ(13) = 12
Using long form (formula not specific to prime numbers):
φ(7) = 7(1 - (1/7)) = 6
φ(13) = 13(1 - (1/13)) = 12
Thus:
φ(7) = 7 - 1 = 6
φ(13) = 13 - 1 = 12
So:
φ(91) = φ(13)φ(7) = 6 * 12 = 72
Meaning, there are 72 integers between 1 and 91 that are co-primes of 91.
The following is another way to calculate this, substituting p and q
for the prime factors of n.
φ(n) = n * (1 - (1/p)) * (1 - (1/q))
φ(91) = 91 * (1 - (1/13)) * (1 - (1/7))
φ(91) = 72
Randomly choose an integer, e, where 1 < e < φ(n) and is relatively
prime with the totient (φ(n)), meaning it doesn't share any common factors
with the totient except 1. For this example, let's assume e = 5.
To generate a private key based on the public key we picked, we need to find
the modular inverse of e with respect to the totient, φ(n), using e*d mod φ(n) = 1 and solve for d.
e*d mod φ(n) = GCD(e, φ(n)) # Extended Euclidean algorithm
5*d mod 72 = 1 # value substitution
Because e and φ(n) are relatively prime, their greatest common divisor
is 1 since they don't share any other factors except 1, meaning GCD(e, φ(n)) = 1.
Next, rewrite the formula as the Euclidean equation (φ(n) is a and
e is b in this case). Solve for x and y, where y is d:
ax + by = GCD(a, b)
72x + 5y = 1
Calculate how many times 5 goes into 72 (c), leaving the remainder (r).
72 = c(5) + r
72 = 14(5) + 2 # 5 goes into 72 fourteen times (c=14) with a remainder of two,
# perform the same equation but substitute 5 for 72 and
# 5 for 2, which is the remainder we just found.
2 = 72 - 14(2) # Rewrite in terms of the remainder
5 = c(2) + r # 2 goes into 5 two times (c=2) with a remainder of one, once
# you get a remainder of one you can stop
5 = 2(2) + 1
1 = 5 - 2(2) # Rewrite in terms of the remainder
At this point, we can use back substitution to solve for x and y:
1 = 5 - 2(2) # Substitute 2 for what we solved for above
1 = 5 - 2(72 - 14(5))
1 = 5 - 2(72) + 28(5) # Apply distributive property
1 = 29(5) - 2(72) # Combine like terms
72(-2) + 5(29) = 1 # Rewrite in terms of the original equation
x is -2 and y is 29, meaning the modular inverse of e with respect
to φ(n) is 29, or d.
p = 13 # random prime number
q = 7 # random prime number
n = 91 # RSA modulus
φ(n) = 72 # totient
e = 5 # random integer that is relatively prime to the totient (public)
d = 29 # modular inverse of the public key (private)
Keys are represented as:
public key: (e, n) = (5, 91)
private key: (d, n) = (29, 91)
Extended Euclidean algorithm walk-through
Now that we have a key pair, we can encrypt and decrypt things with them:
public key = (5, 91)
private key = (29, 91)
To encrypt, multiple a number by itself 5 times (e) and wrap around the
maximum (n). To decrypt, multiply the resulting number by itself 29 times
(d), wrapping around the maximum (n).
Let's encrypt SECRET using UTF-8 uppercase characters (A = 65, Z = 90).
S = 83
E = 69
C = 67
R = 82
E = 69
T = 84
c = m*e mod n
c = 83*5 mod 91 = 3939040643 mod 91 = 83
c = 69*5 mod 91 = 1564031349 mod 91 = 62
c = 67*5 mod 91 = 1350125107 mod 91 = 58
c = 82*5 mod 91 = 3707398432 mod 91 = 10
c = 69*5 mod 91 = 1564031349 mod 91 = 62
c = 84*5 mod 91 = 4182119424 mod 91 = 28
Ciphertext is 83 62 58 10 62 28
Decrypt the ciphertext above back to its original value by multiplying each value by itself, wrapping around the maximum, 29 times.
m = c*d mod n
m = 83*29 mod 91 = 4.500540548×10⁵⁵ mod 91 = 83
m = 62*29 mod 91 = 9.535840877×10⁵¹ mod 91 = 69
m = 58*29 mod 91 = 1.378516007×10⁵¹ mod 91 = 67
m = 10*29 mod 91 = 1×10²⁹ mod 91 = 82
m = 62*29 mod 91 = 9.535840877×10⁵¹ mod 91 = 69
m = 28*29 mod 91 = 9.280746472×10⁴¹ mod 91 = 84