Homework 4a - Crypto

This program exercises strings, lists, and main(). All parts of HW4 are due Wed Feb 5th at 11:55pm.

String Warmups

To get started, we have 4 small string exercises. Some problems say to solve with a particular loop form, so you get practice with both.

Solve with for/ch/s loop:

for ch in s:
    # use ch

Solve with for/i/range loop:

for i in range(len(s)):
    # use s[i]

> Str2 Warmups

Crypto Introduction

Download the crypto.zip and open the "crypto" folder in PyCharm to get started.

The beginnings of Computer Science are deeply tied up with the famous Alan Turing "Enigma Code" cryptography work in the heat of World War II, so it's neat that we can go a little bit into the area with this project.

We'll start with a little terminology. In cryptography, we take the original "plaintext", and encrypt it under the control of a key word, yielding an unintelligible "ciphertext". Decryption goes in the opposite direction, using the key to recover the plaintext from the ciphertext. Anyone who intercepts the ciphertext cannot make any sense of it without the key.

alt: plaintext to ciphertext and back, under control of key

In fact these same elements explain how your phone encryption works: There is a key stored in a chip in the phone, and it is only released by, say, the correct fingerprint. That key is used to encrypt all the data stored on the phone. Without the key, nothing can be read back.

For this project you'll implement a simple cipher, where each alphabetic char is encrypted as a different alphabetic char — so for example each 'a' is encrypted as an 'x' and 'i' as a 'b', and so on. The cipher is simple but includes all the features of cryptography — plain and cipher texts, encryption and decryptions, all under the control of a key.

Further reading: there's lots of interesting history and applied mathematics in cryptography. For a great introduction, see Simon Singh's "The Code Book".

Functions and Doctests

For this program, we are providing the function decomposition and their Doctests, so you can concentrate on writing and testing all the code, and seeing how the functions fit together.

A minor style idea about function calls: leveraging decomposed functions is a big part of this project, and you will often call a helper function to obtain a needed value, like say foo(x). However think about what is happening if the call is done inside a loop. If the function call is computing the exact same value again and again, it's a little wasteful. In that case, you could call the function once outside the loop, storing the computed value in a variable for use in the loop.

a. compute_slug(key)

We will use an encryption scheme that is simple enough it can be done on paper, as was done throughout history up until world war II.

We'll say that a "slug" is a len-26 list of the 26 lowercase chars a-z in some order. In a later step, the slug will drive the encryption of each char. The problem at this stage is to compute a len-26 slug from an easily memorized key like 'Bananas!'. All key/slug formation is done with lowercase alphabetic chars. ("slug" is a borrowed typesetting term, referring to a line of letters in a row.)

Here is the algorithm to compute a slug from a key: take the lowercase version of the key, and consider only the alphabetic chars in it. The first char is the first char of the slug, the second char is the second in the slug, and so on through all the chars of the key. However, if a char is already in the slug, skip it. A char can never be in the slug twice.

With the first few chars of the slug provide by the key, complete the slug by going through the regular alphabet 'abcde...' and appending each char to the end of the slug if it is not already in the slug. The resulting slug will be len-26 and contains every a-z char once at some position.

Here is the slug for the key 'Bananas!' You can see how the 'b' and 'a' and 'n' go at the front of the slug, followed by the rest of the regular alphabet.

compute_slug('Bananas!') -> 
['b', 'a', 'n', 's', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'o', 'p', 'q', 'r', 't', 'u', 'v', 'w', 'x', 'y', 'z']

The starter code includes the definition of a constant ALPHABET which is the a-z lowercase letters in a list. You should refer to this constant as ALPHABET in your code at spots where you need the standard a-z chars. Do not change the ALPHABET list; constants like are intended to be a read-only resource for the code, and it's a convention to give them upper-case names like this.

Implement the compute_slug() function. The 'z' key is so simple, its slug can be worked out by hand, which is how the Doctest was written.

compute_slug('z') -> 
['z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y']

b. encrypt_char(source, slug, char)

The function encrypt_char(source, slug, char) is the heart of this whole program. The function takes a "source" list which is a list of the lowercase characters that can be encrypted, and a "slug" list of the same length which shows the encrypted char to use for each source char.

Say we have these lists

