CS2911
Lab 8

Resources

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
  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.

Your break-key method should run in under 1 second. If it takes longer to run, seek a solution with lower asymptotic complexity (that is, lower Big-O run-time).

Euclid's Extended Algorithym

Euclid's extended algorithm can be expressed in pseudocode as

function inverse(a, n)
    t := 0
    r := n
    newt := 1    
    newr := a    
    while newr ≠ 0
        quotient := r div newr
        (t, newt) := (newt, t - quotient * newt) 
        (r, newr) := (newr, r - quotient * newr)
    if r > 1 then return "a is not invertible"
    if t < 0 then t := t + n
    return t

Note that the div must be integer division -- you will need to check this if you are unsure of it!

You do not need to understand how this algorithm works. You just need to understand that it is much faster (for large n) than the brute-force solution — and to implement it. You can check that it is working correctly by confirming that e * d mod z == 1 with the value for d it returns.

(Source: Wiki:Extended Euclidean algorithm)

Reflection Questions

Answer these questions on a separate piece of paper:

Question 1: RSA Security

In this lab, Trudy is able to find the private key from the public key. Why is this not a problem for RSA in practice?

Question 2: Critical Step(s)

When creating a key, Bob follows certain steps. Trudy follows other steps to break a key. What is the difference between Bob’s steps and Trudy’s so that Bob is able to run his steps on large numbers, but Trudy cannot run her steps on large numbers?

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) (Cracked Fall 2018 by Trey Gallun and Robert Laughlin in seconds using the Euclid's Extended Algorithm instead of the brute-force algorithm that I had recommended in previous years.)
  • Public key: (17, 843995751163) (40 bits) (Cracked Fall 2018 by Robert Laughlin)
  • Public key: (17, 667635191374471) (50 bits) (Cracked Fall 2018 by Robert Laughlin)
  • Public key: (17, 681577419272060989) (60 bits) (Cracked Fall 2018 by Robert Laughlin)
  • Public key: (17, 914079887227953688267) (70 bits) (Cracked Fall 2018 by Robert Laughlin)
  • Public key: (17, 798401852108697575069791) (80 bits)
  • Public key: (17, 985227196010493066836260157) (90 bits)
  • Public key: (17, 956424366058369634576511997901) (100 bits)
  • Pubilc key: (17, 845687515256677794057145483142257) (110 bits)
  • Public key: (17, 940562294173322057894192280217862479) (120 bits)
  • Public key: (17, 1050499240906169867321081277725674006861) (130 bits)
  • Public key: (17, 1010327588654592479489518715626174153572611) (140 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)

The public/private key challenges for 40 through 60 bits were generated with Robert Laughlin's manybit solution.

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.