шифр Фейстеля

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

История

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

Дизайн

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

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

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

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

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

Подробности конструкции

Пусть будет функцией раунда, а пусть будут подключи для раундов соответственно. $\mathrm {F}$ $K_{0},K_{1},\ldots ,K_{n}$ $0,1,\ldots ,n$

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

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

Для каждого раунда вычислите $i=0,1,\точки,n$

L_{i+1}=R_{i},

R_{i+1}=L_{i}\oplus \mathrm {F} (R_{i},K_{i}),

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

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

R_{i}=L_{i+1},

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

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

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

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

Несбалансированные шифры Фейстеля используют модифицированную структуру, где и не имеют одинаковой длины. ^[7] Шифр Skipjack является примером такого шифра. Транспондер цифровой подписи Texas Instruments использует фирменный несбалансированный шифр Фейстеля для выполнения аутентификации вызов-ответ . ^[8] $L_{0}$ $R_{0}$

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

Другие применения

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

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

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

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

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

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

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

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

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

Ссылки

^ Менезес, Альфред Дж.; Ооршот, Пол К. ван; Ванстоун, Скотт А. (2001). Справочник по прикладной криптографии (Пятое изд.). Тейлор и Фрэнсис. стр. 251. ISBN 978-0849385230.
^ Шнайер, Брюс (1996). Прикладная криптография . Нью-Йорк: John Wiley & Sons. ISBN 0-471-12845-7.
^ Стинсон, Дуглас Р. (1995). Криптография: теория и практика . Бока-Ратон: CRC Press. ISBN 0-8493-8521-0.
^ Luby, Michael; Rackoff, Charles (апрель 1988), «Как построить псевдослучайные перестановки из псевдослучайных функций», SIAM Journal on Computing , 17 (2): 373–386, doi :10.1137/0217022, ISSN 0097-5397.
^ Патарин, Жак (октябрь 2003 г.), Боне, Дэн (ред.), Достижения в криптологии - CRYPTO 2003 (PDF) , Конспект лекций по информатике, т. 2729, стр. 513–529, doi :10.1007/b11817, ISBN 978-3-540-40674-7, S2CID 20273458 , получено 2009-07-27
^ Чжэн, Юйлян; Мацумото, Цутому; Имаи, Хидеки (1989-08-20). «О построении блочных шифров, доказуемо безопасных и не полагающихся ни на какие недоказанные гипотезы». Достижения в криптологии — Труды CRYPTO' 89. Заметки лекций по информатике. Том 435. С. 461–480. doi :10.1007/0-387-34805-0_42. ISBN 978-0-387-97317-3.
^ Шнайер, Брюс; Келси, Джон (1996-02-21). "Несбалансированные сети Фейстеля и проектирование блочных шифров". Быстрое программное шифрование. Конспект лекций по информатике. Том 1039. С. 121–144. doi :10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. Получено 21.11.2017 .
^ Боно, Стивен; Грин, Мэтью; Стабблфилд, Адам; Джуэлс, Ари; Рубин, Авиель; Шидло, Майкл (2005-08-05). "Анализ безопасности криптографически-включенного RFID-устройства" (PDF) . Труды симпозиума по безопасности USENIX . Получено 21 ноября 2017 г.
^ ab Моррис, Бен; Рогауэй, Филлип; Стегерс, Тилл (2009). «Как шифровать сообщения в небольшом домене». Достижения в криптологии — CRYPTO 2009 (PDF) . Конспект лекций по информатике. Том 5677. С. 286–302. doi :10.1007/978-3-642-03356-8_17. ISBN 978-3-642-03355-1. Получено 21.11.2017 .