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

Криптографическое построение

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

История

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

Дизайн

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

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

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

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

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

Детали строительства

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

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

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

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

${\displaystyle L_{i+1}=R_{i},}$

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

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

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

${\displaystyle R_{i}=L_{i+1},}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• КАСТ-256
• КЛЕФИЯ
• МакГаффин
• RC2
• RC6
• Скипджек
• СМС4

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

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

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

1. Менезес, Альфред Дж.; Ооршот, Пол К. ван; Ванстон, Скотт А. (2001). Справочник по прикладной криптографии (Пятое изд.). Тейлор и Фрэнсис. п. 251. ИСБН 978-0849385230.
2. Шнайер, Брюс (1996). Прикладная криптография . Нью-Йорк: Джон Уайли и сыновья. ISBN 0-471-12845-7.
3. Стинсон, Дуглас Р. (1995). Криптография: теория и практика . Бока-Ратон: CRC Press. ISBN 0-8493-8521-0.
4. Луби, Майкл; Ракофф, Чарльз (апрель 1988 г.), «Как построить псевдослучайные перестановки из псевдослучайных функций», SIAM Journal on Computing , 17 (2): 373–386, doi : 10.1137/0217022, ISSN  0097-5397.
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 г.
8. Боно, Стивен; Грин, Мэтью; Стабблфилд, Адам; Джулс, Ари; Рубин, Авиэль; Шидло, Майкл (5 августа 2005 г.). «Анализ безопасности RFID-устройства с криптографической поддержкой» (PDF) . Материалы симпозиума по безопасности USENIX . Проверено 21 ноября 2017 г.
9. Моррис, Бен; Рогауэй, Филипп; Стегерс, Тилль (2009). «Как шифровать сообщения в небольшом домене». Достижения в криптологии — КРИПТО 2009 (PDF) . Конспекты лекций по информатике. Том. 5677. стр. 286–302. дои : 10.1007/978-3-642-03356-8_17. ISBN 978-3-642-03355-1. Проверено 21 ноября 2017 г.