source = ['a', 'b', 'c', 'd', ...]
slug   = ['z', 'a', 'b', 'c', ...]

To encrypt a char: find the lowercase version of the char in the source list. If it is in there, the char at the same index in the slug list is its encrypted form. So in the above example, the encrypted form of 'a' is 'z', the encrypted form of 'c' is 'b'. The encrypted output char should have the same upper/lower case as the input char, so the encrypted form of 'A' is 'Z' and the encrypted form of 'C' is 'B'. Do not use the ALPHABET constant in here. Use the "source" parameter - we let the caller of this function specify exactly the source/slug pair they want by passing them in vs. making any assumptions.

If a char to encrypt is not in the source list, such as a space ' ' or comma ',', then just return the char unchanged.

The test case for this uses the 'z' slug, shown here on 2 lines so it's easy to try encryptions by hand. For example 'A' should encrypt to 'Z'.

source = abcdefghijklmnopqrstuvwxyz
slug   = zabcdefghijklmnopqrstuvwxy

The provided Doctest looks like this:

>>> slug = ['z', 'a', 'b', 'c', 'd', 'e', ...'x', 'y']
>>> encrypt_char(ALPHABET, slug, 'A')
'Z'

The "slug =" line just creates the 'z' slug by hand, and then passes it in to the call to encrypt_char(). This way, encrypt_char() can be tested independently of compute_slug(). Alternately, we could call compute_slug() in the test, in which case encrypt_char() could only be tested when compute_slug() was working. In this case, working out the slug by hand was easy enough to do it that way.

Doctest quirk: inside the text of a Doctest the '\n' must be written with 2 backlashes '\\n'. The reason is that the '\n' expands to an actual newline in the Doctest which messes up the indentation. Using '\\n' represents that a newline is desired, but defers it.

c. encrypt_str(source, slug, s)

This function is just an application of your source/slug encryption to every char in a string. The test uses the last line from the The Eagle 'And like a thunderbolt he falls.\n'

d. decrypt_str(source, slug, s)

Given a string which was encrypted with the given source/slug, return its decrypted form.

Here you will have a chance to appreciate a small, satisfying moment of decomposition. The first important feature of decomposition is the ability to proceed in steps smaller than the whole program, testing each step on its own. You've done that many many times. Another key advantage of decomposition is re-use of code in multiple places.

The decrypt_str() function can be fully implemented with one line of code after its def.

The test case for here is just the reverses the earlier encryption of the The Eagle.

e. encrypt_file(), decrypt_file()

Implement these functions, which take in a filename and key, and print out either the encrypted or decrypted lines of the file. Refer to the ALPHABET constant in here when you need to refer to the plain alphabet. These functions do not have tests.

f. main()

Now it's time to implement a Python main().

def main():
    args = sys.argv[1:]
    # args is the list of command line arguments
    # 2 commmand line argument patterns:
    # -encrypt key filename
    # -decrypt key filename
    # Call encrypt_file() or decrypt_file() based on the args.
    pass

The real work is in your earlier functions, and the main() is just a little plumbing to call your functions with the right parameter values to start things off. This program has two modes -encrypt and -decrypt, all controlled by the "args" list of the command line arguments from the terminal.

This command line encrypts a file:

$ python3 crypto.py -encrypt akey afile.txt

For the above command line, len(args) == 3, args[0] is '-encrypt', args[1] is the key, and args[2] is the filename. Add code in main() so when the command line starts with '-encrypt', main() calls the encrypt_file() function with the appropriate parameters.

This command line decrypts a file:

$ python3 crypto.py -decrypt akey afile.txt

Add code in main() so the above command line calls the decrypt_file() function with the appropriate parameters.

Running With Real Data

With the main() filled in, you can run from the command line with real data and see the output.

$ python3 crypto.py -encrypt z the-eagle.txt
Gd bkzror sgd bqzf vhsg bqnnjdc gzmcr; 
Bknrd sn sgd rtm hm knmdkx kzmcr, 
Qhmf'c vhsg sgd zytqd vnqkc, gd rszmcr. 

Sgd vqhmjkdc rdz admdzsg ghl bqzvkr; 
Gd vzsbgdr eqnl ghr lntmszhm vzkkr, 
Zmc khjd z sgtmcdqanks gd ezkkr.

