Сеть Фейстеля

Материал из Википедии — свободной энциклопедии

Сеть Фе́йстеля (конструкция Фейстеля) — разновидность блочного шифра с определенной итерированной структурой. Многие современные блочные шифры используют сеть Фейстеля в качестве основы.

Содержание

1 История
2 Конструкция
3 Модификации сети Фейстеля
4 Теоретические исследования
5 Шифры на основе сети Фейстеля
6 Ссылки

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

В 1973 году Хорст Фейстель (Horst Feistel) в журнале Scientific American опубликовал статью «Cryptography and Computer Privacy», в которой раскрыл некоторые важные аспекты шифрования, а также ввел конструкцию, названную впоследствии сетью Фейстеля. Эта схема была использована в проекте Lucifer фирмы IBM, над которым работали Фейстель и Дон Копперсмит (Don Coppersmith). Этот проект был скорее экспериментальным, но стал базисом для Data Encryption Standard (DES). Итеративная структура алгоритма позволяла упростить его реализацию в аппаратных средах.

[править] Конструкция

Шифрование

Расшифрование

блок открытого текста делится на 2 равные части ( $L_0,\ R_0)$
в каждом раунде вычисляется ( $i=1\ldots n$ — номер раунда)

$L_i\ =\ R_{i-1}\oplus f(L_{i-1},K_{i-1})$
$R_i\ =\ L_{i-1}$ ,

где $f$ — некоторая функция, а $K i - 1$ — ключ $i$ -го раунда. Результатом выполнения $n$ раундов является $(L_n,\ R_n)$ . Но обычно в $n$ -ом раунде перестановка $L n$ и $R n$ не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации:

$L_{i-1}\ =\ R_{i}\oplus f(L_{i},\ K_{i-1})$
$R_{i-1}\ =\ L_i$ ,

Небольшим изменением можно добиться и полной идентичности процедур шифрования и дешифрования. Одно из преимуществ такой модели — обратимость алгоритма независимо от используемой функции $f$ , и она может быть сколь угодно сложной.

[править] Модификации сети Фейстеля

При большом размере блоков шифрования (128 бит и более) реализация такой сети Фейстеля на 32-разрядных архитектурах может вызвать затруднения, поэтому применяются модифицированные варианты этой конструкции. Обычно используются сети с 4 ветвями. На рисунки показаны наиболее распространенные модификации. Также существуют схемы, в которых длины половинок $L 0$ и $R 0$ не совпадают. Они называются несбалансированными.

Модификации сети Фейстеля
Тип 1	Тип 2	Тип 3

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

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

Следующие блочные шифры используют классическую или модифицированную сеть Фейстеля в своей основе: Blowfish, Camellia, CAST, DES, FEAL, ГОСТ 28147-89, KASUMI, LOKI97, Lucifer, MacGuffin, MARS, MAGENTA, MISTY1, RC2, RC5, RC6, Skipjack, TEA, Triple DES, Twofish, XTEA.