PyCrypto Solution

solve.py

#!/usr/bin/env python

frequencies = {'a': 0.0651738, 'b': 0.0124248, 'c': 0.0217339, 'd': 0.0349835, 'e': 0.1041442, 'f': 0.0197881, 'g': 0.0158610, 'h': 0.0492888, 'i': 0.0558094, 'j': 0.0009033, 'k': 0.0050529, 'l': 0.0331490, 'm': 0.0202124,
               'n': 0.0564513, 'o': 0.0596302, 'p': 0.0137645, 'q': 0.0008606, 'r': 0.0497563, 's': 0.0515760, 't': 0.0729357, 'u': 0.0225134, 'v': 0.0082903, 'w': 0.0171272, 'x': 0.0013692, 'y': 0.0145984, 'z': 0.0007836, ' ': 0.1918182}


def single_byte_xor(b, s):
    """ Performs XOR of the single byte against every character in string. """
    assert len(b) == 1
    x = ord(b)
    result = ""
    for char in s:
        result += chr(x ^ ord(char))
    return result


def decode_single_byte_xor(message):
    """ Decodes a string that has been encoded using single-byte XOR, using frequency analysis. """
    mk, byte = 0, ""
    for i in range(256):
        m = single_byte_xor(chr(i), message)
        k = sum(frequencies.get(c, 0) for c in m)
        if k > mk:
            mk, byte = k, chr(i)
    return byte, mk


def repeating_key_xor(key, message):
    """ Encrypts the message with the key using repeating-key XOR. """
    result = ""
    for i, c in enumerate(message):
        result += chr(ord(key[i % len(key)]) ^ ord(c))
    return result


def hamming_distance(str1, str2):
    assert len(str1) == len(str2)
    n = len(str1)
    d = 0
    num1 = int(str1.encode("hex"), 16)
    num2 = int(str2.encode("hex"), 16)
    for i in range(n * 8):
        d += (num1 & 1) ^ (num2 & 1)
        num1 >>= 1
        num2 >>= 1
    return d


def break_repeating_key_xor(message):
    """ Decrypts a string that is encrypted with repeating-key XOR, by guessing the key size. """
    potential = []
    for n in range(2, 41):
        if len(message) < 4 * n:
            break
        d = 0.0
        for i in range(3):
            d += hamming_distance(message[i * n:(i + 1) * n],
                                  message[(i + 1) * n: (i + 2) * n])
        d /= 3 * n
        potential.append((n, d))
    potential.sort(key=lambda p: p[1])
    fm, decoded = 0, ""
    for keysize, _ in potential[:min(len(potential), 5)]:
        chunks = zip(*[iter(message)] * keysize)
        fs = 0
        key = ""
        for i in range(keysize):
            s = "".join(c[i] for c in chunks)
            c, f = decode_single_byte_xor(s)
            key += c
            fs += f
        if fs > fm:
            fm, decoded = fs, repeating_key_xor(key, message)
    return decoded

with open("flag.enc", "rb") as f:
    data = f.read()
    print break_repeating_key_xor(data)