Simplified DES encryption
If you're using constants that are collections you'd be better off making them tuples, not lists. Trying to modify a tuple will raise an error as they're immutable, and using the tuple syntax makes it extra clear that these are unchanging constants.

FIXED_IP = (2, 6, 3, 1, 4, 8, 5, 7)
FIXED_EP = (4, 1, 2, 3, 2, 3, 4, 1)


As Caridorc said, using str.join is faster (depending on your version). It would also allow you to make permutate just one line.

def permutate(original, fixed_key):
    return ''.join(original[i - 1] for i in fixed_key)


It would also be a bit faster to pre-convert all your values in bits and key to integers. You can use map to apply a function to every member of a list, and it's faster than doing it in a list. You could do this when creating the zip object.

def xor(bits, key):
    new = ''
    for bit, key_bit in zip(map(int, bits), map(int, key)):
        new += str(((bit + key_bit) % 2))
    return new


Of course if you wanted this could also be made into a str.join, albeit a long one:

def xor(bits, key):
    return ''.join(str(((bit + key_bit) % 2)) for bit, key_bit in
                   zip(map(int, bits), map(int, key)))


There's a lot of functions here but not a lot of documentation. Explaining what individual functions do would make your code a lot easier to read. And I suspect you have some unnecessary duplicate functions, where you could pass a parameter instead of defining a whole new one. But it's hard to know when I don't entirely understand the functions you have here.