XOR and shift encryptor Solver using Matrix

calc.sage

M = Matrix(GF(2), 64 * 64)
for i in range(64 * 64):
    M[i, i] = 1
s0 = list(M[0:64])
s1 = list(M[64:128])

ZERO = [vector(GF(2), [0] * 64 * 64)]
def shift(v, delta):
    if delta > 0:
        return (ZERO * delta + v[0:-delta])
    else:
        delta *= -1
        return (v[delta:] + ZERO * delta)
# Shift a
shift_s1 = shift(s1, 3)
for i in range(64):
    s1[i] += shift_s1[i]

next_s1 = ZERO * 64
for i in range(64):
    next_s1[i] = s0[i] + s1[i] + shift(s1, -13)[i] + shift(s0, -37)[i]
orig_s = []
for i in range(64):
    orig_s.append(list(M[i * 64:i * 64 + 64]))
M[0:64] = next_s1
for i in range(2, 65):
    M[i*64 - 64:i*64] = orig_s[i % 64]

def to_buf(vec):
    ret = []
    for i in range(64):
        v = int(0)
        for j in range(64):
            if vec[i*64+j]:
                v |= int(1) << j
        ret.append(v)
    return ret

def get_rand(vec):
    b = to_buf(vec)
    return int(b[0] + b[1]) %2**64
    
initial_vec = [0] * 4096
for i in range(64):
    for j in range(64):
        initial_vec[i * 64 + j] = GF(2)(i >> j)
initial_vec = vector(GF(2), initial_vec)
assert 7239098760540678124 == (get_rand(M ** 10000 * initial_vec))

BUCKET = 8
Ms = []
for j in range(64 / BUCKET):
    ctmp = []
    cur = M ** 0
    cM = M ** ((2 ** BUCKET) ** j)
    for i in range(2 ** BUCKET):
        if i % 64 == 0: print(i)
        ctmp.append(cur)
        cur *= cM
    Ms.append(ctmp)
    print("{}/{}".format(j + 1, 64 / BUCKET))

def fast_powM(k):
    ret = M ** 0
    idx = 0
    while k > 0:
        ret *= Ms[idx][k % (2 ** BUCKET)]
        k >>= BUCKET
        idx += 1
    return ret

print(fast_powM(16) == M ** 16)
print(fast_powM(18446744073709551615) == M ** 18446744073709551615)

cur = M ** 31337
with open('enc.dat', 'rb') as f:
    enc = f.read()
flag = ''
for i in range(256):
    buf = get_rand(cur * initial_vec)
    cur *= M
    sh = i // 2
    if sh > 64:
        sh = 64
    mask = (1 << sh) - 1
    buf &= mask
    print(buf)
    cur *= fast_powM(buf)
    xx = get_rand(cur * initial_vec)
    cur *= M
    flag += chr((enc[i]) ^^ (xx & 255))
    print(flag)

output.txt

$ time sage calc.sage
...
Oh, you can read me, right? OK. I'll give you the flag.....FAKEFLAG{THIS_IS_FAKE_FLAG}...Sorry, sorry, just kidding...The true flag goes as follows...........TWCTF{1084cd93186a8ab4110c991a7980aae36d77f2_X0R5h1f7+_15_m0Re_c0mp1ex_th4n_y0u_thought_right?1!!}
sage calc.sage  282.71s user 1.45s system 100% cpu 4:43.93 total