(Beta) Problem Set 1: Code Cracking

The questions below are due on Friday May 09, 2025; 05:00:00 PM.
 

Download Files

1) Pset Beta-Testing Info

Thank you so much for beta-testing the psets that we'll be using for the new and improved version of 6.100A/B in the fall! A few important notes:

• As soon as you see this, if you will be beta-testing this pset please drop your kerb in this form. Do it right now please!! This is so that if I discover mistakes in the pset and need to let you know about it, I can email you.
• Along those lines, if you discover mistakes or ambiguities in the pset that make it difficult to complete the pset properly, feel free to let me know at abbychou@mit.edu.
• If you're a 6.100L student, you can get a few extra credit points for doing either this pset and/or the beta of pset 2. To get credit, you must come to my (Abby's) OH (see below) and do a checkoff with me BEFORE the pset due date of 5pm on Friday, May 9.
• Checkoffs and Office Hours: I (abby) will be running all help and checkoffs for the beta-tested psets, so you won't be able to get help during all of the normal 6.100 office hour times. Here is a gcal that tells you when I'll be at OH, so you can get help and/or do your checkoff! Just come to the normal OH room but don't bother hopping on the queue: just look for me (I am an asian gal with very long hair).
• As you work, please record how long it takes you to complete each section of the pset.
• Also please jot down anything you found confusing, plus anything that might be difficult for new programmers. This would be the very first pset of 6.1000 (which is 6.100A and B merged together). While the students in 6.1000 will have more programming experience than you may have had when you entered 6.100L, many of them will have no python experience. So put yourself back in the shoes of when you were new to programming, and let us know what parts of the pset may create pain points. Before seeing this pset, we will have taught the 6.1000 students variables/basic python syntax, loops, lists, and functions.

2) Introduction

Since the invention of writing, humans have attempted to exchange coded texts. They do this by running their message, or "plain text", through an algorithm that uses a key to encrypt it into a cipher text. If the recipient of the cipher text has access to a corresponding decryption algorithm and the key, they can decipher to the cipher text to recover the plain text.

If you're unfamiliar with the concept of ciphers, read a bit on the caesar cipher to get a feel for how they work.

This problem set uses a cipher algorithm called a john-cipher. The encryption key is a pair of two numbers: an initial_shift and a magic_number. The algorithm shifts each letter in the plaintext a certain number of characters forward in the alphabet. For the first letter, it will be shifted by initial_shift. But each time it produces a character c for the cipher text, it checks whether the index of c in the alphabet is a multiple of magic_number. If so, it increments the shift by 1. For example, if initial_shift = 1, magic_number = 2, and alphabet = 'abcdefghijklmnopqrstuvwxyz', it will encrypt abb as bcd (Remember that in programming, we 0-index, so the character 'a' has index 0, 'b' has index 1, 'c' has index 2, etc.).

2.1) File setup

Download the file beta_ps1.zip and extract all files to the same directory. The files included are:

• ps1.py: This is the main file where you will implement the required functions for the problem set and is the only file you need to modify. Do NOT modify the function signatures. You may, however, create additional helper functions.
• words.txt: This is a text file containing all the words in the English language, which ps1.py uses when checking whether a certain string is a word.
• test_ps1_student.py: This file contains pre-written test cases that will help you check the correctness of your implementation.

3) Encrypt

We have provided functions shift_char and encrypt for you. Read over the code and make sure you know what the provided code is doing. You will be asked to explain the following during checkoff:

• How does shift_char handle wraparound? For example, if the alphabet is 'abcdefghijklmnopqrstuvwxyz' and we want to shift 'w' by 5, how does the code handle this?
  • How does the code handle wraparound for a negative shift?
• In the encrypt function, what does alphabet.find(c) % magic_number represent? Give an example of a case when alphabet.find(c) % magic_number == 0 and one where alphabet.find(c) % magic_number != 0. (An example means you choose c and magic_number, assuming a basic alphabet of lowercase letters 'abcdefghijklmnopqrstuvwxyz')

4) Decrypt

Implement the decrypt function according to the spec! Your implementation should make use of the provided shift_char function.

To test your implementation, uncomment the relevant part of the __main__() method at the bottom of the file. You should also be passing the relevant test cases in test_ps1_student.py. Now, as long as both sides have access to the inital shift and the magic number, you can use your encrypt and decrypt functions to exchange secret messages!

5) Crack Cipher (aka Hacker Mode)

Previously, you were an honest cipher user, encrypting and decrypting messages for which you know the key (the pair of the initial_shift and magic_number). But what if you intercept a message encrypted with the John-Cipher and you want to crack it without knowing the key?

Implement the crack_cipher function according to the spec. Your function should brute-force try all possible pairs of inital shift and magic number, and use the one that yields plaintext containing the most valid English words. We have provided the helper function is_word for you, that makes use of the dictionary of all English words loaded by the load_words function (also provided).

6) Hand-in procedure

Run test_ps1_student.py to check the correctness of your functions. If a test case fails, read the error message carefully to understand what went wrong and debug accordingly. The autograder on the website will be primarily the test cases from this student tester file, along with a few hidden tests.

6.1) Time info

How long did this problem set take you to complete? Please answer in hours.

Loading...

6.2) Submission

Before you submit your files, remove all extra debugging print statements.

Be sure to run the student tester and ensure all tests pass. However, the student tester contains only a subset of the tests that will be run to determine the problem set grade. Passing all of the provided test cases does not guarantee full credit on the pset.

You may upload new versions of each file until the deadline, and no late days may be used. Please note that we will only be grading your last submission.

Select File No file selected

Loading...