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, so
p = 2and
q = 5.
- Compute n = pq.
Simply multiply 2 and 5.
n = 10.
- Compute the totient of n, or
(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 = 10and
e = 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.