Project Euler Problem 59

crack.py

#!/usr/bin/env python3

# ./crack.py p059_cipher.txt diameter
# https://projecteuler.net/problem=59

import sys

def testkey(thekey):
    # crude printable ascii
    return all(c in range(96,123) and c==thekey[n%3] for n,c in enumerate(thekey))

def dothexor(thing, otherthing):
    out = []
    for n in range(len(thing)):
        out.append(thing[n]^otherthing[n])
    return out

def decwithkey(thing, key):
    return bytes([a^key[n%3] for n,a in enumerate(thing)])

fn, kw = sys.argv[1:]

with open(fn) as f:
    ciphertext = [int(a) for a in f.read().split(",")]

kw = sorted([a.encode("ascii") for a in kw.split(",")],key=lambda x: -len(x))

maincrib = kw[0]
maincrib_len = len(maincrib)

end_bound = len(ciphertext)-3
cursor = 0

while cursor < end_bound:
    maybefullkey = dothexor(ciphertext[cursor:cursor+maincrib_len], maincrib)
    maybekey = maybefullkey[:3]

    if testkey(maybefullkey):
        keypos = cursor%3

        if keypos==1:
            maybekey = maybekey[2:] + maybekey[:2]
        if keypos==2:
            maybekey = maybekey[1:] + maybekey[:1]

        plaintext = decwithkey(ciphertext, maybekey)
        if not all(a in plaintext for a in kw):
            cursor += 1
            continue
        plaintext = plaintext.decode("ascii")

        print("key is", bytes(maybekey).decode("ascii"))
        print("-----------------------")
        print(plaintext)
        exit()

    cursor+=1

print("No match, oh dear")
exit(1)