#@# Breaking classical ciphers
#@# ==========================

#@# Note: you will need to copy your solutions here from the previous class
#@# (at least the decryptions, at least up to the Vigenère cipher) --
#@# or alternatively: load() the previous class' Sage file before this one.


#@# ---------------------------------------------------------------------------
#@# Exercise 1: shift cipher - common words
#@# [with solution]
#@#
#@# In the previous class (exercise 2), you were asked to break the shift
#@# cipher by brute-force attack, and then manually select which plaintext was
#@# meaningful. Now we automate this process. Decide "meaninfulness" in a very
#@# simple way: does it contain the common English word "THE"? Break the
#@# following ciphertext this way, printing only the "meaningful" text.
c1 = "KGEWHWGHDWLZAFCLZSLLZWKZAXLUAHZWJAKKWUMJW" #@#

def shift_break_by_the (c):
    for k in range(1, 26):
        m = shift_dec(c, k)  # from previous class
        for i in range(len(m)-2):
            if m[i] == "T" and m[i+1] == "H" and m[i+2] == "E":
                return m
#print(shift_break_by_the(c1))

#@# (Note: this method works in the above case, but in general, there is no
#@# guarantee that "THE" is in the text, or that it doesn't accidentally occur
#@# in invalid texts too. A better method would be to use a dictionary of the
#@# most common English words, and find which plaintext has the most of them.)


#@# ---------------------------------------------------------------------------
#@# Exercise 2: shift cipher - statistics
#@# [with partial solution]
#@#
#@# Here we use a more sophisticated method for checking "meaningfulness".
#@# We use the fact that in human languages, not all letters occur with the
#@# same frequency. For example, in English, the most common letter is 'E',
#@# with around 12.7% frequency (whereas if each letter were equally likely,
#@# it would be 1/26 ≈ 3.8%). The following list contains the average letter
#@# frequencies in English text (index 0 is for A, index 1 is for B, ...):
english_stats = [ #@#
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702,         #@# A,B,C,D,E
    0.02228, 0.02015, 0.06094, 0.06966, 0.00153,         #@# F,G,H,I,J
    0.00772, 0.04025, 0.02406, 0.06749, 0.07507,         #@# K,L,M,N,O
    0.01929, 0.00095, 0.05987, 0.06327, 0.09056,         #@# P,Q,R,S,T
    0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074 #@# U,V,W,X,Y,Z
] #@#
#@# Source: https://mathcenter.oxford.emory.edu/site/math125/englishLetterFreqs/

#@# a) Calculate the letter frequencies of the given text (uppercase letters),
#@# e.g. "ABACUS" -> [2,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0].
def calc_stats (m):
    stats = [0]*26
    for i in range(len(m)):
        x = let2ind(m[i])
        stats[x] += 1
    return stats

#@# b) Measure "how English" a text is, by comparing its letter statistics
#@# (calculated above) to the English letter statistics (listed above).
#@# More specifically, calculate the dot product (= scalar product) of the two
#@# frequency lists. (Note: the dot product measures "how closely aligned" two
#@# vectors are, in this case in the 26-dimensional vector space. It is the
#@# biggest when the vectors align exactly, and 0 when they are orthogonal.)
def englishness (m):
    stats = calc_stats(m)
    score = 0
    for i in range(26):
        score += english_stats[i] * stats[i]
    return score

#@# c) Break the shift cipher by using the above "Englishness" measure,
#@# i.e. do a brute-force search, and pick the plaintext with the highest
#@# "Englishness" score.
def shift_break_by_stats (c):
    pass #TODO

c2 = "ETADFFQJF" #@#
#print(shift_break_by_stats(c1)) # from exercise 1
#print(shift_break_by_stats(c2))

#@# Note: this method works on surprisingly short texts.


#@# ---------------------------------------------------------------------------
#@# Exercise 3: Vigenère cipher - known key length
#@#
#@# The above statistical method can be adapted to the Vigenère cipher too.
#@# Assume that we somehow know the length of the key (in practice we don't,
#@# but that's for another exercise). For example, if the key is k = "BED"
#@# (of length t = 3), then m = "PLAINTEXT" is encrypted as:
#@#    m:  PLAINTEXT
#@#    k*: BEDBEDBED
#@#    c:  QPDJRWFBW
#@# Notice that every third letter is shifted by the same amount, so we can
#@# group the letters into t=3 groups:
#@#    c0: QJF  (positions 0, 3, 6 in c, which were shifted by +1 for B)
#@#    c1: PRB  (positions 1, 4, 7 in c, which were shifted by +4 for E)
#@#    c2: DWW  (positions 2, 5, 8 in c, which were shifted by +3 for D)
#@# Then we can use the statistical method from the previous exercise,
#@# but individually for each group (QJF -> PIE, PRB -> LNX, DWW -> ATT),
#@# and then reassemble the plaintext from these parts.
#@# Break the ciphertext given below (c3) using this method, knowing that
#@# it was encrypted by the Vigenère cipher using a key of length t = 3.
c3 = "MPYCWGMEJMMNRIPCGYXFCLVMUILOBRBIKOPWOEQSPW" #@#

def vigenere_break_with_keylen (c, t):
    pass #TODO
#print(vigenere_break_with_keylen(c3, 3))

#@# (Note: the longer the ciphertext is, the more likely this method works.
#@# For example, m="PLAINTEXT" was too short, it was used only to illustrate
#@# the method. But even for longer texts, it might happen that not all shifts
#@# can be recovered correctly, in which case we need to manually adjust them
#@# at the end, based on interpreting the successfully recovered parts.)


#@# ---------------------------------------------------------------------------
#@# Forms of attacks (what powers the attacker has):
#@# 1. Ciphertext-only attack (COA):
#@#    the attacker knows only c, and tries to get m=Dec(c)
#@#    (this is what we have seen so far - also known as eavesdropping).
#@# 2. Known-plaintext attack (KPA):
#@#    the attacker knows some (m,c) pairs (where c=Enc(m)),
#@#    and tries to break another c'.
#@# 3. Chosen-plaintext attack (CPA):
#@#    the attacker can choose some m and obtain c=Enc(m),
#@#    and tries to break another c'.
#@# 4. Chosen-ciphertext attack (CCA):
#@#    the attacker can choose some c and obtain m=Dec(c),
#@#    and tries to break another c'.
#@#


#@# ---------------------------------------------------------------------------
#@# Exercise 4: Vigenère cipher - KPA
#@#
#@# Break the Vigenère cipher using a known-plaintext attack as follows.
#@# Assume that we learnt the following plaintext and ciphertext pair,
#@# encrypted by the Vigenère cipher (using an unknown key):
mx = "SOMEKNOWNPLAINTEXT" #@#
cx = "DCZKURMHBCRKMLESKZ" #@#
#@# Break the following ciphertext, which was encrypted using the same key.
c4 = "GSEELVMVSA" #@#
#@# Hint: first recover the key from mx and cx ("undoing" the repetition),
#@# and then simply use that key to decrypt the new ciphertext (c4).
#@# Note: for simplicity, you can assume that the key has no repeating letters.

def vigenere_find_key (m, c):
    pass #TODO
#k = vigenere_find_key(mx, cx)
#print("key:", k)
#print(vigenere_dec(c4, k))

#@# Note: notice how long the key was, compared to how short the texts were.
#@# These texts could not have been broken using a ciphertext-only attack,
#@# but it was (hopefully) very easy using a known-plaintext attack. This shows
#@# how insecure classical ciphers are against these stronger forms of attacks.


#@# ---------------------------------------------------------------------------
#@# Exercise 5: mono-alphabetic substitution - KPA
#@#
#@# Break the mono-alphabetic substitution cipher (last class, exercise 3)
#@# using a known-plaintext attack. We obtained the following pair:
mm = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG" #@#
cc = "OHZSMLGUEYAJFXATPMINRADZYOHZCKQVWAB" #@#
#@# Break the following ciphertext, which was encrypted using the same key:
c5 = "LXZZCLFRZGMYZ" #@#

#TODO

#@# (Note: to make it easier, the above mm contains every English letter.
#@# If it didn't, you would need to "fill in" the rest of the permutation
#@# manually, by trying to make sense of the successfully recovered parts.)


#@# ---------------------------------------------------------------------------
#@# Exercise 6: Vigenère cipher - Kasiski's method
#@#
#@# Going back to ciphertext-only attack, in exercise 3, we assumed that the
#@# key length is known, which is rarely true in practice. Now let's see how to
#@# recover the key length. In long texts, common words such as "THE" and "AND"
#@# will occur frequently. For example (from Katz & Lindell's book): 
#@#    m:  THEMANANDTHEWOMANRETRIEVEDTHELETTERFROMTHEPOSTOFFICE
#@#    k*: BEADSBEADSBEADSBEADSBEADSBEADSBEADSBEADSBEADSBEADSBE
#@#    c:  ULEPSOENGLIIWREBRRHLSMEYWEXHHDFXTHJGVOPLIIPRKUSFIADI
#@# The plaintext contains "THE" 4 times, mostly encrypted in different ways.
#@# However, two of them became "LII", because both happened to be aligned with
#@# the keys in exactly the same way. This happens when their distance (30) is
#@# a multiple of the key length (5). So by finding a repetition such as "LII"
#@# in the ciphertext, and measuring their distance (30), we know that the key
#@# length must be a divisor of that. But which divisor? We can solve that by
#@# finding more repetitions, and taking their greatest common divisor (gcd).

