INST326 Homework 03

The assignments below comprise your third homework assignment. Provide the implementations requested.

You will be graded on the following rubric:

  • Documentation: Your code should be sufficiently documented so as to demonstrate you have an understanding of what your code is doing. This point is especially important if you are citing code from the Internet.
  • Execution: Your code should at least execute. If your code does not run, you will get no points for this criteria.
  • Correctness: Your code should implement the specifications provided correctly.
  • Efficiency: While not a major factor, be prepared to have points counted off if your code is extremely inefficient (e.g., looping through a list without apparent need).

NOTE While you may work in groups to discuss strategies for solving these problems, you are expected to do your own work. Excessive similarity among answers may result in punitive ac

Basic Encryption and Decryption

In the days before the Internet, radio, and telephones, when military commanders needed to issue orders to their subordinates, they relied on written messages. These messages could be highly sensitive as they might detail plans, times, and locations for attacks, troop movements, guard numbers, provision details, or other critical pieces of information. Therefore, it was of vital importance that these written messages be kept from enemy hands.

But what if a messenger was intercepted while relaying these messages? To prevent this vital information from being discovered, military commanders developed various methods for protecting their messages using ciphers.

A cipher is an algorithm for converting a plaintext message into encrypted/obfuscated ciphertext, generally with the use of some key that is known only to the sender and receiver. This ciphertext should be uninformative to a reader who does not have the key.

In this homework, you will implement two well-known ciphers that were popular before computers came about and made cracking such ciphers trivial.

Caesar Shift Cipher

Julius Caesar was known for using a rotation cipher when sending messages to his commanders. A rotation cipher is characterized by taking each letter in a plaintext string and rotating it some number of letters in the alphabet to create the ciphertext. The size of this rotation is the key for a rotation cipher.

For example, in the image below, the plaintext string is rotated by three, which is the key Caesar generally used when enciphering (i.e., encrypting) his messages.

Here, we see the letter "A" is rotated to "D", "B" becomes "E", "C" becomes "F" and so on.

Alphabet Boundaries

While straightforward, how do rotation ciphers handle the ends of the alphabet? For example, with a rotation key of 3, what happens to the letter "Z"?

Simple: "Z" wraps around to the beginning of the alphabet to become "C". Likewise, "Y" becomes "B", and "X" becomes "A". The image below shows the entire rotation for the alphabet.

Decryption

To decrypt the ciphertext produced by a Caesar shift, you rotate the alphabet in the opposite direction ("installation is the reverse of removal"). Hence, "A" becomes "X", "B" becomes "Y", "C" becomes "Z", etc.


Homework Problem 1 - Implementing a Caesar Shift

For this problem, write a pair of functions encrypt_caesar(plaintext) and decrypt_caesar(ciphertext) that implements Caesar's shift cipher.

Remember the Caesar shift cipher rotates by 3 letters to the right, so you can decrypt by rotating 3 letters to the left.

Handling Cases, Punctuation, and Numbers

When you encounter numeric, spaces, or punctuation characters in your plaintext, simply ignore them and pass them through to your ciphertext unchanged.

For this first iteration of your rotation cipher, you can also assume all strings will be in lower case, so you don't have to worry about the complexity of handling cases.

In [5]:
# Provide your encryption and decryption implementations here

# There are a few ways to go about writing these functions
## You could make a dictionary that maps input letters to output letters
## You could use ord() and chr() functions to get the ASCII representations and add or subtract
## You could write a large number of if statements that do the mapping for you

# Useful import for string.ascii_lowercase
import string

# Encryption function
def encrypt_caesar(plaintext):
    """Encrypt the plaintext using Caesar's shift, which shifts right by 3 letters"""
    
    ciphertext = ""
    
    for letter in plaintext:
        if ( letter in string.ascii_lowercase ):
            zeroedAsciiValue = ord(letter) - ord("a")
            rotatedValue = (zeroedAsciiValue + 3) % 26
            rotatedAsciiValue = rotatedValue + ord("a")
            rotatedAscii = chr(rotatedAsciiValue)
            ciphertext += rotatedAscii
        else:
            ciphertext += letter
        
    return ciphertext

