Описание Blowfish
Blowfish представляет собой 64-битовый блочный шифр с ключом переменной длины. Алгоритм состоит из двух частей: развертывание ключа и шифрование данных. Развертывание ключа преобразует ключ длиной до 448 битов в несколько массивов подключей, общим объемом 4168 байтов.
Шифрование данных состоит из простой функции, последовательно выполняемой 16 раз. Каждый этап состоит из зависимой от ключа перестановки и зависимой от ключа и данных подстановки. Используются только сложения и XOR 32-битовых слов. Единственными дополнительными операциями на каждом этапе являются четыре извлечения данных из индексированного массива.
В Blowfish используется много подключей. Эти подключи должны быть рассчитаны до начала шифрования или дешифрирования данных.
P-массив состоит из 18 32-битовых подключей:
P1, P2, . . ., P18
Каждый из четырех 32-битовых S-блоков содержит 256 элементов:
S1,0, S1,1, . . ., S1,255
S2,0, S2,2, . . ., S2,255
S3,0, S3,3, . . ., S3,255
S4,0, S4,4, . . ., S4,255
Точный метод, используемый при вычислении этих подключей описан в этом разделе ниже.
Рис. 14-2. Blowfish.
Blowfish является сетью Фейстела (Feistel) (см. раздел 14.10), состоящей из 16 этапов. На вход подается 64-битовый элемент данных x. Для шифрования:
Разбейте x на две 32-битовых половины: xL, xR
Для i = 1 по 16:
xL = xL A P18
xR = F(xL) A xR
Переставить xL и xR (кроме последнего этапа.)
xR = xR A P17
xL = xL A P18
Объединить xL и xR
Рис. 14-3. Функция F.
Функция F представляет собой следующее (см. Рис. 14-3):
Разделить xL на четыре 8-битовых части: a, b, c и d
F(xL) = ((S1,a + S2,b mod 232) A S3,c)+ S4,d mod 232
Дешифрирование выполняется точно также, как и шифрование, но P1, P2, . . ., P18 используются в обратном порядке.
В реализациях Blowfish, для которых требуется очень большая скорость, цикл должен быть развернут, а все ключи должны храниться в кэше. Подробности приведены в [568].
Подключи рассчитываются с помощью специального алгоритма. Вот какова точная последовательность действий.
-
Сначала P-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатиричных цифр p.
-
Выполняется XOR P1 с первыми 32 битами ключа, XOR P2 со вторыми 32 битами ключа, и так далее для всех битов ключа (до P18). Используется циклически, пока для всего P-массива не будет выполнена операция XOR с битами ключа.
-
Используя подключи, полученные на этапах (1) и (2), алгоритмом Blowfish шифруется строка из одних нулей.
-
P1 и P2 заменяются результатом этапа (3).
-
Результат этапа (3) шифруется с помощью алгоритма Blowfish и измененных подключей.
-
P3 и P4 заменяются результатом этапа (5).
-
Далее в ходе процесса все элементы P-массива и затем по порядку все четыре S-блока заменяются выходом постоянно меняющегося алгоритма Blowfish.
Всего для генерации всех необходимых подключей требуется 521 итерация. Приложения могут сохранять подключи - нет необходимости выполнять процесс их получения многократно.