Алгоритм Blowfish

Алгоритм Blowfish разработан Брюсом Шнайером в 1994 г. Автор алгоритма предложил Blowfish в качестве замены стандарту DES. Несомненно, в 1994 г. замена DES на новый стандарт шифрования была уже актуальна из-за корот­кого ключа DES, который уже тогда можно было найти путем полного пере­бора. Брюс Шнайер предположил, что других реальных кандидатов на заме­ну DES нет, в частности, по следующим причинам (описаны Шнайером в спецификации алгоритма Blowfish [342]):

□ многие известные и криптографически стойкие (считающиеся таковыми на момент разработки алгоритма Blowfish) алгоритмы, например, IDEA (см. разд. 3.26) или REDOCII, являются запатентованными, что ограничи­вает их использование;

□ спецификация алгоритма ГОСТ 28147-89 (см. разд. 3.1) не содержит зна­чений таблиц замен, т. е., по мнению Шнайера, алгоритм описан не пол­ностью;

□ алгоритм Skipjack (см. разд. 3.52) вообще являлся секретным на тот момент.

Алгоритм Blowfish оказался весьма «удачным». Он очень широко реализован в различных шифровальных средствах — на сайте Шнайера приведен список из примерно 150 продуктов [343], которые шифруют алгоритмом Blowfish. Однако заменой стандарту DES он все же не стал.

Структура алгоритма

Поскольку Blowfish предполагался в качестве замены алгоритма DES, он, аналогично DES, шифрует данные 64-битными блоками. Размер ключа алго­ритма является переменным — от 32 до 448 битов.

clip_image002

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

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

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

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

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

После 16 раундов выполняется наложение на субблоки еще двух подключей: КХ1 и Кх% складываются операцией XOR с правым и левым субблоками со­ответственно.

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

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

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

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

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

clip_image004

Рис. 3.28. Функция F

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

F(x) = ((Sl(xl) + S2(x2) mod 232) 0 S3 (x3)) + S4 (x4) mod 232, где xxx4 — 8-битные фрагменты входного значения х

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

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

Задача процедуры расширения ключа состоит в вычислении на основе ключа шифрования значений ключей раундов КХ…КХ% и таблиц замен SXS4 . Для этого используется весьма сложная процедура расширения ключа, состоящая из следующих шагов:

1. Исходные значения ключей раундов и таблиц замен инициализируются фиксированной псевдослучайной строкой, в качестве которой использует­ся шестнадцатеричная запись дробной части числа я; инициализированная последовательность ключей КХ…КХ% приведена в табл. 3.9.

Таблица 3.9

243f6a88

85a308d3

13198а2е

03707344

а4093822

29913IdO

082efa98

ес4е6с89

452821е6

38d01377

be5466cf

34е90с6с

с0ас29Ь7

c97c50dd

3f84d5b5

Ь5470917

9216d5d9

8979fblb

В Приложении 1 приведены значения инициализированных таблиц замен, которые заполняются последующими знаками дробной части числа п [340].

2. Операцией XOR на накладываются первые 32 бита ключа шифрова­ния, на К2 — следующие 32 бита и т. д. до £18. Если используется более короткий ключ шифрования, чем необходимо для наложения на КХ…КХ%, то ключ шифрования накладывается циклически.

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

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

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

Достоинства и недостатки алгоритма

В своей книге «Прикладная криптография» [28] Брюс Шнайер привел сле­дующие ограничения алгоритма Blowfish.

□ «Алгоритм Blowfish не годится для применения в случаях, где требуется частая смена ключей». Процедура расширения ключа является достаточно ресурсоемкой, поэтому одно из достоинств алгоритма Blowfish — доста­точно высокая скорость шифрования — проявляется только в тех случаях, если на одном ключе шифруется достаточно большой объем информации. И наоборот, если менять ключ после каждого из шифруемых блоков, ско­рость алгоритма становится катастрофически низкой именно из-за необ­ходимости каждый раз выполнять расширение ключа. Сам Шнайер реко­мендует в приложениях, где критична скорость, хранить уже развернутый ключ (т.е. значения АГ1…ЛГ18 и 5j…54) и загружать его целиком вместо выполнения расширения исходного ключа шифрования [28].

□ «Большие требования к памяти не позволяют использовать этот алгоритм в смарт-картах». Стоит сказать, что принципиальная возможность реали­зации алгоритма в смарт-картах была одним из важных условий при вы­боре нового стандарта шифрования США на конкурсе AES, т. е. данный недостаток алгоритма Blowfish можно считать серьезным [284].

Кроме того, стоит отметить и менее серьезные недостатки алгоритма:

□ невозможность расширения ключа параллельно процессу шифрования;

□ небольшой по современным меркам размер блока шифруемых данных. Алгоритм Blowfish имеет и достаточно серьезные преимущества, в частности:

□ как было сказано выше, высокая скорость шифрования на развернутом ключе (см. также [344]);

□ простота алгоритма, снижающая вероятность ошибок при его реализации;

□ отсутствие известных успешных атак на полнораундовую версию алго­ритма.

Однако стоит сказать, что известный эксперт Серж Воденэ обнаружил, что методом дифференциального криптоанализа r-раундового алгоритма Blowfish с известными таблицами замен можно вычислить значения КХ…КХ% при наличии 28г+1 выбранных открытых текстов [381]. Это не актуально для полнораундовой версии алгоритма (и, тем более, для описанной выше полно­ценной версии алгоритма с вычисляемыми таблицами замен), но при исполь­зовании слабого ключи (Серж Воденэ обнаружил также у алгоритма Blowfish наличие слабых ключей, которые приводят к генерации слабых таблиц за­мен) выбранных открытых текстов требуется существенно меньше: 24/ + 1.

Вероятность, что произвольный ключ окажется слабым, составляет 2~ . Данная атака не является критичной, поскольку для полноценной версии ал­горитма слабые ключи не страшны [28, 341].

Явные достоинства и отсутствие критичных недостатков предопределили широкое использование алгоритма Blowfish.

Ты еще на торгуешь на Форекс/Forex!? торговля forex MegaTrade – пора Зарабатывать!

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100