Introduction to Computer Programming

Program 3: Cryptology (via lists)

Due date: Friday, October 13 at 5pm


Instructions


Background

The primary goal of this assignment is to implement monoalphabetic substitution ciphers: how to encrypt and decrypt messages using them and how to cryptanalyze them using frequency analysis. To better understand these principles you will need to read pp. 1-25 of Simon Singh's The Code Book. (The excerpt is available via e-reserve on MySLC.)

We represent keys as 26-letter strings of uppercase letters where each letter appears exactly once. (In other words, a key can be thought of as a permutation of the uppercase alphabet.) Examples include:

To manually use a key to encrypt a string, we can line up the alphabet with the key, like this:

abcdefghijklmnopqrstuvwxyz
COMPUTERSINABDFGHJKLQVWXYZ

then to encrypt "headache" using that key, we find the cipher letter corresponding to each plain letter so we get "RUCPCMRU" like this:

headache
RUCPCMRU

You can use the supplied function is_valid_key to test if a given string is a valid key. For example:

>>> from hw3_aux import is_valid_key
>>> is_valid_key('RNTSAJKBXEGIWFLOVMPDZQUHCY')
True
>>> is_valid_key('RNTKBXEGIWFLOVMPDZQUHCY')
False
>>> is_valid_key('RNTKBXEGIWFLOVMPDZQUHCYSAJSAJ')
False
>>> is_valid_key('RNTKbxegiwflOVMPDZQUHCYSAJ')
False
>>> is_valid_key('RNTKBXEGIWFLOVMPDZQUHCYSA!')
False

The assignment itself

  1. Download all three files: the starter file, the helper file, and the main REPL. The first is the starter file where all your code will go. The second is a file consisting of helpful functions that you can (and should!) call in your code. The third is the REPL which has been written for you and requires no action on your part - it calls the code in the other two files. Out of the box, if all three files are in the same folder and you run the REPL file it will start the top-level function crypto_repl which will give you a basic menu of options for creating keys, encrypting text, decrypting text, and performing frequency analysis. Several of the features have been implemented for you. Experiment extensively with the REPL before starting to write code.

  2. Complete the function make_random_key() so that it returns a string consisting of a randomized arrangement of all 26 uppercase letters. For example:

    >>> make_random_key()
    'RNTSAJKBXEGIWFLOVMPDZQUHCY'

    (You are encouraged to simplify your efforts by using join, list, random.shuffle and string.ascii_uppercase.)

  3. Complete make_shift_key(k) so that it returns a key string (an arrangement of all 26 uppercase letters) that corresponds to shifting the alphabet forward by k places. You can assume k is not negative and that it is less than 26. For example:

    >>> make_shift_key(3)
    'DEFGHIJKLMNOPQRSTUVWXYZABC'

    (You may use lists, join, append, and the supplied decode function. The % operator may come in handy.)

  4. Complete encrypt(key, text) so that it returns the encrypted version of text using key as a monoalphaetic substitution key. It should only apply the substitution to uppercase letters; all other symbols should remain as is. Examples:

    >>> encrypt('DEFGHIJKLMNOPQRSTUVWXYZABC', 'NOW IS THE TIME!')
    'QRZ LV WKH WLPH!'
    >>> encrypt('DEFGHIJKLMNOPQRSTUVWXYZABC', 'Careful')
    'Fareful'

    (Use a for loop over a string and the supplied encode function.)

  5. Complete invert_key(key) so that it returns a new key that is the inverse of key. For example:

    >>> invert_key('DEFGHIJKLMNOPQRSTUVWXYZABC')
    'XYZABCDEFGHIJKLMNOPQRSTUVW'
    >>> invert_key('RNTSAJKBXEGIWFLOVMPDZQUHCY')
    'EHYTJNKXLFGORBPSVADCWQMIZU'

    By completing invert_key, decryption should now work.

  6. Complete uniquify(s) so that it returns a new string consisting of only one copy of each of the uppercase letters in the order they occur in s. Examples:

    >>> uniquify('')
    ''
    >>> uniquify('COOL')
    'COL'
    >>> uniquify('EVER AND EVER!')
    'EVRAND'
    >>> uniquify('Even The Losers Get Lucky Sometimes')
    'ETLGS'
  7. Complete make_phrase_key(phrase) so that it returns a key string built from phrase. Case is ignored in forming the key; all other (i.e., nonalphabetic) symbols are ignored. If the key would not be a full 26 symbols, the remainder of the unused alphabet, in order, should be added to the string. Examples:

    >>> make_phrase_key('')
    'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    >>> make_phrase_key('RNTSAJKBXEGIWFLOVMPDZQUHCY')
    'RNTSAJKBXEGIWFLOVMPDZQUHCY'
    >>> make_phrase_key('The quick brown fox jumps over the lazy dog.')
    'THEQUICKBROWNFXJMPSVLAZYDG'
    >>> make_phrase_key('Computer science')
    'COMPUTERSINABDFGHJKLQVWXYZ'

  8. Complete count_letters(s) so that it returns an array of 26 numbers indicating how many times each letter of the alphabet occurs in s. Case should be ignored; no other symbols should be counted. Example:

    >>> count_letters('A man. A plan. A canal. Panama!')
    [10, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  9. Complete histogram(a, n, symbol) so that, given that a is array of numbers, n is an integer, and symbol is a single-character string, it returns a new array of the same length but where each item is a string consisting of 0 or more copies of symbol, the length of each strength is proportional to the corresponding value in a, and largest value in a corresponds to a n-letter string in the returned array. Example:

    >>> histogram([5, 3, 7], 10, '#')
    ['#######', '####', '##########']
    >>> histogram([37, 0, 4, 19, 12], 5, '*')
    ['*****', '', '*', '***', '**']
  10. Complete visualize_frequencies(s) so that it returns a string that represents a histogram of the frequencies of the letters occurring in s. Example:

    >>> t = visualize_frequencies('Peter piper picked a peck of pickles')
    >>> print(t)
    A: ########
    B:
    C: #########################
    ...
    P: ##################################################
    ...
    T: ########
    U:
    ...
    Z:

    By completing visualize_frequencies, the frequency analysis feature of the crypto REPL should now work.


Extra credit