Основные схемы построения симметричных алгоритмов шифрования

Схема Фсйстеля, или сеть Фсйстеля (англ. Feistel, иногда в русскоязычной литературе можно встретить перевод Файстель), была первоначально предложена при разработке алгоритма шифрования Люцифер (Lucifer), который во многом схож со стандартом DES. Схема оказалась настолько удачной, что по такому принципу конструировались практически все блочные шифры до появления алгоритма Rijndael, разработчики которого предложили использовать другой способ построения блочных шифров.

Схема Фейстеля представляет собой разновидность итерированного блочного шифра. При зашифровании блок открытого текста разделяется на две равные части — правую и левую. При этом длина исходного блока данных должна быть четной. В каждом цикле одна из частей подвергается преобразованию при помощи функции F и подключа Ki, полученного из исходного секретного ключа К. Результат операции суммируется по модулю 2 (операция XOR) с другой частью. Затем левая и правая части меняются местами. Общий вид одного цикла алгоритма шифрования, построенного по схеме Фейстеля, представлен на рис. 8. Преобразования в каждом цикле одинаковы, но на последнем не выполняется перестановка. Процедура расшифрования аналогична процедуре зашифрования за тем исключением, что подключи ki выбираются в обратном порядке. Если же при зашифровании в последнем цикле была выполнена перестановка, то расшифрование следует начать с перестановки левой и правой частей блока данных.

Уже отмечалось, что к алгоритмам шифрования, построенным по схеме Фейстеля, относятся такие алгоритмы, как DES и ГОСТ 28 147–89. Помимо вышеуказанных алгоритмов существует целый ряд други, таких как, например, Lucifer, FEAL, Khufu, Khafre, LOKI, Blowfish, также построенных по схеме Фсйстеля. Блочный алгоритм шифрования, использующий описанную конструкцию, является обратимым и гарантирует возможность восстановления входных данных функции F в каждом цикле. Сама функция F не обязательно должна быть обратимой. При задании произвольной функции F не потребуется реализовывать две различные процедуры — одну для шифрования, а другую для расшифрования. Ниже мы рассмотрим почему это возможно.

Рис. 8. Один раунд алгоритма шифрования, построенный по схеме Фейстеля.

Необходимо также отметить, что деление исходного шифра на две части может быть заменено делением на четыре, восемь частей и более. Такие алгоритмы шифрования называются производными от схемы Фейстеля. Некоторые современные шифры имеют такую структуру. Например, алгоритм шифрования CAST или закрытый в свое время алгоритм шифрования Skipjack. На рис. 9 показаны пример некоторых модификаций схемы Фейстеля.

Разработчики алгоритма Rijndael ушли от общепринятой схемы Фейстеля и организовали свой шифр так, чтобы не разделять шифруемый текст на половинки, а выполнять все преобразования над цельным блоком данных. Такая структура получила название SPN или SP-сеть или Сеть на основе подстановок и перестановок (от англ, substitution-permutation network). По такому же принципу были построены и некоторые другие алгоритмы шифрования, представленные в качестве кандидатов на конкурс AES, например, алгоритмы шифрования MARS и Serpent. В качестве примера организации шифрования с помощью SP-сети приведем алгоритм шифрования Threefish, лежащий в основе функции хэширования Skein (рис. 10).

Рис. 9. Модификация схемы Фейстеля.

Рис. 10. Пример построения шифра на основе SP-сети.