Blowfish - симметричный блочный шифр

имеет ключ переменной длины, от 32 до 448 бит, что делает его удобным для внутреннего и экспортного использования (как мы помним, ограничения на «сильную криптографию» полностью не сняты ни в США, ни в России). Он достаточно быстр в основной своей части, поскольку использует простую базовую функцию, повторенную 16 раз (циклов), однако требует относительно длительной предварительной работы. С момента публикации он был достаточно обстоятельно проанализирован широкой криптографической общественностью и позиционируется как сильный алгоритм шифрования. Blowfish не запатентован и доступен для любого применения. Качество этого алгоритма доказывает выход в финал конкурса AES его клона Twofish.

Оригинальный текст Blowfish был представлен на первом симпозиуме "Быстрого программного кодирования" в Кембридже, Великобритания (слушания опубликованы в Springer-Verlag, примечания к лекциям в Computer Science #809, 1994) и в Апрельском выпуске 1994 года журнала Dr. Dobbs.

Blowfish предложен, как новый блочный шифр с секретным ключом. Это сеть Feistel, выполняющая шифрование простой функцией 16 раз. Размер блока -64 бита и ключ может от 32 до 448 битов. Хотя существует сложная фаза инициализации до начала шифрования (как раз и связанная с переменной длиной ключа), фактически, шифрование этим алгоритмом очень эффективно на высокопроизводительных процессорах (класса Pentium). Алгоритм включает в себя 2 части: часть расширения ключей и часть шифрования данных. Расширение ключа преобразует ключ, обычно 448-битный, в несколько суммированных массивов подключей размером 4168 байт.

Шифрование данных происходит через 16-итерационную сеть Feistel (см. иллюстрацию справа). Каждая итерация состоит из перестановки, зависящей и от ключа и от данных. Все операции - XOR и ADD приведены к 32-битным словам. Единственные дополнительные 4-битные операции используются при поиске в индексированных массивах.

Blowfish использует большое количество подключей. Эти ключи должны быть предварительно вычислены перед любым зашифрованием или расшифрованием.

1. P-массив включает 18 32-битных подключей:

P1, P2,..., P18

2. Имеются четыре 32-битных S-блока с 256 элементами каждый:

S1,0, S1,1,..., S1,255;

S2,0, S2,1,..,, S2,255;

S3,0, S3,1,..., S3,255;

S4,0, S4,1,..,, S4,255.

Метод, используемый для вычисления подключей, буден описан ниже.

Зашифрование:

Blowfish - сеть Feistel, которая включает 16 итераций. Вводим 64-битный элемент (блок) данных. Обзовем его - «Х». 64-битный блок разбивается на 32-битные слова, что совместимо с существующими алгоритмами и кратно или равно разрядности слов большинства процессоров. Можно легко увеличить размерность блока до 128-бит (применяется в Twofish - предыдущей версии алгоритма) или уменьшить размер блока (категорически не рекомендуется).

Делим X на две части по 32 бита: ХL, ХR

For i = 1 to 16:

ХL = ХL Е Pi

ХR = F(XL) Е ХR

Поменять местами (SWAP) ХL и ХR

(конец цикла)

Поменять местами ХL и ХR (Отменяя последнюю перестановку.)

ХR = ХR Е P17

ХL = ХL Е P18

Объединить ХL и ХR

Функция F (см. иллюстрацию):

Разделить ХL на четыре 8-битных части: a, b, c, и d

F(ХL) = ((S1,a + S2,b mod 232) Е S3,c) + S4,d mod 232

Расшифрование аналогично зашифрованию, за исключением, что P1, P2,..., P18 используются в обратном порядке.

Примечание Шнайера: При реализации Blowfish, если критична скорость приложения, то операции не должны организовываться в цикле. Это гарантирует присутствие всех подключей в КЭШе.

Генерация подключей:

Подключи вычисляются, путем использования алгоритма Blowfish. Данный метод состоит в следующем:

1. Сначала инициализируется P-массив и затем четыре S-блока, с фиксированной строкой. Эта строка состоит из шестнадцатеричных цифр представления числа