Во-первых, перестать постоянно считать в цикле то, что должно быть посчитано вне цикла; во-вторых, не делать того, что делать не нужно:
1) int(bin_password[-8:] - кроме того, что это должно быть константами вне цикла, зачем слайс? Получайте bin_password не через bin, а через '{:08b}'.format(your_int_number).
2) Не проще ли просто последовательно читать из одного файла и писать в другой, а потом при необходмости удалить первый и переименовать второй?
3) Вместо циклического сдвига попробуйте collections.deque.rotate() - хотя с учётом п.1 это большой погоды не сделает.
4) Весь цикл 'for byte in block' поместите в list comprehension, и тогда append не нужен.
5) Вместо range используйте xrange, если Python 2.x
6) Используйте mmap
7) Разделить вычисления и I/O - вынести запись в файл в отдельный тред, пусть параллельно работают. Это классика.
Если файл небольшой лучше сразу весь в память считать. Если большой увеличь BLOCK_SIZE до нескольких мегабайт хотябы. А вообще конечно сначала выясни, что медленно работает - чтение, запись или преобразование.