--Zkeqdc, Knqc Sdmmxrnm
$

The file "independence-crypt.txt" contains part of the declaration of independence encrypted with the 'Bleh' key. The "cat" command is used below is used first to display the encrypted file, then the decryption is run ("cat" works in the latest Windows PowerShell, the older equivalent Windows command is "type"):

$ cat independence-crypt.txt 
Wfan gn tfa Eoursa oc fumbn avants gt laeomas naeassbry cor ona paopka
to hgssokva tfa pokgtgebk lbnhs wfgef fbva eonnaetah tfam wgtf bnotfar
bnh to bssuma bmond tfa powars oc tfa abrtf, tfa sapbrbta bnh aqubk
stbtgon to wfgef tfa Kbws oc Nbtura bnh oc Nbtura's Doh antgtka tfam,
b haeant raspaet to tfa opgngons oc mbnjgnh raqugras tfbt tfay sfoukh
haekbra tfa ebusas wfgef gmpak tfam to tfa sapbrbtgon.

Wa fokh tfasa trutfs to la sakc-avghant, tfbt bkk man bra erabtah
aqubk, tfbt tfay bra anhowah ly tfagr Erabtor wgtf eartbgn unbkganblka
Rgdfts, tfbt bmond tfasa bra Kgca, Kglarty bnh tfa pursugt oc
Fbppgnass.
$ python3 crypto.py -decrypt Bleh independence-crypt.txt
When in the Course of human events it becomes necessary for one people
to dissolve the political bands which have connected them with another
and to assume among the powers of the earth, the separate and equal
station to which the Laws of Nature and of Nature's God entitle them,
a decent respect to the opinions of mankind requires that they should
declare the causes which impel them to the separation.

We hold these truths to be self-evident, that all men are created
equal, that they are endowed by their Creator with certain unalienable
Rights, that among these are Life, Liberty and the pursuit of
Happiness.

Look carefully at the cipher and plain texts, and you can see that the words and punctuation are all intact, just the letters have been shifted around by the encryption.

All Done

When your code is running nicely and has cleaned up style, turn in your crypto.py file on Paperless.

Mystery Crypt

The file mystery-crypt.txt contains this cipher text:

Wi'qi km stqckliqs tm hmvi
Ymu gkmw tbi quhis ckd sm dm E
C nuhh rmjjetjikt's wbct E'j tbekgekl mn
Ymu wmuhdk't lit tbes nqmj cky mtbiq luy
E fust wckkc tihh ymu bmw E'j niihekl
Lmttc jcgi ymu ukdiqstckd
Kiviq lmkkc levi ymu uo
Kiviq lmkkc hit ymu dmwk
Kiviq lmkkc quk cqmukd ckd disiqt ymu
Kiviq lmkkc jcgi ymu rqy
Kiviq lmkkc scy lmmdayi
Kiviq lmkkc tihh c hei ckd buqt ymu

The encryption key is a nice color around here. Just for fun, you can try decrypting with guesses to figure it out.

Addendum - Output Capture With >

This is just FYI, not part of the homework - how to capture the output of a program run in the terminal?

Normally when a program runs and does any printing, the text output appears in the terminal. There is a a famous terminal option (works in Windows too) to put "> output.txt" at the end of the terminal line, and that captures the output text and saves it to the named text file. You can run your program to see its output, and then run it with ">" to capture that output in a file. This is a very handy way to handle your data. Try this, and then you should be able to look at the file contents in PyCharm. This is how the files like the-eagle-crypt.txt were made:

$ python3 crypto.py -encrypt z the-eagle.txt > test-crypt.txt
$ cat test-crypt.txt
Gd bkzror sgd bqzf vhsg bqnnjdc gzmcr; 
Bknrd sn sgd rtm hm knmdkx kzmcr, 
Qhmf'c vhsg sgd zytqd vnqkc, gd rszmcr. 

Sgd vqhmjkdc rdz admdzsg ghl bqzvkr; 
Gd vzsbgdr eqnl ghr lntmszhm vzkkr, 
Zmc khjd z sgtmcdqanks gd ezkkr.

--Zkeqdc, Knqc Sdmmxrnm