RSA

RSA encryption encrypts and decrypts messages using modular exponentiation. It is also a public-key encryption scheme, so that a person using the system will have two different keys - a "public" key that is shared publicly and a "private" key that is kept private. If someone wants to send a message to me, they encrypt the message with my public key, and it supposed to be the case that I am the only who can decrypt the message (using my private key). Clearly there needs to be a relation between the private key and public key for this to work.

This page walks you through choosing an RSA public/private key pair, using small numbers, in a way that you can do many of the computations "by hand" using algorithms you have learned in a course (e.g., CS 303).

Public Key

The process starts with "large" primes p and q. For our example, we use p=241 and q=251. Okay, let's get started...

=Fermat prime test / modular exponentation

Confirm that the primes are indeed prime. We use the Fermat prime test, and show how this works for p. We need to check that 2^p-1 = 1 mod p. So we need to compute 2²⁴⁰ mod 241. Note that Python can do with (pow(2, 240, 241)), but we want to see how to do this using the algorithm for fast modular exponentiation. So, here is my work for computing 2²⁴⁰ mod 241:

• 2¹ mod 241 = 2
• 2² mod 241 = 4
• 2⁴ mod 241 = 16
• 2⁸ mod 241 = 15
• 2¹⁶ mod 241 = 225
• 2³² mod 241 = 15
• 2⁶⁴ mod 241 = 225
• 2¹²⁸ mod 241 = 15
• Note that 240 = 16 + 32 + 64 + 128, so 2²⁴⁰ mod 241 = (2¹⁶)(2³²)(2⁶⁴)(2¹²⁸) mod 241 = 225 * 15 * 225 * 15 mod 241 = 1

We conclude that p=241 passes the Fermat prime test, and we're going to say that we're okay with using it as one of our primes for the algorithm.

Let's assume that we have also checked that q=251 is also prime (passes the Fermat prime test).

Modulus and Totient

We set our modulus n = p*q = 241*251 = 60491. This will be part of our public key. Note that we share the value of n, but do NOT share p and q.

We will need the so-called "Carmichael totient" function of n. Namely we need the value lcm(p-1, q-1). We will call the value "totient". We can compute the lcm using the gcd, and compute the gcd using the Euclidean algorithm.

• lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1)
• So let's compute gcd(p-1, q-1) = gcd(240, 250)

250 = 240*1 + 10, so gcd(250, 240) = gcd(240, 10) 240 = 10*24 + 0, so gcd(240, 10) = gcd(10, 0) = 10

• We conclude that gcd(p-1, q-1) = 10, and therefore lcm(p-1,q-1) = 240*250 / 10 = 6000

So we set totient = 6000

Encryption exponent

We need to pick an encryption exponent e that has no common factors with our totient. We try e=2, e=3, ..., until we find an e with gcd(e, 6000) = 1.

• gcd(2, 6000) = 2, so 2 is no good.
• gcd(3, 6000) = 3, so 3 is no good.
• Similarly, 4, 5, and 6 don't work.
• gcd(7, 6000) = 1.

So we will use e=7 as our encryption exponent.

We now have our public key, which is (n, e) = (60491, 7)

Private Key

The private key consists of the same modulus n but a different exponent. We are looking for the exponent d such that d is the inverse of e mod totient. So we are looking for d that satisfied d*e = 1 mod totient.

Send a Message

Given primes p and q

1. Confirm p and q are prime using Fermat's little theorem prime test.
   1. Show the steps of how this is done using fast modular exponentiation.
2. Let n = p*q and totient = lcm(p-1, q-1) = (p-1)*(q-1) / gcd(p-1, q-1).
   1. Show the steps of computing gcd(p-1, q-1) using the Euclidean algorithm.
3. Find the smallest e > 1 such that gcd(e, totient) = 1.
4. Let d be the inverse of e mod totient.
   1. Show the steps of computing d using the extended Euclidean algorithm.
5. Your public key: n, e
6. Your private key: n, d

Take a given ciphertext c and computer c**d mod n to decrypt the message. Note: you will receive a message from the instructor that is encrypted with your public key.

Given the instructor's public key, encrypt your response and include that in your submission of the assignment.

CyberChef things to use...

• To Char code, from char code.