Resources

• Lab Checklist — I will provide a paper copy of this.
• CS2911 Coding Standard

Overview

In this lab, you will create and brute-force attack 16-bit RSA encryption. Before you can play out these scenarios, you will need code to create and use a public & private key.

Once your code is written, assign the roles of Alice, Bob, and Trudy to a person on your team.

Pre/In-lab procedure

Complete the in-class exercise before you start writing code to get the tactile experience of how RSA works.

Before the lab period starts, write and confirm that your RSA code creates keys that successfully encrypt/decrypt at least most of the time. During lab, make sure it works all the time.

1. Download rsa.py (The template has been updated to clarify the parameter of the apply_key method: :param int m: the message as a number 1 < m < n (roughly) and to correct an error in the parameter description which should read :param tuple key: (e,n) or (d,n))
2. Put your names at the top of the file.
3. Create a design for the methods create_keys and apply_key in rsa.py. See the documentation for these methods in the rsa.py template. One of these methods requires significantly more work than the other. Complete your design as a team, then divide up the work for the most challenging method among the members of the team. Implement Euclid's Extended Algorithm for finding d (Pseudocode below).
4. As a team, create a design for the method break_key. If you design create_key well, break_key should be easy to write, only requiring two new methods
5. Individually, fill out your own part of the design for the sub-methods of create_keys
6. Individually, fill out your own part of the design for the sub-methods of break_key (if you are assigned one of these)
7. As a team, combine all of the methods and test that they work.
8. Bob: Run the program and create a public/private key pair. Deliver the public key to Alice. (You can reuse the key from Step 5 if you like.)
9. Alice: Create a secret message. Encrypt it with Bob’s public key using the encrypt_message option of the program. Supply Bob and Trudy with the encrypted message. (You may need to email the hexadecimal characters to Bob and Trudy — or share them on IM.)
10. Bob: Run the program with the decrypt_message option to read Alice’s secret message using your private key.
11. Trudy: Run the program with the break_key option to read Alice’s secret message using only the public key.

Euclid's Extended Algorityhm

Euclid's extended algorithm can be expressed in pseudocode as

TBA

(Source: Wiki:Extended Euclidean algorithm)

Excellent Credit

In this excellent-credit exercise, we will pretend that we are using enough bits so that break_key is ineffective. Nevertheless, because we use a non-cryptographic hash, Alice can forge a message to look like the one Bob signed with his public key.

1. Bob: Run the program with the compute_checksum option to create an encrypted checksum for the message "Bob owes Trudy $100.99". Save the public & private keys, as well as the encrypted checksum for your records. Provide Alice and Trudy with the public key. Provide Trudy with the plain-text message and the encrypted checksum. (Suppose that Trudy is an unscrupulous online store)
2. Trudy: Create a message that results in the same checksum as Bob’s message, but implies that Bob owes a larger amount of money. Hint: If you rearrange the characters in the string, how does that change the checksum? Supply Alice with the forged message and the encrypted checksum that Bob gave you.
3. Alice: Check Trudy’s message using the verify_checksum option of the program. Does it check out OK? If not, Trudy should keep trying.
4. As a team: Explain in your final comments how Trudy can be prevented from performing this trick in a real application. (Suppose Alice is the bank responsible for transferring the money from Bob to Trudy. And note that Trudy did not use break_key here!)

Just for Fun

It's fairly easy to modify our simple RSA algorithm to run for an arbitrary number of bits -- albeit slower and slower. Just for fun (not even excellent credit), migrate your code to the rsa-many-bit.py template, and see how long it takes you to crack the keys below.

If you want to use the encrypt/decrypt functionality provided in the rsa-many-bit tempate, you must re-write your apply_key method to use the three argument pow() method, or it will take too long to run.

• Public key: (17, 262439711) (28 bits) (Cracked Fall 2016 by Eric Nowac, Evan Richardson)
• Public key: (17, 245733727) (28 bits) (Cracked Fall 2016 by Eric Nowac, Evan Richardson)
• Public key: (17, 1058904137) (30 bits) (Cracked Fall 2016 by Evan Richardson)
• Public key: (17, 3869374409) (32 bits) (Cracked Fall 2016 by Eric Nowac (1.3 hrs), Evan Richardson)
• Public key: (17, 16483395023) (34 bits) (Cracked Fall 2016 by Evan Richardson)
• Public key: (17, 65854648177) (36 bits) (Cracked Fall 2016 by Evan Richardson (~1 hr on i7-6700m processor running Linux))
• Public key: (17, 180672543437) (38 bits)

Acknowledgement

The simple form of the RSA encryption/decryption used in this exercise is based on Avi Kak’s lecture notes on cryptography, available here, and from our text, Kurose & Ross, Computer Networking: A Top-Down Approach, 7th Edition, Section 8.2.2, pp. 606-610 (6th edition, same section, pp. 684-688)

Submission

Please submit your file below for testing during lab. Also submit the lab checklist as usual, with your printed code attached. Please make sure your usernames are separated by underscores and in alphabetical order.