The assignments below comprise your third homework assignment. Provide the implementations requested.
You will be graded on the following rubric:
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
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.
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.
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.
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.
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.
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.
# 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.
# 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)
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.
# Open the file
with open("test01b_caesar_shift_ciphertext.txt", "r") as inFile:
for line in inFile:
print(decrypt_caesar(line.lower().strip()))
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.
# 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
# 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)
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.
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)]
# 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])
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.
# 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))
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.
# 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
# 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))
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.
# 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