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

В криптография, а Шифр Фейстеля (также известный как Блочный шифр Луби – Рэкоффа) - симметричная структура, используемая при построении блочные шифры, названный в честь Немецкий -родившийся физик и криптограф Хорст Фейстель кто провел новаторские исследования, работая на IBM (СОЕДИНЕННЫЕ ШТАТЫ АМЕРИКИ); это также широко известно как Сеть Фейстеля. Большая часть блочные шифры использовать схему, включая США Стандарт шифрования данных, советский / российский ГОСТ и более поздние Blowfish и Twofish шифры. В шифре Фейстеля шифрование и дешифрование - очень похожие операции, и оба состоят из итеративного выполнения функции, называемой «циклической функцией», фиксированное количество раз.

История

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

Дизайн

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

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

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

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

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

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

Позволять ${ displaystyle { rm {F}}}$ - круглая функция и пусть ${ displaystyle K_ {0}, K_ {1}, ldots, K_ {n}}$ быть подключами для раундов ${ displaystyle 0,1, ldots, n}$ соответственно.

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

Разделите блок открытого текста на две равные части, ( ${ displaystyle L_ {0}}$ , ${ displaystyle R_ {0}}$ )

Для каждого раунда ${ Displaystyle я = 0,1, точки, п}$ , вычислить

{ Displaystyle L_ {я + 1} = R_ {я} ,}

{ displaystyle R_ {i + 1} = L_ {i} oplus { rm {F}} (R_ {i}, K_ {i}).}

Где ${ displaystyle oplus}$ средства XOR. Тогда зашифрованный текст ${ displaystyle (R_ {n + 1}, L_ {n + 1})}$ .

Расшифровка зашифрованного текста ${ displaystyle (R_ {n + 1}, L_ {n + 1})}$ достигается путем вычисления для ${ Displaystyle я = п, п-1, ldots, 0}$

{ Displaystyle R_ {я} = L_ {я + 1} ,}

{ displaystyle L_ {i} = R_ {i + 1} oplus operatorname {F} (L_ {i + 1}, K_ {i}).}

потом ${ displaystyle (L_ {0}, R_ {0})}$ это снова открытый текст.

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

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

Несбалансированные шифры Фейстеля используют модифицированную структуру, в которой ${ displaystyle L_ {0}}$ и ${ displaystyle R_ {0}}$ не одинаковой длины.^[7] В Скипджек cipher является примером такого шифра. В Инструменты Техаса транспондер с цифровой подписью использует собственный несбалансированный шифр Фейстеля для выполнения проверка подлинности запрос – ответ.^[8]

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

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

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

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

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

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

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

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

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

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

Криптография
Потоковый шифр
Сеть подстановки-перестановки
Схема подъема для дискретного вейвлет-преобразования имеет примерно такую же структуру
Шифрование с сохранением формата
Схема Лая – Мэсси

внешняя ссылка

Feistelnetwork - реализация на Go

[1] Менезеш, Альфред Дж .; Оршот, Пол К. ван; Ванстон, Скотт А. (2001). Справочник по прикладной криптографии (Пятое изд.). п.251. ISBN 978-0849385230.

[2] Шнайер, Брюс (1996). Прикладная криптография. Нью-Йорк: Джон Вили и сыновья. ISBN 0-471-12845-7.

[stinson-3] Стинсон, Дуглас Р. (1995). Криптография: теория и практика. Бока-Ратон: CRC Press. ISBN 0-8493-8521-0.

[pseudorandom-4] Луби, Майкл; Ракофф, Чарльз (апрель 1988 г.), "Как построить псевдослучайные перестановки из псевдослучайных функций", SIAM Журнал по вычислениям, 17 (2): 373–386, Дои:10.1137/0217022, ISSN 0097-5397

[7-rounds-5] Патарин, Жак (октябрь 2003 г.), Боне, Дэн (ред.), «Лубы – Рэкофф: 7 туров на двоих хватит»^{п(1 − ε)} Безопасность" (PDF), Достижения в криптологии - CRYPTO 2003, Конспект лекций по информатике, 2729: 513–529, Дои:10.1007 / b11817, ISBN 978-3-540-40674-7, S2CID 20273458, получено 2009-07-27

[6] Чжэн, Юлянь; Мацумото, Цутому; Имаи, Хидеки (1989-08-20). О построении блочных шифров, надежно защищенных и не опирающихся на какие-либо недоказанные гипотезы. Достижения в криптологии - Труды CRYPTO '89. Конспект лекций по информатике. 435. С. 461–480. Дои:10.1007/0-387-34805-0_42. ISBN 978-0-387-97317-3.

[7] Шнайер, Брюс; Келси, Джон (1996-02-21). Несбалансированные сети Фейстеля и конструкция блочного шифра. Быстрое программное шифрование. Конспект лекций по информатике. 1039. С. 121–144. Дои:10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. Получено 2017-11-21.

[crypto-rfid-8] Боно, Стивен; Грин, Мэтью; Стаблфилд, Адам; Джуэлс, Ари; Рубин, Авиель; Шидло, Майкл (2005-08-05). «Анализ безопасности устройства RFID с поддержкой криптографии» (PDF). Материалы симпозиума по безопасности USENIX. Получено 2017-11-21.

[thorp-9] а ^б Моррис, Бен; Рогавей, Филипп; Стегерс, Тилль (2009). Как зашифровать сообщения в небольшом домене (PDF). Достижения в криптологии - CRYPTO 2009. Конспект лекций по информатике. 5677. С. 286–302. Дои:10.1007/978-3-642-03356-8_17. ISBN 978-3-642-03355-1. Получено 2017-11-21.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]