Шифр Фейстеля - Feistel cipher

В криптографии , шифра Фейстеля (также известный как Лубы-Rackoff блочного шифра ) является симметричной структурой , используемой в строительстве блочных шифров , названный в честь немецкого -born физика и криптограф Файстель кто пионерские исследования, работая на IBM (США) ; она также широко известна как сеть Фейстеля . Большая часть блочных шифров использует эту схему, в том числе стандарт шифрования данных США , советский / российский ГОСТ и новейшие шифры Blowfish и Twofish . В шифре Фейстеля шифрование и дешифрование - очень похожие операции, и оба состоят из итеративного выполнения функции, называемой «циклической функцией», фиксированное количество раз.

История

Многие современные симметричные блочные шифры основаны на сетях Фейстеля. Сети Фейстеля впервые были замечены на коммерческой основе в шифре Люцифера IBM , разработанном Хорстом Фейстелем и Доном Копперсмитом в 1973 году. Сети Фейстеля приобрели респектабельность, когда федеральное правительство США приняло DES (шифр, основанный на Люцифере с изменениями, внесенными АНБ ). Подобно другим компонентам DES, итеративный характер конструкции Фейстеля упрощает аппаратную реализацию криптосистемы (особенно на оборудовании, доступном на момент разработки DES).

дизайн

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

Теоретическая работа

Структура и свойства шифров Фейстеля были тщательно проанализированы криптографами .

Майкл Луби и Чарльз Рэкофф проанализировали конструкцию шифра Фейстеля и доказали, что если функция раунда является криптографически безопасной псевдослучайной функцией с K i, используемым в качестве начального числа, то 3 раунда достаточно, чтобы сделать блочный шифр псевдослучайной перестановкой , а 4 раунда достаточно, чтобы сделать его «сильной» псевдослучайной перестановкой (что означает, что он остается псевдослучайным даже для злоумышленника, который получает доступ оракула к своей обратной перестановке). Из-за этого очень важного результата Люби и Рэкоффа шифры Фейстеля иногда называют блочными шифрами Луби – Рэкоффа.

Дальнейшая теоретическая работа несколько обобщила конструкцию и дала более точные оценки безопасности.

Детали конструкции

Схема шифра Фейстеля en.svg

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

Тогда основная операция выглядит следующим образом:

Разделите блок открытого текста на две равные части, ( , )

Для каждого раунда вычислите

Где означает XOR . Тогда зашифрованный текст .

Расшифровка зашифрованного текста осуществляется путем вычисления

Затем снова открытый текст.

Схема иллюстрирует как шифрование, так и дешифрование. Обратите внимание на изменение порядка подключей для дешифрования; это единственное различие между шифрованием и дешифрованием.

Несбалансированный шифр Фейстеля

Несимметричные шифры Фейстеля используют модифицированную структуру , где и не имеет одинаковую длину. Полосатый шифр является примером такого шифра. Texas Instruments цифровая подпись транспондер использует собственный несбалансированное Фейстеля шифра для выполнения аутентификации запрос-ответ .

Перетасовка Торп это крайний случай неуравновешенной Фейстеля шифра , в котором одна сторона является один бит. У этого есть более доказуемая безопасность, чем у сбалансированного шифра Фейстеля, но требуется больше раундов.

Другое использование

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

Обобщенный алгоритм Фейстеля может использоваться для создания сильных перестановок на небольших доменах размером не степень двойки (см. Шифрование с сохранением формата ).

Сети Фейстеля как компонент дизайна

Независимо от того, является ли весь шифр шифром Фейстеля или нет, сети типа Фейстеля могут использоваться в качестве компонента конструкции шифра. Например, MISTY1 - это шифр Фейстеля, использующий трехэтапную сеть Фейстеля в своей раундовой функции, Skipjack - это модифицированный шифр Фейстеля, использующий сеть Фейстеля в своей перестановке G, а Threefish (часть Skein ) - это блочный шифр не-Фейстеля, который использует функцию MIX типа Фейстеля.

Список шифров Фейстеля

Фейстель или модифицированный Фейстель:

Обобщенный Фейстель:

Смотрите также

Рекомендации