Сеть Фейстеля
В криптографии шифр Feistel представляет собой симметричную структуру, используемую при построении блочных шифров, названную в честь немецкого криптографа IBM Хорста Фейстела; она также широко известна как сеть Feistel. Большой набор блочных шифров использует эту схему, в том числе Стандарт шифрования данных
Преимущество структуры Feistel заключается в том, что операции шифрования и дешифрования очень похожи, даже идентичны в некоторых случаях, что требует только изменения расписания ключей. Поэтому размер кода или схемы, необходимой для реализации такого шифра, сокращается почти вдвое.
Конструкция Feistel носит итеративный характер, что облегчает реализацию криптосистемы в аппаратном обеспечении.
Сети Feistel и подобные конструкции являются шифрами продуктов, и поэтому объединяют несколько циклов повторяющихся операций, например:
- Перестановка битов (часто называемая коробками перестановки или P-боксами)
- Простые нелинейные функции (часто называемые коробками замены или S-боксами)
- Линейное смешивание (в смысле модульной алгебры) с использованием XOR для получения функции с большим количеством того, что Клод Шеннон назвал "путаницей и диффузией".
Битовое перетасовывание создает эффект диффузии, в то время как замещение используется для путаницы.
теоретическая работа
Многие современные симметричные блочные шифры используют сети Feistel, а структура и свойства шифров Feistel были тщательно исследованы криптографами. В частности, Майкл Луби и Чарльз Ракофф проанализировали конструкцию блочного шифра Feistel и доказали, что если круглая функция является криптографически безопасной псевдослучайной функцией, в которой в качестве зерна используется Ki, то 3 раунда достаточно, чтобы сделать блок-шифр псевдослучайной перестановкой, а 4 раунда достаточно, чтобы сделать его "сильной" псевдослучайной перестановкой (что означает, что он остается псевдослучайным даже для противника, который получает доступ оракула к его инверсной перестановке). Из-за этого очень важного результата Luby и Rackoff, шифры Feistel иногда называют блок-шифрами Luby-Rackoff. Дальнейшие теоретические исследования обобщили конструкцию и определили более точные пределы безопасности.
Строительство
Пусть F {\displaystyle {\rm {F}} будет круглой функцией и пусть K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots,K_{n}} будут подклавишами для раундов 1,2 , ... , n {\displaystyle 1,2,\ldots,n} соответственно.
Тогда основная операция выглядит следующим образом:
Разделите блок простого текста на две равные части ( L 1 {\displaystyle L_{1}} , R 1 {\displaystyle R_{1}}).
Для каждого раунда i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots,n} вычислять (рассчитывать)
L i + 1 = R i {\displaystyle L_{i+1}=R_{i},}
R i + 1 = L i ⊕ F ( R i , K i ) {\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}(R_{i},K_{i}}(R_{i},K_{i})} .
Затем шифрованный текст ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} . (Обычно две части R n {\displaystyle R_{n}} и L n {\displaystyle L_{n} не меняются после последнего раунда).
Расшифровка шифрованного текста ( R n , L n ) {\displaystyle (R_{n},L_{n})} выполняется вычислением для i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots,1}
R i = L i + 1 {\displaystyle R_{i}=L_{i+1},}
L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}(L_{i+1},K_{i})} .
Тогда ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} снова чистый текст.
Одним из преимуществ данной модели является то, что круглая функция F {\displaystyle {\rm {F}} не обязательно должна быть инвертируемой и может быть очень сложной.
Диаграмма иллюстрирует процесс шифрования. Для расшифровки требуется только перевернуть порядок подклавиши K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots,K_{1}} используя тот же самый процесс; в этом единственная разница между шифровкой и расшифровкой:
В несбалансированных шифрах Feistel используется модифицированная структура, в которой L 1 {\displaystyle L_{1}} и R 1 {\displaystyle R_{1}} не имеют одинаковой длины. Шифр MacGuffin является экспериментальным примером такого шифра.
Конструкция Feistel также используется в криптографических алгоритмах, отличных от блочных шифров. Например, схема Optimal Asymmetric Encryption Padding (OAEP) использует простую сеть Feistel для рандомизации шифрованных текстов в некоторых схемах шифрования с асимметричными ключами.
Сетевая операция Feistel на блочном шифре, где P - чистый текст, а C - шифрованный текст.
Список шифров Feistel
Feistel или модифицированный Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, ГОСТ 28147-89
Вопросы и ответы
В: Что такое шифр Фейстеля?
О: Шифр Фейстеля - это симметричная структура, используемая при построении блочных шифров, названная в честь немецкого криптографа Хорста Фейстеля из IBM. Он также широко известен как сеть Фейстеля.
В: Каковы некоторые преимущества использования структуры Фейстеля?
О: Основное преимущество использования структуры Фейстеля заключается в том, что операции шифрования и дешифрования очень похожи, в некоторых случаях даже идентичны, требуя только изменения расписания ключей. Это уменьшает размер кода или схемы, необходимой для реализации такого шифра, почти наполовину. Кроме того, итеративная природа шифра упрощает реализацию криптосистемы в аппаратном обеспечении.
В: Как Клод Шеннон описал "путаницу и распространение"?
О: Клод Шеннон описал "путаницу и диффузию" как наличие большого количества обоих элементов для того, чтобы злоумышленнику было трудно расшифровать зашифрованное сообщение.
В: Какие техники используются для создания путаницы и диффузии?
О: Замешательство и диффузия создаются с помощью перестановки битов (часто называемых ящиками перестановки или P-ящиками) и простых нелинейных функций (часто называемых ящиками подстановки или S-ящиками), а также линейного смешивания (в смысле модульной алгебры) с помощью XOR. Перестановка битов создает эффект диффузии, а подстановка используется для запутывания.
В: Каким типом шифра является сеть Фейстеля?
О: Сеть Фейстеля - это тип продукционного шифра, который объединяет несколько раундов повторяющихся операций для надежного шифрования данных.
В: Кто разработал этот тип шифрования?
О: Структура Фейстеля была разработана немецким криптографом Хорстом Фейстелем из IBM.
В: Основан ли Data Encryption Standard на этом типе криптографии?
О: Да, Data Encryption Standard использует этот тип криптографии, который использует те же принципы, описанные выше, для создания путаницы и диффузии внутри зашифрованного сообщения.