RSA

RSA encryption encrypts and decrypts messages using modular exponentiation. It is 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 this 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). For the Fermat prime test we could have used some other base, but 2 is just as easy as any other, so you can use 2 for your base in the test as well.

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.

• totient = 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 together with 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 satisfies d*e = 1 mod totient.

Note that e was chosen so that gcd(e, totient) = 1. Also, note that for any a and b, the extended Euclidean algorithm can be used to find s and t such that gcd(a, b) = s*a + t*b. If we apply the extended Euclidean algorithm to e and totient, we will have s and t such that 1 = gcd(e, totient) = s*e + t*totient. Notice that this means s*e = 1 mod totient, so s will be the exponent d we want.

To find d, we need to run the extended Euclidean algorithm on e and totient, so on 7 and 6000.

• 6000 = 7*857 + 1, so gcd(6000,7) = gcd(7, 1)
• gcd(7, 1) = 1 = 6000 - 7*857, so 1 = 6000*1 + 7*(-857)

We get that -857 is the inverse of 7 mod 6000. Equivalently, -857+6000 = 5143 is the inverse of 7 mod 6000.

We now have our private key: (n, d) = (60491, 5143).

Send a Message

Let's now send a message using the public key computed above. The public key we are using is: (n, e) = (60491, 7). Let's say we want to send the message "cool!". We first need to have the binary representation for the text. We use the ASCII values, and assume we are going to encrypt each byte of the message separately (in real life we would encrypt much more than that at a time, and be using much much larger primes and numbers).

• cool! in ASCII is: 99, 111, 111, 108, 33. Note - you can look up each one, have Python do it for you, or you can use a tool like CyberChef (under Data Format, use To CharCode).
• We encode these as follows, using Python:
  • pow(99, 7, 60491) = 41054
  • pow(111, 7, 60491) = 29085
  • pow(111, 7, 60491) = 29085
  • pow(108, 7, 60491) = 31620
  • pow(33, 7, 60491) = 53346

The encrypted message that we send is thus: 41054, 29085, 29085, 31620, 53346

Receive a Message

The person receiving the message uses their private key. In our case we would perform pow(x, 5143, 60491) for each of the values x that was sent to us. You can verify that we do indeed get back the values that were encrypted (99, 111, 111, 108, 33).

Assignment

If you are given this as an assignment you will be assigned primes p and q, and you need do the following.

1. Fermat prime test on both p and q, showing that they are prime. Demonstrate the fast modular exponentiation algorithm to do this.
2. Totient - demonstrate the using the Euclidean algorithm to find the gcd that is used in finding the totient value. Use the gcd you find to determine the totient.
3. Encryption exponent e - find the smallest e that has no factors with your totient. Together with n, you have your public key.
4. Decryption exponent d - demonstrate using the extended Euclidean algorithm to find the decryption exponent d (your private key).
5. You will be sent a message encrypted with your public key. Decrypt the message and include the plaintext of the message in your solution.
6. Make up some response to the encrypted message, and encrypt it using the public key that was demonstrated on this page. Include the encrypted message in your solution.

Note that this is a "doing / demonstration" assignment and not a "proofs" assignment. Still, keep your work organized, and use the numbering indicated here to make it easier for your instructor to follow along.

Good luck!