# Decryption function
def decrypt_caesar(ciphertext):
    """Decrypt the ciphertext using Caesar's shift, which shifts right by 3 letters"""
    plaintext = ""
    
    for letter in ciphertext:
        if ( letter in string.ascii_lowercase ):
            zeroedAsciiValue = ord(letter) - ord("a")
            rotatedValue = (zeroedAsciiValue - 3) % 26
            rotatedAsciiValue = rotatedValue + ord("a")
            rotatedAscii = chr(rotatedAsciiValue)
            plaintext += rotatedAscii
        else:
            plaintext += letter
    
    return plaintext

Below is a skeleton for testing your encryption and decryption functions on small strings.

In [6]:
# The following strings are plain text that you should encrypt
plaintext_list = [
    "this is a test",
    "caesar’s wife must be above suspicion",
    "as shatner would say: you, should, also, be, able, to, handle, punctuation.",
    "to mimic chris walken: 3, 2, 1, why must you, pause, in strange places?",
]

# The following strings are encrypted versions of the above plain text
## Each element of this list corresponds to the element of the same
## position in the list above.
ciphertext_list = [
    "wklv lv d whvw", 
    "fdhvdu’v zlih pxvw eh deryh vxvslflrq", 
    "dv vkdwqhu zrxog vdb: brx, vkrxog, dovr, eh, deoh, wr, kdqgoh, sxqfwxdwlrq.", 
    "wr plplf fkulv zdonhq: 3, 2, 1, zkb pxvw brx, sdxvh, lq vwudqjh sodfhv?",
]

# Iterate through the lists above and encrypt/decrypt
sampleCount = len(plaintext_list)
for i in range(sampleCount):
    
    # Get the actual plain and cipher texts
    actual_plaintext = plaintext_list[i]
    actual_ciphertext = ciphertext_list[i]
    
    # Compute the encrypted and decrypted forms
    computed_ciphertext = encrypt_caesar(actual_plaintext)
    computed_plaintext = decrypt_caesar(actual_ciphertext)
    
    # Ensure the encrypted version matches what we expect
    assert(computed_ciphertext == actual_ciphertext)
    
    # Ensure the decrypted version matches what we expect
    assert(computed_plaintext == actual_plaintext)

Assignment 1b - Testing Your Caesar Shift Code on Files

I have provided a test file: test01b_caesar_shift_ciphertext.txt. Write code to read this file, decrypt the ciphertext, and print the contents. I will use a similar method to grade your work.

I suggest you break the files into lines using readlines() and iterate through these lines, decrypting each line. You can also read the entire file in one go and decrypt, but this approach may make debugging difficult.

In [8]:
# Open the file
with open("test01b_caesar_shift_ciphertext.txt", "r") as inFile:
    for line in inFile:
        print(decrypt_caesar(line.lower().strip()))
aquarius
there's travel in your future when your tongue freezes to the back of a speeding bus
fill that void in your pathetic life by playing whack-a-mole seventeen hours a day

pisces
try to avoid any virgos or leos with the ebola virus
you are the true lord of the dance, no matter what those idiots at work say

aries
the look on your face will be priceless when you find that forty pound watermelon in your colon
trade toothbrushes with an albino dwarf, then give a hickey to meryl streep

taurus
you will never find true happiness - what you gonna do, cry about it?
the stars predict tomorrow you'll wake up, do a bunch of stuff, and then go back to sleep

that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today
that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today

gemini
your birthday party will be ruined once again by your explosive flatulence
your love life will run into trouble when your fiance hurls a javelin through your chest

cancer
the position of jupiter says you should spend the rest of the week face down in the mud
try not to shove a roll of duct tape up your nose while taking your driver's test

leo
now is not a good time to photocopy your butt and staple it to your boss's face, oh no
eat a bucket of tuna-flavored pudding, then wash it down with a gallon of strawberry quik

virgo
all virgos are extremely friendly and intelligent - except for you
expect a big surprise today when you wind up with your head impaled on a stick

