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.

1. Choose two distinct prime numbers p and q.
These are the two primes that he mentioned, so `p = 2` and `q = 5`.
2. Compute n = pq.
Simply multiply 2 and 5. `n = 10`.
3. Compute the totient of n, or `(p-1)(q-1)`.
`(2-1)` times `(5-1)` is 1 times 4 which equals 4.
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` and `e = 3`.
5. 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.

Category :