Jump to content

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

(Перенаправлено из структуры Фейстеля )

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

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

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

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

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

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

См. также

[ редактировать ]
  1. ^ Менезес, Альфред Дж.; Ооршот, Пол К. ван; Ванстон, Скотт А. (2001). Справочник по прикладной криптографии (Пятое изд.). Тейлор и Фрэнсис. п. 251 . ISBN  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 г.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 695ae0f76c72e514ae63cffa52f94cd4__1715740080
URL1:https://arc.ask3.ru/arc/aa/69/d4/695ae0f76c72e514ae63cffa52f94cd4.html
Заголовок, (Title) документа по адресу, URL1:
Feistel cipher - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)