that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today
that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today

now you may find it inconceivable or at the very least a bit unlikely that the relative position of the planets and the stars could have a special deep significance or meaning that exclusively applies to only you, but let me give you my assurance that these forecasts and predictions are all based on solid, scientific, documented evidence, so you would have to be some kind of moron not to realize that every single one of them is absolutely true.

where was i?

libra
a big promotion is just around the corner for someone much more talented that you
laughter is the very best medicine, remember that when your appendix bursts next week

scorpio
get ready for an unexpected trip when you fall screaming from an open window
work a little harder on improving your low self-esteem, you stupid freak

sagittarius
all your friends are laughing behind your back (kill them)
take down all those naked pictures of ernest borgnine you've got hanging in your den

capricorn
the stars say that you're an exciting and wonderful person, but you know they're lying
if i were you, i'd lock my doors and windows and never never never never never leave my house again

that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today
that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today

that's your horoscope for today (that's your horoscope for today)
that's your horoscope for today
that's your horoscope for today (yay yay yay yay yay)
that's your horoscope for today

Homework Problem 2 - General Rotation Cipher

Extend your Caesar shift code above to accept a key, representing the number of letters by which you shift. Provide implementations for encrypt_rotation(keyValue, plaintext) and decrypt_rotation(keyValue, ciphertext). Recall in the Caesar shift, you rotate by 3, so calling your encrypt and decrypt functions with keyValue = 3 and keyValue = -3 should give you the same results as your functions above.

This time, also provide your own test cases.

In [9]:
# Provide your encryption and decryption implementations here

# Encryption function
def encrypt_rotation(keyValue, plaintext):
    """Encrypt the plaintext using a rotation by keyValue letters"""
    ciphertext = ""
    
    for letter in plaintext:
        if ( letter in string.ascii_lowercase ):
            zeroedAsciiValue = ord(letter) - ord("a")
            rotatedValue = (zeroedAsciiValue + keyValue) % 26
            rotatedAsciiValue = rotatedValue + ord("a")
            rotatedAscii = chr(rotatedAsciiValue)
            ciphertext += rotatedAscii
        else:
            ciphertext += letter
        
    return ciphertext

# Decryption function
def decrypt_rotation(keyValue, ciphertext):
    """Decrypt the ciphertext using a rotation by keyValue letters"""
    """Decrypt the ciphertext using Caesar's shift, which shifts right by 3 letters"""
    plaintext = ""
    
    for letter in ciphertext:
        if ( letter in string.ascii_lowercase ):
            zeroedAsciiValue = ord(letter) - ord("a")
            rotatedValue = (zeroedAsciiValue - keyValue) % 26
            rotatedAsciiValue = rotatedValue + ord("a")
            rotatedAscii = chr(rotatedAsciiValue)
            plaintext += rotatedAscii
        else:
            plaintext += letter
    
    return plaintext
In [11]:
# The following strings are plain text that you should encrypt
plaintext_list = [
    "to mimic chris walken: 3, 2, 1, why must you, pause, in strange places?",
    "don't take life too seriously. you'll never get out alive",
]

# This lists the rotation keys the connect the plaintext to the ciphertext
rotation_keys = [
    3,
    13,
]

# The following strings are encrypted versions of the above plain text
## Each element of this list corresponds to the element of the same
## position in the list above.
ciphertext_list = [
    "wr plplf fkulv zdonhq: 3, 2, 1, zkb pxvw brx, sdxvh, lq vwudqjh sodfhv?",
    "qba'g gnxr yvsr gbb frevbhfyl. lbh'yy arire trg bhg nyvir"
]

# Iterate through the lists above and encrypt/decrypt
sampleCount = len(plaintext_list)
for i in range(sampleCount):
    
    # Get the actual plain and cipher texts and key
    actual_plaintext = plaintext_list[i]
    rotation_key = rotation_keys[i]
    actual_ciphertext = ciphertext_list[i]
    
    # Compute the encrypted and decrypted forms
    computed_ciphertext = encrypt_rotation(rotation_key, actual_plaintext)
    computed_plaintext = decrypt_rotation(rotation_key, actual_ciphertext)
    
    # Ensure the encrypted version matches what we expect
    assert(computed_ciphertext == actual_ciphertext)
    
    # Ensure the decrypted version matches what we expect
    assert(computed_plaintext == actual_plaintext)

