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

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

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

Содержание

  • 1 История
  • 2 Дизайн
  • 3 Теоретическая работа
  • 4 Детали конструкции
    • 4.1 Несбалансированный шифр Фейстеля
    • 4.2 Другое применение
    • 4.3 Сети Фейстеля как компонент проектирования
  • 5 Список шифров Фейстеля
  • 6 См. Также
  • 7 Ссылки
  • 8 Внешние ссылки

История

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

Дизайн

Сеть Фейстеля использует функцию округления, функцию, которая принимает два входа, блок данных и подключ, и возвращает один выход того же размера, что и блок данных. В каждом раунде функция раунда запускается для половины данных, подлежащих шифрованию, и ее выходные данные подвергаются операции XOR с другой половиной данных. Это повторяется фиксированное количество раз, и конечным результатом являются зашифрованные данные. Важным преимуществом сетей Фейстеля по сравнению с другими конструкциями шифров, такими как сети замещения-перестановки, является то, что вся операция гарантированно обратима (т. Е. Зашифрованные данные могут быть расшифрованы), даже если функция округления не является сам обратимый. Функция округления может быть произвольно сложной, поскольку ее не нужно проектировать так, чтобы она была обратимой. Кроме того, операции шифрования и дешифрования очень похожи, даже идентичны в некоторых случаях, требуя только реверсирования расписания ключей. Следовательно, размер кода или схемы, необходимых для реализации такого шифра, уменьшается почти вдвое.

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

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

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

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

Детали конструкции

Схема шифра Фейстеля ru.svg

Пусть F {\ displaystyle {\ rm {F}}}{\ rm F} - функция округления, и пусть K 0, K 1,…, K n {\ displaystyle K_ {0}, K_ {1}, \ ldots, K_ {n}}K_0, K_1, \ ldots, K_ {n} быть подключами для раундов 0, 1,…, n {\ displaystyle 0,1, \ ldots, n}0,1, \ ldots, n соответственно.

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

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

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

L я + 1 знак равно р я {\ Displaystyle L_ {я + 1} = R_ {я} \,}L_ {i + 1 } = R_i \,
R я + 1 = L я ⊕ F (R я, К я). {\ Displaystyle R_ {я + 1} = L_ {i} \ oplus {\ rm {F}} (R_ {i}, K_ {i}).}{\ displaystyle R_ { i + 1} = L_ {i} \ oplus {\ rm {F}} (R_ {i}, K_ {i}).}

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

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

R i = L i + 1 {\ displaystyle R_ {i} = L_ {i + 1} \,}R_ {i} = L_ {i + 1} \,
L я знак равно р я + 1 ⊕ F ⁡ (L я + 1, К я). {\ Displaystyle L_ {i} = R_ {i + 1} \ oplus \ operatorname {F} (L_ { i + 1}, K_ {i}).}{\ displaystyle L_ {i} = R_ {i + 1} \ oplus \ operatorname {F} (L_ {i + 1}, K_ {i}).}

Тогда (L 0, R 0) {\ displaystyle (L_ {0}, R_ {0})}(L_0, R_0) i s снова открытый текст.

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

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

Несбалансированные шифры Фейстеля используют измененную структуру, где L 0 {\ displaystyle L_ {0}}L_ {0} и R 0 {\ displaystyle R_ {0}}R_ {0} не имеют одинаковой длины. Шифр Skipjack является примером такого шифра. Транспондер с цифровой подписью Texas Instruments использует собственный несбалансированный шифр Фейстеля для выполнения аутентификации запрос – ответ.

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

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

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

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

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

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

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

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

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

См. также

Ссылки

Внешние ссылки

Последняя правка сделана 2021-05-20 13:06:14
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте