# Seth Jones
# Code to help break CIS 3362 Homework #3 Question #4
# This tries potential keys and looks for common 5 and 6 letter words.

from math import gcd

x = "kcppxxtlafgktqiqhhgistvgmxfmkknffomkpkhjcgpjsuitqzgykohrwtvjxomjgtwgvrfagkolfrtqitqvgkofajtxxurkykoyompeeecblfrlplwurywqywiekjctb"
lookingfor = "the"
MAX_RARE = 3 

# load the common words into a set
words = set()
for line in open("words.txt"):
    words.add(line.strip())

#3x3 Determinant
def det3(m):
    return (m[0][0] * (m[1][1]*m[2][2] - m[1][2]*m[2][1])
          - m[0][1] * (m[1][0]*m[2][2] - m[1][2]*m[2][0])
          + m[0][2] * (m[1][0]*m[2][1] - m[1][1]*m[2][0])) % 26

def parity(r):
    # even/odd pattern of a row
    return [v % 2 for v in r]

def decrypt_row(row):
    # one matrix row decrypts one letter from every block
    out = ""
    for block in blocks:
        c = [ord(ch) - ord('a') for ch in block]
        out += chr((row[0]*c[0] + row[1]*c[1] + row[2]*c[2]) % 26 + ord('a'))
    return out

def filter_rows(rows):
    # throw out rows that can't be part of the real key before building any matrices
    kept_rows, kept_text = [], []
    for r in rows:
        if parity(r) == [0, 0, 0]:
            continue
        text = decrypt_row(r)
        if sum(text.count(ch) for ch in "jqxz") > MAX_RARE:
            continue   # too many rare letters to be English
        kept_rows.append(r)
        kept_text.append(text)
    return kept_rows, kept_text

def find_words(plain):
    # check every 5 and 6 letter piece of the plaintext against the word set
    found = []
    for size in (5, 6):
        for k in range(len(plain) - size + 1):
            if plain[k:k+size] in words:
                found.append(plain[k:k+size])
    return found

# split the ciphertext into 3 letter blocks

blocks = [x[i:i+3] for i in range(0, len(x), 3)]

# for each block, find the matrix rows that turn it into "THE"

target = [ord(ch) - ord('a') for ch in lookingfor]   # [19, 7, 4]

block_matches = []
for block in blocks:
    c = [ord(ch) - ord('a') for ch in block]
    rows = []
    for t in target:
        row_vals = []
        for a in range(26):
            for b in range(26):
                for d in range(26):
                    if (a*c[0] + b*c[1] + d*c[2]) % 26 == t:
                        row_vals.append([a, b, d])
        rows.append(row_vals)
    block_matches.append(rows)

#try every matrix, decrypt, and keep plaintexts with "the" and common words

matches = [] 
for i, rows in enumerate(block_matches):
    t_rows, t_text = filter_rows(rows[0])
    h_rows, h_text = filter_rows(rows[1])
    e_rows, e_text = filter_rows(rows[2])
    for a in range(len(t_rows)):
        for b in range(len(h_rows)):
            if parity(t_rows[a]) == parity(h_rows[b]):
                continue
            for d in range(len(e_rows)):
                m = [t_rows[a], h_rows[b], e_rows[d]]
                if gcd(det3(m), 26) != 1:
                    continue   # not invertible, can't be a Hill key
                # put the three rows' letters back in order to get one plaintext string
                plain = "".join(x + y + z for x, y, z in zip(t_text[a], h_text[b], e_text[d]))
                if plain.count("the") < 2:
                    continue   # need at least two "the"s before checking for words
                found = find_words(plain)
                if found:
                    matches.append((len(found), blocks[i], m, found, plain))

#sort by most words found and write to the file

matches.sort(key=lambda r: r[0], reverse=True)

results = open("hardhill_results.txt", "w")
for count, block, m, found, plain in matches:
    print(count, block, m, found, plain, file=results)
results.close()
