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.