Proj 4: RSA with Very Small Keys (10 pts. + 20 pts. extra credit)

What you need:

Purpose

To calculate RSA parameters and use them, in a very simple case with small numbers.

Summary

Here's a diagram from the textbook showing the RSA calculations.

1. Choose Two Primes: p and q

Let's use p = 7 and q = 23

2. Compute n = p * 2

Start Python in interactive mode. On a Mac or Linux box, you can do that by typing this command into a Terminal window:
python
Execute these commands to store p and q in the Python interpreter, and calculate n 
p = 7
q = 23
n = p * q
print p, q, n
The parameters print out, as shown below. n = 161

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

Execute these commands (I don't know how to use Greek in Python, so we'll use "phin" instead of φ(n)): 
phin = (p-1) * (q-1)
print p, q, n, phin
The parameters print out, as shown below. phin = 132

4. Select Public Exponent e

e has to be between 1 and phin - 1 and it has to not share any divisors with phin. One simple way to meet these requirements is to pick a small prime number.

Let's use e = 5

5. Compute Private Key d

We need to find a d with this property:
(d * e) mod phin = 1
First let's set e and perform a simple multiplication.

Execute these commands. As shown below, 20 * 5 is 100, as you'd expect. 

e = 5
print 20 * e
Now let's use modular arithmetic, with a modulus of phin, that is, 132. In Python, we use a % character to indicate a modulus.

Modulus 132 means there is no number larger than 131. Adding 1 to 131 makes it roll back to 0. The numbers are on a ring, as shown below.

Execute these commands. As shown below, 132 modulus phin is zero. 

print 100 % phin
print 130 % phin
print 131 % phin
print 132 % phin
Now let's calculate the result for values of d from 20 through 25.

Execute these commands: 

print (20 * e) % phin
print (21 * e) % phin
print (22 * e) % phin
print (23 * e) % phin
print (24 * e) % phin
print (25 * e) % phin
print (26 * e) % phin
print (27 * e) % phin
We weren't able to find a good value for d -- 26 resulted in 130, and 27 resulted in 3, as shown below. We went right past 1.
We'll have to use larger values and try to hit 1 the next time we go around the ring.

Execute these commands: 

print (50 * e) % phin
print (51 * e) % phin
print (52 * e) % phin
print (53 * e) % phin
We have a winner, as shown below! Let's use d = 53

Encrypting a Message

Meghan wants to get private email, so she uses the values above to generate her key pair, as shown below.

She publishes her public key to the cloud.

Cueball wants to send Meghan this message: 

Hi!
We can only send numbers. Let's encode that message with ASCII using the table below.

So the message is: 

72 105 33
A public key contains two numbers: n and e. To encrypt a message x, use this formula:

Execute these commands: 

print 72 ** e % n
print 105 ** e % n
print 33 ** e % n
As shown below, the encrypted message is 151 119 157

Decrypting the Message

To decrypt a message, use this formula:
Execute these commands: 
d = 53
print 151 ** d % n
print 119 ** d % n
print 157 ** d % n
As shown below, the decrypted message is 72 105 33 or Hi!.

Challenge 4a: Decrypt a Message (10 pts.)

Meghan gets another message, which was encrypted with her public key.

The encrypted message is 69 43 155 54 75 138 119 34 137

Decrypt it.

Use the form below to put your name on the WINNERS PAGE.

Your Name (without spaces):
The decrypted message:

Saving a Screen Image

Make sure the your name is visible on the winners page, as shown below.

Press Shift+PrintScrn to copy the whole desktop to the clipboard.

YOU MUST SUBMIT A FULL-SCREEN IMAGE FOR FULL CREDIT!

Paste the image into Paint.

Save the document with the filename "YOUR NAME Proj 4a", replacing "YOUR NAME" with your real name.

Challenge 4b: Cueball's Keys (10 pts. extra credit)

Cueball will use these values: p=13 q=41 e=7

Calculate Cueball's public and private keys.

Use the form below to put your name on the WINNERS PAGE.

Your Name (without spaces):
Cueball's Public Key, like this: (161,5):
Save a whole-screen image of the winners page showing your name with the filename "YOUR NAME Proj 4b".

Challenge 4c: Message to Cueball (10 pts. extra credit)

Meghan sends this message to Cueball. Decrypt it.

460, 364, 144, 153, 501, 402, 19, 311, 501, 280, 501, 80, 153, 382, 296, 153, 311

Hint: use the chr() and ord() functions

Use the form below to put your name on the WINNERS PAGE.

Your Name (without spaces):
Decrypted Message:
Save a whole-screen image of the winners page showing your name with the filename "YOUR NAME Proj 4c".

Turning in your Project

Email the images to cnit.141@gmail.com with the subject line: Proj 4 from YOUR NAME.

Sources

Cracking short RSA keys
Cueball image
Megan image
Cloud image

Posted 3-23-16 by Sam Bowne
Winners pages added 8-6-16
Attack server name updated 4-4-17
First challenge added 6-10-17
Updated 6-11-17
Updated 9-9-17 with email address