Алгоритм BlowFish — это криптографический алгоритм, который реализует блочное симметричное шифрование при переменной длине ключа.
Введение
В конце 1993-го года в криптографическом мире сформировалась достаточно неловкая ситуация. Алгоритм симметричного шифрования DES, имеющий не очень сильный 56-битный ключ, приближался к своему фиаско, а существующие в то время альтернативные версии, например, Khufu, REDOC II, IDEA были запатентованными объектами и являлись недоступными для свободного применения. Алгоритмы RC2 и RC4, которые были разработаны в то время компанией RSA Security, также предполагали осуществление лицензионной процедуры. И в общем, криптографическая индустрия в границах государственных организаций и больших компаний была направлена на использование секретных алгоритмов, подобных, например, Skipjack.
Таким образом образовался некоторый вакуум в этой сфере. Требовался алгоритм шифрования, который стал бы более криптостойким в сравнении с отмирающим DES. Но, при этом, не имел бы каких-либо ограничений на право своего применения. И такой алгоритм вскоре появился. В 1994-ом году, на семинаре Fast Software Encryption в Кембридже, а затем и в журнале «Lecture Notes in Computer Science», Брюс Шнайер осуществил презентацию своего алгоритма блочного шифрования, получившего название Blowfish.
Характерными чертами данного алгоритма явились более высокий уровень криптографической стойкости, в сравнении с алгоритмом DES, повышенная скорость операций шифрования и дешифровки (путем генерации таблиц замены), а самое главное возможность его бесплатного использования для различных целей.
Алгоритм Blowfish
BlowFish является алгоритмом 64-битного блочного шифра, имеющим ключ переменной длины. Как было указано выше, сформировал его известный специалист в сфере криптографии и защиты информации Брюс Шнайер (Bruce Schneier). В общем варианте алгоритм имеет в свое м составе следующие этапы:
- Этап расширения ключа.
- Этап шифрации и дешифрации исходных данных.
На рисунке ниже изображена блок-схема этого алгоритма.
Рисунок 1. Блок-схема алгоритма. Автор24 — интернет-биржа студенческих работ
На первом этапе, то есть, этапе расширения ключа, исходный ключ должен быть преобразован в матрицу раундовых ключей (P) и матрицу подстановки (S, Substitution-box) (или замены). Их общий объе м равен 4168 байт. Вероятно, это «расширение» от 448 бит до 4168 байт и определило выбор названия алгоритма Blowfish.
На желудке иглобрюхих рыбешек имеются мешкообразные наросты. Когда появляется опасность, то они заполняются водой или воздухом, и рыба превращается в аналогию раздувшегося шара с торчащими шипами. Шарообразное состояние превращает таких рыб в практически неуязвимых для хищников. А когда все -таки сравнительно большой хищник будет пытаться проглотить такой шар, то он может застрять в горле у агрессора, который в дальнейшем просто может умереть.
Шифрование данных, а также формирование матрицы раундовых ключей и подстановки, может быть выполнено путем использования сети Фейстеля, которая состоит в свою очередь из шестнадцати раундов. По этой причине, прежде чем рассматривать этапы расширения ключа и шифрации данных в деталях, сначала следует рассмотреть организацию сети Фейстеля.
В 1971-ом году, основатель стандарта DES, Хорст Фейстель (Horst Feistel), сотрудник компании IBM, сумел разработать пару устройств, реализовавших разные алгоритмы шифрования, получившие впоследствии общее название «Люцифер». В одном из данных устройств он применил схему, которая в дальнейшем была названа Сетью Фейстеля. Данная сеть является определенной многократно итерированной (повторяющейся) структурой, именуемой ячейкой Фейстеля, как показано на рисунке ниже.
Рисунок 2. Сеть Фейстеля. Автор24 — интернет-биржа студенческих работ
Принцип действия сети можно представить следующим образом:
- Начальные данные необходимо разбить на блоки, имеющие фиксированную длину, которая обычно является кратной степени двойки, например, 64 бит или 128 бит. В случае, когда длина блока начальных данных меньше, чем длина разрядности шифра, то блок следует дополнить каким-нибудь заранее определенным образом.
- Блок следует поделить на пару равных подблоков, а именно, «левый» L0 и «правый» R0. В случае, когда используется 64-битная разрядность, следует поделить блоки, длиной по 32 бита каждый.
- «Левый подблок» L0 следует видоизменить функцией итерации F(L0, P0) в зависимости от ключа P0, а затем сложить его по модулю 2 (XOR) с «правым подблоком» R0.
- Итог сложения необходимо присвоить новому левому подблоку L1, который превращается в левую половину входных данных для следующего раунда, а «левый подблок» L0 следует присвоить без коррективов новому правому подблоку R1, который превращается в правую половину.
- Данную операцию следует повторить n-1 раз, причем при переходе от одного этапа к следующему этапу должны изменяться раундовые ключи (P0, P1, P2 и так далее), где n является количеством раундов для применяемого алгоритма.
Процедура расшифровки аналогична процессу шифрования за исключением того обстоятельства, что раундовые ключи необходимо использовать в обратном порядке.
В общем варианте, алгоритм шифрования Blowfish является сетью Фейстеля, но с определенными особенностями генерации и применения раундовых ключей (P0, P1 …). Сначала сделаем допущение, что функция итерации F в алгоритме Blowfish является некоторым «черным ящиком», который должен принимать на входе и выдавать на выходе 32-битное число (DWORD).
Причем для 32-битных раундовых ключей Pn выполняются следующие операции:
- Ключи должны вычисляться по определенному правилу от исходного ключа, имеющего длину до 448 бит.
- Ключи не могут быть аргументами для функции итерации F.
- Ключи должны непосредственно складываться по модулю 2 (XOR) с «левым блоком». Итоговый результат данной операции считается входящим 32-битным аргументом для функции F.
В алгоритме Blowfish при выполнении шифрования исполняются шестнадцать раундов (внутри сети Фейстеля), а семнадцатый и восемнадцатый ключи должны суммироваться с левым и правым выходным блоком последнего раунда.
