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

Определение блочного шифра

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

3.2. Принцип итерирования

Принцип итерирования является основным при разработке криптографических преобразова­ний и заключается в многократной, состоящей из нескольких циклов обработке одного блока открытого текста. На каждом цикле данные подвергаются специальному преобразованию при участии вспомогательного ключа, полученного из заданного секретного ключа. Выбор числа циклов определяется требованиями криптостойкости и эффективности реализации блочного шифра. Как правило, чем больше циклов, тем выше криптостойкость и ниже эффективность реализации (больше задержка при шифровании/дешифровании) блочного шифра, и наобо­рот. Так, например, в случае DES (федеральный криптостандарт США) для того, чтобы все биты шифротекста зависели от всех битов ключа и всех битов открытою текста, необходимо 5 циклов криптографического преобразования [196,197]. DES с 16 циклами обладает высокой криитостойкостыо по отношению к ряду криптоаналити-ческих атак.

Конструкция Фейстеля (Н. 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.

Дата добавления: 2014-01-05