Шифры Фейстеля. 
Системные и прикладные аспекты

Одна из первых конструкций раундовой функции (в DAE5-алгоритме) основана на биективном регистре сдвига длины 2 над V_:r2- Она нашла широкое применение в дальнейших разработках блочных шифров {FEAL, ГОСТ 28 147–89 (см. работу [13]), Khufu, Khafre, LOKI, Blowfish и др.). Такие шифры названы шифрами Фейстеля в честь одного из разработчиков алгоритма DES.

Обозначим х = (х, х₂) е V_n х V_n. Шифр Фейстеля — это итеративный СБШ, раундовая функция ф (х, q) которого имеет вид.

где |/: V_n х Q —> V_n. Функцию ф (х, q) называют цикловой (раундовой) функцией Фейстеля, а функцию |/(.г₂, q) — функцией усложнения шифра Фейстеля. Шифры Фейстеля отличаются конструкцией функции усложнения ф, входного и выходного отображений и свойствами ключевого расписания. Схема реализации раундовой функции Фейстеля дана на рис. 15.1.

ф (х, q) = (х₂, i (x₂, q) © .г,).

Рис. 15.1. Схема реализации цикловой функции ф (х, ц)

Из равенства (15.5) следует, что ср_г/ есть подстановка регистра сдвига длины 2 над множеством с обратной связью ф (х₂, ^{х П}Р^И любом у е (). Биективность преобразования ср,_; следует по теореме 7.5 (см. ч. 1 данного учебника) из биективности по х_{ функции обратной связи 1(/(х₂, я) © (c)х^ Заметим, что преобразование ср_г/ биективное и при использовании других биективных по X) функций, например сложения по модулю 2″ .

Реализация шифра Фейстеля более проста по сравнению с реализацией 5Р-сети итеративного СБШ общего вида, что очевидно из сравнения областей определения отображений ф (х, ц) и (/(х₂, ф), являющихся основными элементами соответствующих 5Р-сетей. Вместе с гем в ЛУ-'-сети шифра Фейстеля перемешивание входных блоков происходит медленнее, так как перемешиваются биты одной половины блока, а остальные биты лишь сдвигаются.

Установим важное свойство раундовой функции Фейстеля.

Лемма 15.1. При любой функции усложнения.

^ Докажем равносильное равенство ф_г/Г" ср_г/Г" = е, полученное из равенства (15.6) домножением слева на ср_г/. Используя равенство (15.5) и инволютивность подстановки Т^п, при любых д е (2 и х_1? х₂ е получаем х₂) = ф^Г"ф^(х₂, = Ф_г/РЧ^ц ?(*1″ ?) ® *2) = Ф*(?(*1> <7) ©.

(c)Х₂, Х^ = (Х_{, Х₂). ?

Теорема 15.2. Если п_(/(х) = 8~^хТ^п(х) при любом д е (У, то алгоритм шифрования Фейстеля инволютивный и расшифрование отличается от зашифрования лишь использованием раундовых ключей в обратном порядке.

^ В условиях теоремы подстановки Е_к и Е_к~^х определяются формулами.

В равенстве (15.8) сделаем г замен для подстановок ф"¹, …, ф~¹ в соответствии с выражением (15.6). Учитывая, что Т^1п = е, получаем после замен равенство Е_к~^(у) = б^Г^ф^.ф^ 5^₊₁(г/). Сравнивая его с формулой (15.7), убеждаемся в том, что теорема верна. ?