#@# a) Find all pairs of three-letter repetitions in the given text,
#@# and return their positions as list of pairs. For example:
#@#    "ABAXYZABABACXYZ" -> [(0,6), (0,8), (3,12), (6,8)]
def find_all_repeats (m):
    pass #TODO
#print(find_all_repeats("ABAXYZABABACXYZ"))

#@# b) Break the following ciphertext as follows:
#@#    1. Find all repeations by the above function.
#@#    2. Guess the key length by taking the gcd of all repeating distances,
#@#       e.g. [(1,9), (5,17), (21,41)] -> gcd(8, 12, 20) = 4.
#@#    3. Use exercise 3 to recover the plaintext using this key length.
c6 =  "CCJWNORLQXKEEHTTVZDKPWPTXCEBTJWRJXGFZECBVPYCWTZEWM" #@#
c6 += "UKFTRCICTGFFUTWYZRWKGRQDGCEBRHPJAXXPTCPGFJFDNNUYRM" #@#
c6 += "VFUPKFJMCXCEMIAGIGCTUGGGBVFDQKQKFTKJFMS" #@#

#TODO

#@# (Note: in real life - not in the above example -, repetitions could also
#@# occur accidentally, ruining the above method. To counter this, we would
#@# need to find some subset of the differences that gives the "best" gcd.)


#@# ---------------------------------------------------------------------------
#@# Exercise 7: mono-alphabetic substitution - COA
#@#
#@# Break the following ciphertext using a ciphertext-only attack, if we know
#@# that it was encrypted by a mono-alphabetic substitution cipher:
c7 =  "JGRMQOYGHMVBJWRWQFPWHGFFDQGFPFZRKBEEBJIZQQOCIBZKLFAFGQVFZFWWE" #@#
c7 += "OGWOPFGFHWOLPHLRLOLFDMFGQWBLWBWQOLKFWBYLBLYLFSFLJGRMQBOLWJVFP" #@#
c7 += "FWQVHQWFFPQOQVFPQOCFPOGFWFJIGFQVHLHLROQVFGWJVFPFOLFHGQVQVFILE" #@#
c7 += "OGQILHQFQGIQVVOSFAFGBWQVHQWIJVWJVFPFWHGFIWIHZZRQGBABHZQOCGFHX" #@#
#@# (Source: Katz & Lindell's book)
#@# This is a manual process that involves examining the letter frequencies
#@# (see exercise 2), finding common words, and some iterative guesswork.
#@# For clarity, let's write the plaintext letters in lowercase (a, b, ...),
#@# while keeping the ciphertext letters uppercase (A, B, ...). In each step,
#@# a ciphertext letter is replaced with the guessed plaintext letter, e.g.:
#@#    c = c.replace("F", "e")
#@#
#@# Hints for the guesses:
#@# 1. The most frequent letter in the ciphertext is "F" (see calc_stats() in
#@#    exercise 2), so assume that it is "e", the most common English letter.
#@# 2. Find the second most frequent letter in the ciphertext, and assume that
#@#    it corresponds to the second most frequent English letter.
#@# 3. Having guessed "e" and "t", we can search for "the", a very common
#@#    English word. Look for "t*e" in the ciphertext, and find which letter
#@#    is at "*" the most, and assume that it stands for "h".
#@# 4. Now we can look for other occurances of "th". Having done everything
#@#    correctly so far, we can find multiple "thHt". What can "H" mean?
#@# 5. Now we can find the snippet "eaGththe", which suggests that there is
#@#    a word boundary at "eaGth|the". What does this suggest for "G"?
#@# 6. A bit later is "atetrIthh", suggesting "ate|trIth|h". What is "I"?
#@# 7. And so on, we can find longer and longer meaningful fragments, and guess
#@#    more and more letters until we recover the whole plaintext.
#@#
#@# More information: https://en.wikipedia.org/wiki/Frequency_analysis