3.3. Конструкция Фейстеля

Конструкция Фейстеля (Н. Feistel), или сеть Фейстеля, представляет собой разновидность итерированного блоч­ного шифра [194,195). При шифровании блок открыто­го текста разбивается на две равные части правую и левую. Очевидно, что длина блока при этом должна быть четной. На каждом цикле одна из частей подверга­ется преобразованию при помощи функции f и вспомо­гательного ключа k_i полученного из исходного секретно­го ключа. Результат операции суммируется по модулю 2 (операция XOR) с другой частью. Затем левая и правая части меняются местами. Схема конструкции Фейстеля представлена на рисунке 3.5. Преобразования на каждом ци­кле идентичны, но на последнем не выполняется переста­новка. Процедура дешифрования аналогична процедуре шифрования, однако k_i выбираются в обратном порядке. Конструкция Фейстеля хороша тем, что прямое и обрат­ное криптографические преобразования для какого блоч­ного шифра имеют идентичную структуру.

Конструкция Фейстеля применяется в криптоалгорит­мах DES, ГОСТ 28147-89, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и др. Блочный шифр, ис­пользующий такую конструкцию, является обратимым и гарантирует возможность восстановления входных дан­ных функции f на каждом цикле. Сама функция f не обязательно должна быть обратимой. При задании про­извольной функции f не потребуется реализовывать две различные процедуры - одну для шифрования, а дру-гую для дешифрования. Структура сети Фейстеля автоматически позаботится об этом.

Рисунок 3.5 Схема конструкции Фейстеля

Существует еще одно объяснение идеи конструкции Фейстеля. В своих лекциях известный криптограф Дж. Мэсси (J. L. Massey) вводит понятие инволютивного оюбражения. Так, неко-торая функция f является инволюцией, если f (f(x)) = х для всех х. Для такой функции область определения (множество аргументов х) и область значений (множество значений f(x)) совпадают. Например, функция f (х) = х является инволюцией, так как f (f (х)) = f (х) =  (х) = х. Другой пример инволюции: f(x) = х  с, где с - некоторая константа. Действительно, f (f (х)) = f (хс) = х  с  с = х.

Рисунок 3.6 - Шифрование композиционного блочного шифра

Инволюция является полезным свойством при констру­ировании блочных шифров. Рассмотрим композиционный блочный шифр, включающий n последовательных крипто­графических преобразований Е_i^K(), 1  i  n на ключе К (рис. 3.6).

Рисунок 3.7 - Дешифрование композиционного блочного шифра

Тогда шифротекст С получается в результате преобразования

С = Е_n^K(Е_n-1^K (…Е₂^K (Е₁^K (P))…)),

где Р — открытый текст (рисунок 3.7). Если функция Е_i^K является инволюцией, открытый текст может быть восстановлен в результате преобразования

P = Е₁^K(Е₂^K (…Е_n-1^K (Е_n^K (С))…)).

Действительно, согласно описанному выше свойству имеем:

P = Е₁^K(Е₂^K (…Е_n-1^K (Е_n^K (Е_n^K(Е_n-1^K (…Е₂^K (Е₁^K (P))…))))…))

Так как Е_n^K (Е_n^K()) =  , Е_n-1^K (Е_n-1^K()) =  ; и так далее вплоть до получения тождества

P  P.