Алгоритм шифрования Blowfish

Описание алгоритма Blowfish

До появления Blowfish существовавшие алгоритмы были либо запатентованными, либо ненадёжными, а некоторые и вовсе держались в секрете (например, Skipjack). Алгоритм был разработан в 1993 году Брюсом Шнайером в качестве быстрой и свободной альтернативы устаревшему DES и запатентованному IDEA. По заявлению автора, критерии проектирования Blowfish были:

• скорость (шифрование на 32-битных процессорах происходит за 26 тактов);

• простота (за счёт использования простых операций, уменьшающих вероятность ошибки реализации алгоритма);

• компактность;

• настраиваемая стойкость.

Blowfish -блочный шифр, который шифрует данные в 8- байтовых блоках. Алгоритм включает в себе 2 части: часть расширения ключей и часть кодирования данных. Расширение ключа преобразует ключи переменной длинны, в большинстве 56 байтовые (448 битов), в несколько суммированных массивов подключей размером в 4168 байт. Данный алгоритм имеет 16 итераций. Каждая итерация включает в себя зависящие от ключа перестановки, и зависящей от ключей и данных замены. Все операции XOR и добавления на 32-битных словах. Единственные дополнительные операции - четыре индексированных поиска данных в целочисленных массивах. [1].

Blowfish шифрует данные 64-битными блоками. Ключ алгоритма имеет переменный размер - от 32 до 448 бит.

Алгоритм представляет собой сеть Фейстеля. Шифрование данных выполняется за 16 раундов, в каждом из которых над левым 32-битным субблоком данных проводятся следующие действия:

1. Значение субблока складывается с ключом i-го раунда Ki операцией XOR, результат операции становится новым значением субблока.

2. Субблок обрабатывается функцией F (описана ниже), результат обработки накладывается на правый субблок операцией XOR.

3. Субблоки меняются местами во всех раундах, кроме последнего.

4. После 16 раундов выполняется наложение на субблоки еще двух подключей: K17 и K18 складываются операцией XOR с правым и левым субблоками соответственно.

 

Рисунок 1. Структура алгоритма Blowfish.

 

 

Функция F (рис. 2) обрабатывает субблок следующим образом:

1. 32-битное входное значение делится на четыре фрагмента по 8 бит, каждый из которых прогоняется через одну из таблиц замен S1...S4 с получением четырех 32-битных выходных фрагментов. Таблицы замен содержат по 256 значений по 32 бита, они не являются фиксированными и зависят от ключа шифрования. Принципы их вычисления подробно описаны ниже.

2. Первые два выходных фрагмента складываются по модулю.

3. Результат предыдущего шага складывается операцией XOR с третьим выходным фрагментом.

4. Выходное значение функции F получается путем сложения результата предыдущего шага с четвертым выходным фрагментом по модулю.

Функцию F можно определить так:

F(x) = ((S₁(x₁) + S₂(x₂) mod 2³²) S₃(x₃)) + S₄(x₄) mod 2³²,

где x1...x4 - 8-битные фрагменты входного значения x.

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

Рисунок 2. Функция F алгоритма Blowfish.

Процедура расширения ключа

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

Задача процедуры расширения ключа состоит в вычислении на основе ключа шифрования значений ключей раунда K₁...K₁₈ и таблиц замен S₁...S₄.

Расширение ключа выполняется в 5 этапов:

1. Исходные значения ключей раунда и таблиц замен инициализируются фиксированной псевдослучайной строкой, в качестве которой используется шестнадцатеричная запись дробной части числа π (пи).

2. Операцией XOR на K₁ накладываются первые 32 бита ключа шифрования, на K₂ - следующие 32 бита и т. д. - до K₁₈. Если ключ шифрования короче, чем необходимо для наложения на K₁...K₁₈, то он накладывается циклически.

3. С использованием полученных ключей раунда и таблиц замен выполняется шифрование алгоритмом Blowfish блока данных, состоящего из 64 нулевых бит. Результат становится новым значением ключей K₁ и K₂.

4. Результат предыдущего этапа снова шифруется алгоритмом Blowfish (причем уже с измененными значениями ключей K₁ и K₂), в результате получаются новые значения ключей K₃ и K₄.

5. Шифрование выполняется до тех пор, пока новыми значениями не будут заполнены все ключи раунда и таблицы замен.

В процедуре расширения ключа мы видим, что для создания ключа необходима какая-то фиксированная псевдослучайная строка S (набор из любых шестнадцатеричных символов). На строку S c помощью операции XOR накладывается ключ принадлежащий пользователю. В теории для каждого ключа должна соответствовать своя фиксированная псевдослучайная строка S.