Системы блочного шифрования и симметричные шифры

Схема Фейстеля

В литературе, посвященной криптографии схема Фейстеля (Н. Feistel) также часто называется конструкция Фейстеля (Н. Feistel), или сеть Фейстеля. Условимся полагать, что это синонимичные понятия. Рассматриваемый подход представляет собой разновидность итерированного блочного шифра.

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

2. На каждом цикле одна из частей (например, левая) подвергается преобразованию при помощи функции f и вспомогательного ключа k_i, полученного из исходного секретного ключа.

3. Результат операции суммируется по модулю 2 (команда процессора - XOR) с другой частью.

4. Затем левая и правая части меняются местами.

Схема конструкции Фейстеля представлена на рисунке 1.

Рис. 1.1 Принцип работы схемы Фейстеля

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

Рассмотренная схема лишь определяет подход, который может иметь различные реализации, выраженные в конечных алгоритмах. Так из наиболее известных алгоритмов, реализующих данную схему, можно выделить: DES, ГОСТ 28147-89, Lucifer, FEAL, Khufu, Khaire, JOKI, COST, CAST, Blowfish, и других.

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

Существует еще одно объяснение идеи конструкции Фейстеля. В своих лекциях известный криптограф Дж. Мэсси (J. L. Massey) вводит понятие иволютивного отображения.

Так, некоторая функция является инволюцией, если f(f(x)) = x для всех х. Для такой функции область определения (множество аргументов х) и область значений (множество значений f(x)) совпадают.

Например, функция f(x) = −x является инволюцией, так как f(f(x)) = f(−x) = −(−x) = х. Другой пример инволюции: f(x) = хÅс, где с — некоторая константа. Действительно, f(f(x)) = f(xÅс) = хÅсÅс = х. Так как сÅс = 0, а хÅ0 = х

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

C = Е^K_n(Е^K_n−1(…Е^K₁(P)…)), (2.1)

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

P = Е^K₁(Е^K₂(…Е^K_n(C)…)). (2.2)