Resources

• Please see your instructor's submission instructions for checklists, etc.
• 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.

As usual, during the following week's lab, be prepared to demo your code at the start of the lab.

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

This code solves the equation at mod n == 1 for 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) (Cracked Fall 2019 by Noah Horton)
• Public key: (17, 985227196010493066836260157) (90 bits) (Cracked Fall 2019 by Noah Horton)
• Public key: (17, 956424366058369634576511997901) (100 bits) (Cracked Fall 2019 by Noah Horton)
• Pubilc key: (17, 845687515256677794057145483142257) (110 bits) (Cracked Fall 2019 by Noah Horton)
• Public key: (17, 940562294173322057894192280217862479) (120 bits) (Cracked Fall 2019 by Noah Horton)
• Public key: (17, 1050499240906169867321081277725674006861) (130 bits) (Cracked Fall 2019 by Noah Horton)
• Public key: (17, 1010327588654592479489518715626174153572611) (140 bits) (Cracked Fall 2019 by Noah Horton)
• Public key: (17, 954408344258307963167386933095470926757906833) (150 bits)
• Public key: (17, 1206641416126754032441387494108570591309330651103) (160 bits)
• Public key: (17, 973607460392457781571715947566555017699035751061097) (170 bits)
• Public key: (17, 1259714232554985299730573571992530137288967940148051) (180 bits)
• Public key: (17, 1312146826492950870824970931914634678701075368845546689397) (190 bits)
• Public key: (17, 1196512127911231582816317581340375183596021484875123829415441) (200 bits)
• Public key: (17, 1037162170215981148162595975371513935975849254783561689103691833) (210 bits)
• Public key: (17, 1404131190791370871673426152438500624925171736630339525317380731369) (220 bits)
• Public key: (17, 1481552700383344055933482904750488579687052680001784844804329429651839) (230 bits)
• Public key: (17, 1166781500294932822435046762500592616133269207232610577169862084824250431) (240 bits)
• Public key: (17, 1280143490698562991877658497008603176185284136722957358532571624062751133109) (250 bits)
• Public key: (17, 1539848228786520040826487238449180551304039027373882663437229447176112893637937) (260 bits)
• Public key: (17, 1659075060954455867604017382906305728047100336653444290377489865916402989981399317) (270 bits)
• Public key: (17, 1283512215461296056514875744384594834671474449162818637949030242160366307042615054721) (280 bits)
• Public key: (17, 1382265026944875881636361054346212168035152512513954347684282446023649474984596575436707) (290 bits)
• Public key: (17, 1300920435356292271711234973757244178357467504556261393953604789988329283379771800701486581) (300 bits)
• Public keys and messages 300 bits-400 bits. In the interest of space on this page, keys longer than 300 bits are included in the linked file.

Noah Horton tried a variety of algorithms. His notes (edited for this context) are below:

Pollard's rho and Pollard's p-1 based on the algorithms from the respective wikipedia articles

Lenstra based on publicly available algorithm on wikipedia as well as publicly posted code

Primes are found using the python symbolic math library

Pollard's rho can deterministically break higher bit keys, but due to the increase in time, after n reaches 105 bit length it is skipped in favor of lenstra. With 10^8 iterations pollards rho solves ~100 bit numbers in around 3 minutes

Lenstra is probabilistic, so the runtime on higher bit numbers can be unpredictable, but in general it will be faster than Pollard's rho

Five iterations of Lenstra are used with a set upper bound, getting a new random starting point each time. After this, the upper bound is increased, and 5 iterations are performed again. This cycle continues indefinitely

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 140 bits were generated with Robert Laughlin's manybit solution.

The public/private key challenges for 150 bits and beyond were generated with Robert Laughlin's manybit solution, replacing the primality test with Miller-Rabin Primality testing