Описание Blowfish

Blowfish представляет собой 64-битовый блочный шифр с ключом переменной длины. Алгоритм состоит из двух частей: развертывание ключа и шифрование данных. Развертывание ключа преобразует ключ длиной до 448 битов в несколько массивов подключей, общим объемом 4168 байтов.

Шифрование данных состоит из простой функции, последовательно выполняемой 16 раз. Каждый этап состоит из зависимой от ключа перестановки и зависимой от ключа и данных подстановки. Используются только сложения и XOR 32-битовых слов. Единственными дополнительными операциями на каждом этапе являются четыре извлечения данных из индексированного массива.

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

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

P1, P2,..., P18

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

S_1,0, S_1,1,..., S_1,255

S_2,0, S_2,2,..., S_2,255

S_3,0, S_3,3,..., S_3,255

S_4,0, S_4,4,..., S_4,255

Точный метод, используемый при вычислении этих подключей описан в этом разделе ниже.

Рис. 14-2. Blowfish.

Blowfish является сетью Фейстела (Feistel) (см. раздел 14.10), состоящей из 16 этапов. На вход подается 64-битовый элемент данных x. Для шифрования:

Разбейте x на две 32-битовых половины: x_L, x_R

Для i = 1 по 16:

x_L = x_L Å P₁₈

x_R = F(x_L) Å x_R

Переставить x_L и x_R (кроме последнего этапа.)

x_R = x_R Å P₁₇

x_L = x_L Å P₁₈

Объединить x_L и x_R

Рис. 14-3. Функция F.

Функция F представляет собой следующее (см. Рис. 14-3):

Разделить x_L на четыре 8-битовых части: a, b, c и d
F(x_L) = ((S_1,a + S_2,b mod 2³²) Å S_3,c)+ S_4,d mod 2³²

Дешифрирование выполняется точно также, как и шифрование, но P₁, P₂,..., P₁₈ используются в обратном порядке.

В реализациях Blowfish, для которых требуется очень большая скорость, цикл должен быть развернут, а все ключи должны храниться в кэше. Подробности приведены в [568].

Подключи рассчитываются с помощью специального алгоритма. Вот какова точная последовательность действий.

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

(2) Выполняется XOR P₁ с первыми 32 битами ключа, XOR P₂ со вторыми 32 битами ключа, и так далее для всех битов ключа (до P₁₈). Используется циклически, пока для всего P-массива не будет выполнена операция XOR с битами ключа.

(3) Используя подключи, полученные на этапах (1) и (2), алгоритмом Blowfish шифруется строка из одних нулей.

(4) P₁ и P₂ заменяются результатом этапа (3).

(5) Результат этапа (3) шифруется с помощью алгоритма Blowfish и измененных подключей.

(6) P₃ и P₄ заменяются результатом этапа (5).

(7) Далее в ходе процесса все элементы P-массива и затем по порядку все четыре S-блока заменяются выходом постоянно меняющегося алгоритма Blowfish.

Всего для генерации всех необходимых подключей требуется 521 итерация. Приложения могут сохранять подключи - нет необходимости выполнять процесс их получения многократно.