Frequency Analysis

A major weakness of these rotation ciphers is that the relative frequency of common letters is not altered. For example, the letter "e" is much more common in English than the letter "q".

With this knowledge, you can reverse out the rotation key by finding the most common letter in the ciphertext and checking rotation keys that will map that common cipher letter to a common plain-text letter.

Homework Problem 3 - Find Most Common Letters

Write a function most_common_letters(text) that returns a dictionary that maps letters to their frequencies. Once again, ignore punctuation. Hint: You can easily check if a character should be counted by checking whether character in string.ascii_letters == True, but be sure to import string first. For handling letter case, however, convert all strings to lowercase (frequency analysis is case-insensitive anyway).

For example, given the following text string:

we the people of the united states, in order to form a more perfect union, establish justice, insure domestic tranquility, provide for the common defence, promote the general welfare, and secure the blessings of liberty to ourselves and our posterity, do ordain and establish this constitution for the united states of america.

You should return a dictionary like this:

[('j', 1),
 ('q', 1),
 ('w', 2),
 ('v', 2),
 ('g', 2),
 ('y', 3),
 ('b', 4),
 ('p', 6),
 ('m', 7),
 ('c', 8),
 ('h', 9),
 ('l', 9),
 ('f', 9),
 ('u', 10),
 ('d', 11),
 ('a', 14),
 ('n', 17),
 ('i', 20),
 ('s', 20),
 ('r', 20),
 ('o', 25),
 ('t', 29),
 ('e', 39)]
In [18]:
# Provide your implementation here

def most_common_letters(text):
    freqDict = {}
    
    for letter in text.lower():
        if ( letter in string.ascii_lowercase ):
            freqDict[letter] = freqDict.get(letter, 0) + 1
    
    return freqDict

testText = """we the people of the united states, in order to form 
a more perfect 
union, establish justice, insure domestic tranquility, provide for 
the common defence, promote the general welfare, and secure the 
blessings of liberty to ourselves and our posterity, do ordain and 
establish this constitution for the united states of america."""

counted = most_common_letters(testText)
for key in sorted(counted, key=counted.get):
    print(key, counted[key])
j 1
q 1
w 2
v 2
g 2
y 3
b 4
p 6
m 7
c 8
h 9
l 9
f 9
u 10
d 11
a 14
n 17
i 20
s 20
r 20
o 25
t 29
e 39

Assignment 3b - Code Breaking

I have provided an encrypted text file test03b_encrypted_ciphertext.txt but have not provided the key. Use your implementation above to determine the key, decrypt the file using your decrypt_rotation(keyValue, ciphertext) function, and print the results to the screen.

In [29]:
# Open the file
with open("test03b_encrypted_ciphertext.txt", "r") as inFile:
    fileText = inFile.read().lower().strip()
        
    # Find the most common letter in the cipher text
    counted = most_common_letters(fileText)
    sortedKeys = sorted(counted, key=counted.get)
    print("Most Common:", sortedKeys[-1])
    
    # Guess the rotation key
    rotGuess = ord(sortedKeys[-1]) - ord("e")
    print("Guessed Rotation:", rotGuess)

    # Decrypt the file and print its contents
    print(decrypt_rotation(rotGuess, fileText))
    
    #### Most common didn't work, let's try the next most common
    
    # Guess the rotation key
    rotGuess = ord(sortedKeys[-2]) - ord("e")
    print("Guessed Rotation:", rotGuess)

    # Decrypt the file and print its contents
    print(decrypt_rotation(rotGuess, fileText))
Most Common: v
Guessed Rotation: 17
reoep pejuqnh.yki/453pg3v
bkn w bqj wjz wjjkuejc peia

