Table of Contents

CS 190C LAB 15: Friday, May 1, 2009

Final Exam Review

A sample final exam is posted on Blackboard for your reviewing pleasures.

Computability Review

In Lab Problem

Write a program that encrypts and decrypts simple lower-case strings using a substitution cipher, like a cryptoquote. Simply put, each letter is substituted with one other letter for encryption, and the process is reversed for decryption. Each letter must be replaced by a unique letter. Thus, A and B cannot both be replaced by C. An example key, or the mapping from the plaintext letters to the code letters, is given in cipher.txt. This is only one possible mapping; there are 26!-1 different mappings. Notice that each letter only appears once in both columns, which shows that each letter is transformed uniquely.

One popular mapping is known as rot13, where the alphabet is rotated halfway. Thus,

A B C D E F G ... 

maps to:

N O P Q R S T ...

If we wanted to encrypt “hello world”, we find the letter 13 positions after each letter (with wraparound, meaning o becomes b). Our result is then: “uryyb jbeyq”. To decrypt, we find the letter 13 positions *before* each letter. Note that a substitution cipher does not have to be a simple rotation like rot13 (the provided cipher is not such a case).

You are given the following function that will read the mapping from a file. However, it does not store the mapping; it is your choice how to store the data for easy and efficient lookup. There is more than one good choice, so COMMENT in why you chose to do it this way. This comment is required. You should take into account that you need to support both encrypt and decrypt operations.

def load_mapping(path):
    Load a mapping stored in a file at path.
    f = open(path)
    for line in f:
        u,v = line.strip().split()

Submit your file along with a comment on why you picked the mapping structure you picked on Blackboard.