Сети Фейстеля.

Сеть Фейстеля подразумевает разбиение обрабатываемого блока данных на несколько субблоков (чаще всего - на два), один из которых обрабатывается некоей функцией и накладывается на один или несколько остальных субблоков.

а) б)

Рис. 1. Структура алгоритмов на основе сети Фейстеля

а) шифрования, б) дешифрования.

Блок открытого текста делится на две равные части ( ). Для каждого раунда ( - номер раунда) вычисляется:

где — некоторая функция, а — ключ -го раунда.

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

Результатом выполнения раундов является . Но обычно в -ом раунде перестановка и не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации:

Такая структура алгоритмов шифрования получила свое название по имени Хорста Фейстеля (Horst Feistel) - одного из разработчиков алгоритма шифрования Lucifer и разработанного на его основе алгоритма DES (Data Encryption Standard) - бывшего (но до сих пор широко используемого) стандарта шифрования США. Оба этих алгоритма имеют структуру, аналогичную показанной на рис. 1. Среди других алгоритмов, основанных на сети Фейстеля, можно привести в пример отечественный стандарт шифрования ГОСТ 28147-89, а также другие весьма известные алгоритмы: RC5, Blowfish, TEA, CAST-128 и т.д.

На сети Фейстеля основано большинство современных алгоритмов шифрования - благодаря множеству преимуществ подобной структуры, среди которых стоит отметить следующие:

Алгоритмы на основе сети Фейстеля могут быть сконструированы таким образом, что для зашифрования и расшифрования могут использоваться один и тот же код алгоритма - разница между этими операциями может состоять лишь в порядке применения ключей ; такое свойство алгоритма наиболее полезно при его аппаратной реализации или на платформах с ограниченными ресурсами; в качестве примера такого алгоритма можно привести ГОСТ 28147-89.

Алгоритмы на основе сети Фейстеля являются наиболее изученными - таким алгоритмам посвящено огромное количество криптоаналитических исследований, что является несомненным преимуществом как при разработке алгоритма, так и при его анализе.

Существует и более сложные структуры сети Фейстеля. При большом размере блоков шифрования (128 бит и более) реализация сети Фейстеля на 32-разрядных архитектурах может вызвать затруднения, поэтому применяются модифицированные варианты этой конструкции. Обычно используются сети с 4 ветвями. На рисунке показаны наиболее распространенные модификации. Также существуют схемы, в которых длины половинок и не совпадают. Они называются несбалансированными.

рис. 2. Модификации сети Фейстеля