@hapgwjuabejeod e wi w xkp. opwnp w psaap sepd @hapgwjuabejeod, wjz e sehh bejeod ep. gwjua opuha.

@hapgwjuabejeod kj w pqaozwu e okiapeiao swga ql ej pda iknjejc wjz pdejg wxkqp sdwp opanakpulao pk xnawg

@hapgwjuabejeod bejwho ckp ia hega e'i ejowja, hega e'i ejowja, hega e'i ejowja, hega e'i ejowja, hega e'i dephan.


@hapgwjuabejeod e fqop skj w pnqyg bqhh kb laklha, gwjua zkaoj'p ywna wxkqp wna pda bwjo.
Guessed Rotation: 13
visit tinyurl.com/453tk3z
for a fun and annoying time

@letkanyefinish i am a bot. start a tweet with @letkanyefinish, and i will finish it. kanye style.

@letkanyefinish on a tuesday i sometimes wake up in the morning and think about what stereotypes to break

@letkanyefinish finals got me like i'm insane, like i'm insane, like i'm insane, like i'm insane, like i'm hitler.


@letkanyefinish i just won a truck full of people, kanye doesn't care about are the fans.

Assignment 4 - Brute Force

While frequency analysis was a powerful tool, another weakness with rotation ciphers is that they provide little security in the face of modern computing power. It takes very little computing power to try all possible rotations.

To that end, write a function brute_force_decrypt(ciphertext) that takes some ciphertext and tries all possible rotations (how many are there?). The brute_force_decrypt() function should return an array of potentially good rotation keys. Write a separate function is_good_key(key, plaintext, sentinel) that accepts a candidate rotation key, a plaintext string, and a common keyword for which to search in the resulting plaintext. Have this is_good_key() function return True if the sentinel word is found within the decrypted plaintext and False otherwise.

Use these functions to decrypt a file I have provided, test04_ciphertext.txt, and print it to the screen.

In [45]:
# Provide your implementations here

def brute_force_decrypt(ciphertext):
    
    # Try all possible rotation keys, decrypting the ciphertext 
    #  with each one, and calling is_good_key() on each one
    #  to determine if it's a reasonable key
    possibleKeys = []
    for i in range(26):
        candidatePlain = decrypt_rotation(i, ciphertext)
        
        if ( is_good_key(i, candidatePlain, "in")):
            possibleKeys.append(i)
    
    return possibleKeys

def is_good_key(keyValue, plaintext, sentinel):
    
    # Check to see if your sentinel word exists in the plaintext string
    return sentinel in plaintext
In [46]:
# Read in the ENTIRE file
# Open the file
with open("test04_ciphertext.txt", "r") as inFile:
    fileText = inFile.read().lower().strip()

    # Call brute_force_decrypt(ciphertext) and 
    #  print out possible rotation keys
    possibleKeys = brute_force_decrypt(fileText)
    print("Number of possible keys:", len(possibleKeys))
    for pk in possibleKeys:
        print("Possible Key:", pk)
        print(decrypt_rotation(pk, ciphertext=fileText))
Number of possible keys: 2
Possible Key: 18
email me your favorite, most hilarious meme.

include inst326 memetics in the subject.
Possible Key: 23
zhvdg hz tjpm avqjmdoz, hjno cdgvmdjpn hzhz.

dixgpyz dino326 hzhzodxn di ocz npwezxo.

Extra Credit

Rotation ciphers are clearly weak forms of encryption and are easily broken even without a modern computer.

For extra credit, implement a Vigenere Cipher and try to crack it using the frequency analysis and brute force methods described above.

In Vigenere ciphers, the key corresponds to a word that encodes several rotation ciphers.

In [ ]:
# Provide your encryption and decryption implementations here

# Encryption function
def encrypt_vigenere(keyValue, plaintext):
    """Encrypt the plaintext using a Vigenere cipher and keyValue key"""
    ciphertext = plaintext
    return ciphertext

# Decryption function
def decrypt_vigenere(keyValue, ciphertext):
    """Decrypt the ciphertext using a Vigenere cipher and keyValue key"""
    plaintext = ciphertext
    return plaintext