Блочные составные шифры

Идея, лежащая в основе составных, или композиционных, блочных шифров, состоит в построении криптостойкой системы путем многократного применения относительно простых криптографических преобразований, в качестве которых
К. Шеннон предложил использовать преобразования подстановки (substitution) и перестановки (permutation); схемы, реализующие эти преобразования, называются SP-сетями. Отмечается, что действие таких шифров аналогично "алгоритму", к которому прибегают, когда месят тесто:

РАСКАТАТЬ

СЛОЖИТЬ

РАСКАТАТЬ

СЛОЖИТЬ

РАСКАТАТЬ

СЛОЖИТЬ

Многократное использование этих преобразований (рис. 1.7) позволяет обес­печить два свойства, которые должны быть присущи стойким шифрам: рассеи­вание (diffusion) и перемешивание (confusion). Рассеивание предполагает рас­пространение влияния одного знака открытого текста, а также одного знака ключа на значительное количество знаков шифротекста. Наличие у шифра этого свойства:

· позволяет скрыть статистическую зависимость между знаками открытого текста, иначе говоря, перераспределить избыточность исходного языка посредством распространения ее на весь текст;

· не позволяет восстанавливать неизвестный ключ по частям.

Например, обычная перестановка символов позволяет скрыть частоты появ­ления биграмм, триграмм и т. д.

Цель перемешивания - сделать как можно более сложной зависимость между ключом и шифротекстом. Криптоаналитик на основе статистического анализа перемешанного текста не должен получить сколь-нибудь значительного количе­ства информации об использованном ключе. Обычно перемешивание осуществ­ляется при помощи подстановок. Как будет видно ниже, применение к каждому элементу открытого текста своей собственной подстановки приводит к появле­нию абсолютно стойкого шифра. Применение рассеивания и перемешивания порознь не обеспечивает необходимую стойкость (за исключением вышеупомянутого предельного случая), стойкая криптосистема получается только в резуль­тате их совместного использования.

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

 

Рис. 1.7. Схема простейшего итерационного шифра

Примерами прозрачных операций могут являться операции циклического сдвига, замены и т. п. Любое количество подряд выполняющихся операций цик­лического сдвига или замены всегда можно заменить одной эквивалентной опе­рацией соответственно циклического сдвига или замены. Если два преобразова­ния, выбранные в качестве соседних раундов, имеют общую прозрачность g и при этом существует простое преобразование, непрозрачное для g, это преобразование следует поместить между двумя раундами шифрования, и полученная композиция уже не будет прозрачной для g. Такие преобразования, чаще всего не зависящие от ключа, называются буферами. Помимо внутренних иногда при­меняют и внешние буфера, выполняющие преобразования, зависящие или не зависящие от ключа.

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

Составные шифры, использующие в качестве раундовых криптографически слабые преобразования, становятся нестойкими, если становятся известными какие-либо промежуточные результаты преобразований. По этой причине ис­пользование этой информации при криптоанализе составных шифров является некорректным.

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

Первыми широко известными практическими реализациями итерационного блочного шифра были разработанные X. Фейстелем, Д. Копперсмитом и другими сотрудниками фирмы IBM криптоалгоритмы Lucifer и созданный на его основе в 1974 г. в качестве стандарта шифрования данных в государственных и частных организациях DES (Data Encryption Standard). DES работает с блоками данных раз­рядностью 64 бита с применением 56-разрядного ключа, из которого по специаль­ному фиксированному алгоритму, использующему перестановки и сдвиги, выраба­тываются раундовые ключи). Применяемые преобразования- поразрядное сложе­ние по модулю 2, подстановки и перестановки; число раундов равно 16; перед нача­лом первого раунда выполняется начальная фиксированная перестановка IP, после 16-го раунда выполняется обратная перестановка. Следуя рекомендациям Шеннона, в каждом раунде выполняется один шаг перемешивания (с использованием соответствующего раундового ключа и 5-блоков), после которого следует шаг рассеивания, не зависящий от ключа.

 

Интересно отметить, что в первоначальной схеме, предложенной IBM, все шестнадцать 48-разрядных раундовых ключей выбирались независимо, т. е. раз­мер ключа был равен 768 битам. Однако по требованию Агентства националь­ной безопасности США (АЫБ), во-первых, размер ключа был уменьшен до 64 бит, из которых только 56 являются секретными, во-вторых, в алгоритме опре­делены перестановки лишь специального вида, не зависящие от ключа, что на­водило критиков этого алгоритма на мысль, что АНБ могла использовать из­вестные ей слабости алгоритма для его взлома. На протяжении последних десятилетий DES подвергался интенсивному и всестороннему исследованию и по современным понятиям уже не считается надежным.

Существует несколько предложений, направленных на усовершенствование DES. Наиболее известное из них заключается в трехкратном применении алго-ритма (Triple DES) по схемам, показанным на рис. 1.9.

Наиболее известные блочные шифры - IDEA, BLOWFISH, SKIPJACK.

IDEA (International Data Encryption Algorithm) разработан в 1991 г., работает с блоками данных длиной 64 бита, используя ключ длиной 128 бит, число раундов равно восьми. Используемые преобразования- умножение по модулю 216+ 1, сложение по модулю 2, сложение по модулю 216. Авторы - К. Лэй, Д. Мэссей.

BLOWFISH - разработан в 1994 г. Б. Шнайером; работает с блоками данных разрядностью 64 бита, используя ключ переменной длины (максимальная раз­рядность равна 448 битам), число раундов равно 16. Используемые преобразования - подстановка, сложение по модулю 2, сложение по модулю 232.

SKIPJACK - разработан в 1990 г. NSA в качестве криптоалгоритма для микросхем Clipper и Capstone. Первоначально алгоритм был объявлен секретным, однако впоследствии его описание "просочилось" в Интернет. Шифр работает с блоками данных разрядностью 64 бита с использованием 80-разрядного ключа. Число раундов равно 32.