# 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, so`p = 2`

and`q = 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,

and*n*= 10

.*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.