Lab 7 : Let’s be clever and crack the ciphers¶
0 Preliminaries¶
To run doctests, add the following to the bottom of your file:
if (__name__ == '__main__'):
import doctest
doctest.testmod(optionflags= doctest.NORMALIZE_WHITESPACE)
1 Introduction¶
We are going to learn how to crack the additive cipher and the affine cipher during this lab. The trick is to do frequency analysis. Since both additive cipher and affine cipher are monoaphabetic substitution ciphers, we know that all the letter E’s are encrypted into same letters. So do the letter T’s. The frequencies of these two letters in English are the largest (and also the most distinct) ones. The encryption for E should be the most frequent letter in the ciphertext. That for T should be the second frequent letter in the ciphertext. After we determine the ciphertext for E and T, cracking these ciphers are relatively straight forward.
2 Convert between the alphabet and \(\mathbb{Z}_{26}\)¶
We have seen how to do this. Feel free to copy your code.
Exercise 1 Write functions that can convert between strings and lists of numbers.
def text_to_nums(m):
"""
>>> text_to_nums('MEETMEATTHEUSUALPLACE')
[12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4]
"""
def nums_to_text(l):
"""
>>> nums_to_text([12, 4, 4, 19, 12, 4, 0, 19, 19, 7, 4, 20, 18, 20, 0, 11, 15, 11, 0, 2, 4])
'MEETMEATTHEUSUALPLACE'
"""
2 Additive cipher¶
We have seen how to do this. Feel free to copy your code.
Exercise 2 Write the additive cipher and decipher functions.
def add_enc(text, key):
"""
>>> add_enc('KNOWLEDGEISPOWERFRANCEISBACON',3)
'NQRZOHGJHLVSRZHUIUDQFHLVEDFRQ'
"""
def add_dec(text, key):
"""
>>> add_dec('NQRZOHGJHLVSRZHUIUDQFHLVEDFRQ',3)
'KNOWLEDGEISPOWERFRANCEISBACON'
"""
3 Frequency analysis¶
Now we are going to do some statistics. We will calculate how many times has each letter occurred in the ciphertext. Then we can figure out which letter is the encryption for plaintext E.
Exercise 3 Write a function which takes a list L and an index n and then increases the \(n^{th}\) item in L by one.
def add_count(L, n):
"""
>>> add_count([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25], 3)
[0, 1, 2, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
"""
Exercise 4 Write a function to count the occurrence of each letter in the given text. Use text_to_nums.
def get_frequency(text):
"""
>>> get_frequency('KNOWLEDGEISPOWERFRANCEISBACON')
[2, 1, 2, 1, 4, 1, 1, 0, 2, 0, 1, 1, 0, 3, 3, 1, 0, 2, 2, 0, 0, 0, 2, 0, 0, 0]
>>> get_frequency('NQRZOHGJHLVSRZHUIUDQFHLVEDFRQ')
[0, 0, 0, 2, 1, 2, 1, 4, 1, 1, 0, 2, 0, 1, 1, 0, 3, 3, 1, 0, 2, 2, 0, 0, 0, 2]
"""
4 Crack the additive cipher¶
Now we are going to crack the additive cipher. The trick is relatively straightforward. We can determine the key with some simple arithmetic from the encryption of letter ‘E’ which is the most frequent letter in the ciphertext.
Exercise 5 Write a function to determine the index of the largest number in a list.
def get_largest_index(l):
"""
>>> get_largest_index([0, 0, 0, 2, 1, 2, 1, 4, 1, 1, 0, 2, 0, 1, 1, 0, 3, 3, 1, 0, 2, 2, 0, 0, 0, 2])
7
"""
Exercise 6 Write a function to determine the most probable key given the ciphertext from an additive cipher.
>>> get_frequency('NQRZOHGJHLVSRZHUIUDQFHLVEDFRQ')
[0, 0, 0, 2, 1, 2, 1, 4, 1, 1, 0, 2, 0, 1, 1, 0, 3, 3, 1, 0, 2, 2, 0, 0, 0, 2]
>>> get_largest_index([0, 0, 0, 2, 1, 2, 1, 4, 1, 1, 0, 2, 0, 1, 1, 0, 3, 3, 1, 0, 2, 2, 0, 0, 0, 2])
7
>>> 7-4
3
def crack_additive(text):
"""
>>> crack_additive('NQRZOHGJHLVSRZHUIUDQFHLVEDFRQ')
3
"""
5 Affine cipher¶
The affine cipher is a combination of additive cipher and multiplicative cipher. It uses its additive key to encrypt the plaintext first with an additive cipher and gets an intermediate result. Then it uses its multiplicative key to encrypt the intermediate result with multiplicative cipher. The output of the multiplicative cipher will be the final result.
Here is a working (but not efficient) function to compute the multiplicative inverse. Feel free to use it.
def mul_inv(n):
for i in range(1, 26):
if (i*n%26==1):
return i
Exercise 7 Write the multiplicative cipher and decipher functions. Use mul_inv.
def mul_enc(text, key):
"""
>>> mul_enc('KNOWLEDGEISPOWERFRANCEISBACON',3)
'ENQOHMJSMYCTQOMZPZANGMYCDAGQN'
"""
def mul_dec(text, key):
"""
>>> mul_dec('ENQOHMJSMYCTQOMZPZANGMYCDAGQN',3)
'KNOWLEDGEISPOWERFRANCEISBACON'
"""
Exercise 8 Write the affine cipher and decipher functions. Use the additive cipher/decipher and multiplicative cipher/decipher.
>>> add_enc('KNOWLEDGEISPOWERFRANCEISBACON', 4)
'ORSAPIHKIMWTSAIVJVERGIMWFEGSR'
>>> mul_enc('ORSAPIHKIMWTSAIVJVERGIMWFEGSR',3)
'QZCATYVEYKOFCAYLBLMZSYKOPMSCZ'
def affine_enc(text, s, r):
"""
>>> affine_enc('KNOWLEDGEISPOWERFRANCEISBACON', 3, 4)
'QZCATYVEYKOFCAYLBLMZSYKOPMSCZ'
>>> affine_enc('ET', 3, 4)
'YR'
"""
def affine_dec(text, s, r):
"""
>>> affine_dec('QZCATYVEYKOFCAYL', 3, 4)
'KNOWLEDGEISPOWER'
"""
Challenge 1: Crack the following ciphertext
GURRKPYNZNGVBARHERXNVFNGGEVOHGRQGBGURNAPVRAGTERRXFPUBYNENEPUVZRQRFURERCBEGRQYLCEBPYNVZRQRHERXNRHERXNNSGREURUNQFGRCCRQVAGBNONGUNAQABGVPRQGUNGGURJNGREYRIRYEBFRJURERHCBAURFHQQRAYLHAQREFGBBQGUNGGURIBYHZRBSJNGREQVFCYNPRQZHFGORRDHNYGBGURIBYHZRBSGURCNEGBSUVFOBQLURUNQFHOZRETRQGUVFERYNGVBAVFABGJUNGVFXABJANFNEPUVZRQRFCEVAPVCYRGUNGQRNYFJVGUGURHCGUEHFGRKCREVRAPRQOLNOBQLVZZREFRQVANSYHVQURGURAERNYVMRQGUNGGURIBYHZRBSVEERTHYNEBOWRPGFPBHYQORZRNFHERQJVGUCERPVFVBANCERIVBHFYLVAGENPGNOYRCEBOYRZURVFFNVQGBUNIRORRAFBRNTREGBFUNERUVFQVFPBIRELGUNGURYRNCGBHGBSUVFONGUGHONAQENAANXRQGUEBHTUGURFGERRGFBSFLENPHFR
6 Crack the affine cipher¶
Now we will move on to crack the affine cipher. The trick is similar. We need to solve two equations to determine the key pair (s, r):
\(s*(4+r) \equiv x \pmod{26}\)
\(s*(19+r) \equiv y \pmod{26}\)
where \(x\) and \(y\) are the corresponding number of the most frequent letter and the second most frequent letter in the ciphertext.
Exercise 9 Write a function to determine the index of the second largest number in a list.
def get_second_largest_index(list):
"""
>>> get_second_largest_index([2, 1, 2, 1, 5, 1, 1, 0, 2, 0, 1, 1, 0, 4, 3, 1, 0, 2, 2, 0, 0, 0, 2, 0, 0, 0])
13
"""
Exercise 10 Write a function to solve the equations mentioned above. Use mul_inv.
def solve(x, y):
"""
>>> solve(24, 17)
[3, 4]
"""
Exercise 11 Write a function to determine the most probable key given the ciphertext from an affine cipher.
>>> get_frequency('YXYLGRKWYSMRYMRO')
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 0, 1, 0, 0, 3, 1, 0, 0, 0, 1, 1, 4, 0]
>>> get_largest_index([0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 0, 1, 0, 0, 3, 1, 0, 0, 0, 1, 1, 4, 0])
24
>>> get_second_largest_index([0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 0, 1, 0, 0, 3, 1, 0, 0, 0, 1, 1, 4, 0])
17
>>> solve(24, 17)
[3, 4]
def crack_affine(text):
"""
>>> crack_affine('YXYLGRKWYSMRYMRO')
[3, 4]
"""
Challenge 2: Crack the following ciphertext
YQBDUVJDBEZKVYVRHKTYODRYDOBTZGKHYBPVWWKBHLBTVYHKXQHIBKBWTZPBYZYQBZOVCBYQHYVYTDUDTDHKTZRVHKRKVPHYBHKKZNBWYQBBPBOLBURBZGHOHOBRDKYDOHKBGGKZOBTRBURBVYHKXWVWUZYBSVTYHTHEZKVYVRHKBUYVYXVUYQBBHOKXPZWBOUEBOVZWVUTYBHWVYNHTWVIVWBWVUYZTPHKKBORVYXTYHYBTHUWYBOOVYZOVBTYQBFVULWZPZGUHEKBTRZUYOZKKBWYQBTZDYQYQBOBEDMKVRZGGKZOBURBHUWYQBEHEHKTYHYBTHYYQBRBUYBOYQBPVKHUBTBHUWYQBLBUZBTBYZYQBUZOYQHUWNBTYOBTEBRYVIBKXHUWYQBIBUBYVHUTYZYQBBHTYGVGYBBUYQRBUYDOXVYHKXNHTZUBZGYQBPZTYDOMHUVTBWHOBHTVUBDOZEBPHUXZGVYTRVYVBTTYZZWHPZULYQBODVUTZGHURVBUYOZPHUMDVKWVULTVYTBBPTKVFBKXYQHYYQBRKHTTVRHKUHYDOBZGYQBOBUHVTTHURBNHTKVUFBWYZVYTZOVLVUVUYQBOZPHUBPEVOBTQBHOYKHUWQVTYZOVHUHUWEZKVYVRHKEQVKZTZEQBOJDBUYVUTFVUUBOEZVUYTZDYYQHYZYYZZGGOBVTVULHLBOPHUMVTQZEIVTVYVULUZOYQVYHKXWDOVULYQBYNBKGYQRBUYDOXUZYVRBWHNVWBTEOBHWUBNGZOPZGEZKVYVRHKHUWTZRVHKZOLHUVCHYVZUZMTBOIVULYQHYVYHKXHEEBHOBWYZQHIBBSVYBWGOZPGBDWHKVTPTZYQHYVYTTZRVBYXNHTMHTBWZUPBORQHUYTHUWRZPPBORBKVUFBWYZYQVTNHTHUYVPZUHORQVRHKYQVUFVULOBEOBTBUYBWVUYQBGHPZDTBHOKXOBUHVTTHURBGOBTRZRXRKBHKKBLZOXZGLZZWHUWMHWLZIBOUPBUYVUTVBUHMXHPMOZLVZKZOBUCBYYVNQZTBTYOZULPBTTHLBVTHMZDYYQBIVOYDBTZGGHVOUBTTADTYVRBOBEDMKVRHUVTPHUWLZZWHWPVUVTYOHYVZUZKWVULMZYQRQDORQHUWBPEVOBHYMHXYQBTBRVYXOBEDMKVRTNBOBWBIZYBWYZUZYVZUTZGKVMBOYXFVUUBOOBEZOYTYQHYYQBOBNBOBPHUXWBGBURBTZGKVMBOYXTDRQHTYQBPHYYBZEHKPVBOVRBKBMOHYVZUZGGKZOBUYVUBLBUVDTUZYZUKXVUHOYTRDKEYDOBHUWHORQVYBRYDOBMDYYQBOBPHOFHMKBBGGKZOBTRBURBZGPZOHKTZRVHKHUWEZKVYVRHKEQVKZTZEQXYQHYZRRDOOBWVUGKZOBURBHYYQBTHPBYVPB