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

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

История

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

Дизайн

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

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

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

Майкл Люби и Чарльз Ракофф проанализировали конструкцию шифра Фейстеля и доказали, что если функция раунда является криптографически безопасной псевдослучайной функцией с использованием K _i в качестве начального числа, то 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,\dots ,n$ , вычислить

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

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

где $\oplus$ означает XOR . Тогда зашифрованный текст $(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})$ это снова открытый текст.

На диаграмме показано как шифрование, так и дешифрование. Обратите внимание на изменение порядка подразделов для расшифровки; это единственная разница между шифрованием и дешифрованием.

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ Менезес, Альфред Дж.; Ооршот, Пол К. ван; Ванстон, Скотт А. (2001). Справочник по прикладной криптографии (Пятое изд.). Тейлор и Фрэнсис. п. 251 . ISBN 978-0849385230 .
^ Шнайер, Брюс (1996). Прикладная криптография . Нью-Йорк: Джон Уайли и сыновья. ISBN 0-471-12845-7 .
^ Стинсон, Дуглас Р. (1995). Криптография: теория и практика . Бока-Ратон: CRC Press. ISBN 0-8493-8521-0 .
^ Луби, Майкл; Ракофф, Чарльз (апрель 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 , получено 27 июля 2009 г.
^ Чжэн, Юлян; Мацумото, Цутому; Имаи, Хидеки (20 августа 1989 г.). «О построении блочных шифров, доказуемо безопасных и не полагающихся на какие-либо недоказанные гипотезы». Достижения в криптологии — CRYPTO' 89 Труды . Конспекты лекций по информатике. Том. 435. стр. 461–480. дои : 10.1007/0-387-34805-0_42 . ISBN 978-0-387-97317-3 .
^ Шнайер, Брюс; Келси, Джон (21 февраля 1996 г.). «Несбалансированные сети Фейстеля и конструкция блочного шифра». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 1039. стр. 121–144. дои : 10.1007/3-540-60865-6_49 . ISBN 978-3-540-60865-3 . Проверено 21 ноября 2017 г.
^ Боно, Стивен; Грин, Мэтью; Стабблфилд, Адам; Джулс, Ари; Рубин, Авиэль; Шидло, Майкл (5 августа 2005 г.). «Анализ безопасности RFID-устройства с криптографической поддержкой» (PDF) . Материалы симпозиума по безопасности USENIX . Проверено 21 ноября 2017 г.
^ Перейти обратно: ^а ^б Моррис, Бен; Рогауэй, Филипп; Стегерс, Тилль (2009). «Как шифровать сообщения в небольшом домене». Достижения в криптологии — КРИПТО 2009 (PDF) . Конспекты лекций по информатике. Том. 5677. стр. 286–302. дои : 10.1007/978-3-642-03356-8_17 . ISBN 978-3-642-03355-1 . Проверено 21 ноября 2017 г.

[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 Journal on Computing , 17 (2): 373–386, doi : 10.1137/0217022 , ISSN 0097-5397 .

[7-rounds-5] Патарин, Жак (октябрь 2003 г.), Боне, Дэн (редактор), Достижения в криптологии - CRYPTO 2003 (PDF) , Конспекты лекций по информатике, том. 2729, стр. 513–529, doi : 10.1007/b11817 , ISBN. 978-3-540-40674-7 , S2CID 20273458 , получено 27 июля 2009 г.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]