from Crypto.Util.number import *

revrule = {'0':[], '1':[]}
RULE = [86 >> i & 1 for i in range(8)]
N_BYTES = 32
N = 8 * N_BYTES

for bit in [0,1]:
    for i in range(len(RULE)):
        if RULE[i]==bit:
            revrule[str(bit)].append(bin(i)[2:].zfill(3)[::-1])

def next(x):
    x = (x & 1) << N+1 | x << 1 | x >> N-1
    y = 0
    for i in range(N):
        y |= RULE[(x >> i) & 7] << i
    return y

def xor(s1, s2):
    res = "".join(map(lambda x: chr(ord(x[0]) ^ ord(x[1])), zip(s1, s2)))
    return res

def str_to_int(str1):
    return int(str1[::-1].encode("hex"), 16)

def int_to_str(num):
    return hex(num)[2:].replace("L","").zfill(64).decode("hex")[::-1]

def invnext2(y):
    bin_str = bin(y)[2:].zfill(N)[::-1]
    valid = ['']
    for i in range(0, len(bin_str)):
        bit = bin_str[i]
        newvalid = []
        for v in valid:
            for subset in revrule[bit]:
                if i == 0:
                    newvalid.append(subset)
                elif i != 0 and v[-2:] == subset[:2]:
                    newvalid.append(v[:-2] + subset)
        valid = newvalid
    for v in valid:
        if v[:2] == v[-2:]:
            b1 = int(v[::-1], 2)
    return b1

ct = open("hint.gif.enc", "rb").read()
ct1 = open("rule86.txt","r").read()
ct2 = open("rule86.txt.enc","rb").read()
ct3 = open("super_cipher.py.enc","rb").read()
ct4 = open("test.gif","wb")

keystream = xor(ct1, ct2)
print xor(keystream, ct3)
sub_keystream = keystream[:32]
sub_keystream = str_to_int(sub_keystream)

for i in range(0, len(ct), 32):
    ct4.write(xor(ct[i:i+32], int_to_str(sub_keystream)))
    sub_keystream = next(sub_keystream)

y = str_to_int(keystream[:32])
for c in range(N//2):
    step = invnext2(y)
    x = (step >> 1) & 2**256-1
    y = x
print int_to_str(y)
