Encryption Math(s)
Numberphile recently posted a video about the math behind RSA encryption. In the video below, a brief description of public key cryptography is given and then we are shown a simple example of the math used to perform encryption and decryption (math example @ 2:25).
In the video, James skips over the method for determining the private key, so I thought I would run through the key generation steps for his example.
- Choose two distinct prime numbers p and q.
These are the two primes that he mentioned, sop = 2
andq = 5
. - Compute n = pq.
Simply multiply 2 and 5.n = 10
. - Compute the totient of n, or
(p-1)(q-1)
.
(2-1)
times(5-1)
is 1 times 4 which equals 4. - Choose an integer e greater than 1 and less than the totient of n such that e and the totient are coprime.
There are only two integers between 1 and 4. Two divides 4, so the only choice left is 3. At this point, we have the two components of the public key,n = 10
ande = 3
. - Find d where d times e equals 1 modulo the totient.
- 0 times 3 is 0 and the remainder of 0 divided by 4 is 0.
- 1 times 3 is 3 and the remainder of 3 divided by 4 is 3.
- 2 times 3 is 6 and the remainder of 6 divided by 4 is 2.
- 3 times 3 is 9 and the remainder of 9 divided by 4 is 1. Therefore,
d = 3
.
In this case, the public exponent e and the private key d are both 3. That’s why the values were cubed in both encryption and decryption. The cubed values were divided by 10 which was the n we computed in step 2. The remainder of the division yielded the encrypted or decrypted message.