Из Википедии, бесплатной энциклопедии
  (Перенаправлено из сети Feistel )
Перейти к навигации Перейти к поиску

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

История [ править ]

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

Дизайн [ править ]

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

Теоретическая работа [ править ]

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

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

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

Детали строительства [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сети Фейстеля как компонент дизайна [ править ]

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

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

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

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

  • CAST-256
  • КЛЕФИЯ
  • Макгаффин
  • RC2
  • RC6
  • Скипджек
  • SMS4

См. Также [ править ]

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

Ссылки [ править ]

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