10.2 : RSA Key Generation

RSA Encryption was introduced in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman at MIT; hence the name "RSA". On the lecture slides, it's also called Public Key Encryption (PKE) and PKC (Public Key Cryptography).

Some links you may find helpful in this section

The RSA Key Generation Worksheet does most of this for you. The math relies on a lot of properties of prime numbers in modular arithmetic. The previous section covers it quite a bit more. You can also read through my notes from when I took CS-303: Algorithmic Number Theory & Cryptography CS-303 was a lot of work, but I really enjoyed the class. When you actually got the chance to sit down and play with the material, the way the numbers just worked was really cool.

1. Select p and q

p and q must be two random prime numbers. The larger the number, the more secure. Think about how long it would take to check the primeness of a number.

2. Compute n
n = pq

Since p and q are both prime, n only has four factors: {1, p, q, n}. Even though n will be made public, it's still very difficult to calculate the prime factorization of n.

3. Compute φ(n)
φ(n) = (p - 1)(q - 1)

It may be tempting to just accept this new seemingly random formula without question. I urge you to look a little deeper into where this formula came from.

If we look back at the the phi function, we see that the φ(n) function calculates how many values less than n are coprime to n. Why are we using subtraction and multiplication here? Why aren't we using a loop to count the number of values?

In the aforementioned math section, I also showed you the proof for two cool properties that φ has:

  1. If n is prime, &phi(n) = n - 1
  2. If a and b are coprime, then φ(ab) = φ(a) * φ(b)

Since we chose p and q to be prime numbers, when we put this all together we get:

n = pq Definition of n
φ(n) = φ(pq) Substitute definition
φ(pq) = φ(p) * φ(q) Property of φ
φ(p) = p - 1 Property of φ
φ(q) = q - 1 Property of φ
φ(n) = (p - 1)(q - 1) Substitution

4. Choose e and d

e will be our public key and d will be our private key.

Choose e such that it is relatively prime to φ(n)

We then calculate d such that it becomes the inverse of e. To do this, we use the following formula:

ed ≡ 1 mod φ(n)

The previous section goes much more in depth into this new notation for modulo and how to calculate a modular inverse. The RSA Key Generation Worksheet you use in lab generates possible K candidates which you choose to be factored into e and d. K = (p - 1)(q - 1)i + 1 where i is a random number. This is a possible approach because the numbers we are using on the worksheet are very small. In practice, it's much harder to generate the factors of a large number.

At first glance, the math for key generation appears to be very complicated and overwhelming, but if we look at it closely, even the unfamiliar math is much easier than it looks.

Back To Top