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

Сеть Фе́йстеля, или конструкция Фейстеля (Шаблон:Lang-en), — один из методов построения блочных шифров. Сеть состоит из ячеек, называемых ячейками Фейстеля. На вход каждой ячейки поступают данные и ключ. На выходе каждой ячейки получают изменённые данные и изменённый ключ. Все ячейки однотипны, и говорят, что сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру. Ключ выбирается в зависимости от алгоритма шифрования/расшифрования и меняется при переходе от одной ячейки к другой. При шифровании и расшифровании выполняются одни и те же операции; отличается только порядок ключей. Ввиду простоты операций сеть Фейстеля легко реализовать как программно, так и аппаратно. Ряд блочных шифров (DES, RC2, RC5, RC6, Blowfish, FEAL, CAST-128, TEA, XTEA, XXTEA и др.) использует сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть (AES и др.).

История

В 1971 году Хорст Фейстель запатентовал два устройства, реализующих различные алгоритмы шифрования, позже получившие название «Люцифер» (Шаблон:Lang-en). Одно из этих устройств использовало конструкцию, впоследствии названную «сетью Фейстеля» (Шаблон:Lang-en, Шаблон:Lang-en2). Тогда Фейстель работал над созданием новых криптосистем в стенах IBM вместе с Доном Копперсмитом. Проект «Люцифер» был скорее экспериментальным, но стал основой для алгоритма DES (Шаблон:Lang-en). В 1973 году журнал «Scientific American» опубликовал статью Фейстеля «Криптография и компьютерная безопасность» (Шаблон:Lang-en)^[1], в которой раскрыты некоторые важные аспекты шифрования и приведено описание первой версии проекта «Люцифер». В первой версии проекта «Люцифер» сеть Фейстеля не использовалась.

На основе сети Фейстеля был спроектирован алгоритм DES. В 1977 году власти США приняли стандарт Шаблон:Nobr, признающий DES стандартным методом шифрования данных. DES некоторое время широко использовался в криптографических системах. Итеративная структура алгоритма позволяла создавать простые программные и аппаратные реализации.

Согласно некоторым данным^[2], в СССР уже в 1970-е годы КГБ разрабатывала блочный шифр, использовавший сеть Фейстеля, и, вероятно, именно этот шифр в 1990 году был принят в качестве ГОСТ 28147-89.

В 1987 году были разработаны алгоритмы FEAL и RC2. Сети Фейстеля получили широкое распространение в 1990-е годы — в годы появления таких алгоритмов, как Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) и других.

2 января 1997 года институт NIST объявил конкурс по созданию нового алгоритма шифрования данных, призванного заменить DES. Новый блочный шифр получил название AES (Шаблон:Lang-en) и был утверждён 26 мая 2002 года. В AES вместо сети Фейстеля используется подстановочно-перестановочная сеть.

Конструкция блочного шифра на основе сетей Фейстеля

Простое описание

Шифрование

Пусть требуется зашифровать некоторую информацию, представленную в двоичном виде (в виде последовательности нулей и единиц) и находящуюся в памяти компьютера или иного устройства (например, в файле).

Алгоритм шифрования.

Информация разбивается на блоки одинаковой (фиксированной) длины. Полученные блоки называются входными, так как поступают на вход алгоритма. В случае, если длина входного блока меньше, чем размер, который выбранный алгоритм шифрования способен зашифровать единовременно (размер блока), блок удлиняется каким-либо способом. Как правило, длина блока является степенью двойки, например, составляет 64 бита или 128 бит.

Далее будем рассматривать операции, происходящие только с одним блоком, так как в процессе шифрования с другими блоками выполняются те же самые операции.

Выбранный блок делится на два подблока одинакового размера — «левый» ( $L_{0}$ ) и «правый» ( $R_{0}$ ).
«Правый подблок» $R_{0}$ изменяется функцией F с использованием раундового ключа $K_{0}$ :

x = F (R_{0}, K_{0}) .

Результат складывается по модулю 2 («xor») с «левым подблоком» $L_{0}$ :

x = x \oplus L_{0} .

Результат будет использован в следующем раунде в роли «правого подблока» $R_{1}$ :

R_{1} = x .

«Правый подблок» $R_{0}$ текущего раунда (в своем не измененном на момент начала раунда виде) будет использован в следующем раунде в роли «левого подблока» $L_{1}$ :

L_{1} = R_{0} .

По какому-либо математическому правилу вычисляется раундовый ключ $K_{1}$ — ключ, который будет использоваться в следующем раунде.

Перечисленные операции выполняются N-1 раз, где N — количество раундов в выбранном алгоритме шифрования. При этом между переходами от одного раунда (этапа) к другому изменяются ключи: $K_{0}$ заменяется на $K_{1}$ , $K_{1}$ — на $K_{2}$ и т. д.).

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

Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке, то есть не от первого к N-му, а от N-го к первому.

Алгоритмическое описание

Блок открытого текста делится на две равные части: $(L_{0}, R_{0})$ .
В каждом раунде вычисляются:

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

R_{i} = L_{i - 1},

где:

i — номер раунда; $i = 1 \dots N;$
N — количество раундов в выбранном алгоритме шифрования;
$f$ — некоторая функция;
$K_{i - 1}$ — ключ i-1-го раунда (раундовый ключ).

Результатом выполнения $N$ раундов является $(L_{N}, R_{N})$ . В N-м раунде перестановка $L_{N}$ и $R_{N}$ не производится, чтобы была возможность использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования ключей ( $K_{N}, K_{N - 1}, \dots, K_{0}$ вместо $K_{0}, K_{1}, \dots, K_{N}$ ):

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

R_{i - 1} = L_{i} .

Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования.

Достоинства:

обратимость алгоритма независимо от используемой функции f;
возможность выбора сколь угодно сложной функции f.

Математическое описание

Рассмотрим пример. Пусть:

X — блок данных, поступающий на вход (входной блок);
A — некоторое инволютивное преобразование (или инволюция) — взаимно-однозначное преобразование, которое является обратным самому себе^[3], то есть [[Квантор всеобщности|для каждого Шаблон:Symbol]] X справедливо выражение:

A A X = A^{2} X = X, \forall X;

Y — блок данных, получаемый на выходе (результат).

При однократном применении преобразования A к входному блоку X получится выходной блок Y:

Y = A X .

При применении преобразования A к результату предыдущего преобразования — Y получится:

A Y = A A X = X, \forall X .

Пусть входной блок X состоит из двух подблоков L и R равной длины:

X = (L, R) .

Определим два преобразования:

$G (X, K)$ — шифрование данных X с ключом K:

G (X, K) = G ((L, R), K) = (L \oplus F (K, R), R);

$T (L, R)$ — перестановка подблоков L и R:

T (L, R) = (R, L) .

Введём обозначения:

однократное применение преобразования G:

\tilde{X} = (\tilde{L}, \tilde{R}) = G X;

двукратное применение преобразования G:

\tilde{\tilde{X}} = (\tilde{\tilde{L}}, \tilde{\tilde{R}}) = G^{2} X .

Докажем инволютивность двукратного преобразования G ( $G^{2}$ ).

Несложно заметить, что преобразование G меняет только левый подблок L, оставляя правый R неизменным:

\tilde{L} = L \oplus F (K, R);

\tilde{R} = R .

Поэтому далее будем рассматривать только подблок L. После двукратного применения преобразования G к L получим:

\tilde{\tilde{L}} = \tilde{L} \oplus F (K, \tilde{R}) = \tilde{L} \oplus F (K, R) = L \oplus F (K, R) \oplus F (K, R) = L .

Таким образом:

G^{2} L = L;

G^{2} R = R,

следовательно

G^{2} X = X

и G — инволюция.

Докажем инволютивность двукратного преобразования T ( $T^{2}$ ).

T^{2} X = T^{2} (L, R) = T (R, L) = (L, R) = X .

Рассмотрим процесс шифрования. Пусть:

X — входное значение;
$G_{i}$ — преобразование с ключом $K_{i}$ ;
$Y_{i}$ — выходное значение, результат i-го раунда.

Тогда преобразование, выполняемое на i+1-м раунде, можно записать в виде:

Y_{i + 1} = T G_{i} Y_{i}

.

Преобразование, выполняемое на 1-м раунде:

Y_{1} = T G_{1} X .

Следовательно, выходное значение после m раундов шифрования будет равно:

Y_{m} = T G_{m} Y_{m - 1} = T G_{m} T G_{m - 1} \dots T G_{1} X .

Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.

Расшифрование ведётся применением всех преобразований в обратном порядке. В силу инволютивности каждого из преобразований обратный порядок даёт исходный результат:

X = G_{1} T G_{2} T \dots G_{m - 1} T G_{m} T (Y_{m}) = G_{1} T G_{2} T \dots G_{m - 1} T (Y_{m - 1}) = \dots = G_{1} T (Y_{1}) = X .

Функции, используемые в сетях Фейстеля

В своей работе «Криптография и компьютерная безопасность»^[1] Хорст Фейстель описывает два блока преобразований (функций $f (L_{i}, K_{i})$ ):

блок подстановок (s-блок, Шаблон:Lang-en);
блок перестановок (p-блок, Шаблон:Lang-en).

Можно показать, что любое двоичное преобразование над блоком данных фиксированной длины может быть реализовано в виде s-блока. В силу сложности строения N-разрядного s-блока при больших N на практике применяют более простые конструкции.

Термин «блок» в оригинальной статье^[1] используется вместо термина «функция» вследствие того, что речь идёт о блочном шифре и предполагалось, что s- и p-блоки будут цифровыми микросхемами (цифровыми блоками).

Файл:S-block.svg

Принципиальная схема 3-разрядного s-блока

Файл:Feistel Network P-Block.png

Принципиальная схема 8-разрядного p-блока

S-блок

Шаблон:Main Блок подстановок (s-блок, Шаблон:Lang-en) состоит из следующих частей:

дешифратор — преобразователь n-разрядного двоичного сигнала в одноразрядный сигнал по основанию $2^{n}$ ;
система коммутаторов — внутренние соединения (всего возможных соединений $2^{n}!$ );
шифратор — преобразователь сигнала из одноразрядного $2^{n}$ -ричного в n-разрядный двоичный.

Анализ n-разрядного S-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений крайне велико ( $2^{n}$ ). На практике блок подстановок используется как часть более сложных систем.

В общем случае s-блок может иметь несовпадающее число входов/выходов, в этом случае в системе коммутации от каждого выхода дешифратора может идти не строго одно соединение, а 2 или более или не идти вовсе. То же самое справедливо и для входов шифратора.

В электронике можно непосредственно применять приведённую справа схему. В программировании же генерируют таблицы замены. Оба этих подхода являются эквивалентными, то есть файл, зашифрованный на компьютере, можно расшифровать на электронном устройстве и наоборот.

Таблица замены для приведённого 3-разрядного s-блока
№ комбинации	0	1	2	3	4	5	6	7
Вход	000	001	010	011	100	101	110	111
Выход	011	000	001	100	110	111	010	101

P-блок

Блок перестановок (p-блок, Шаблон:Lang-en) всего лишь изменяет положение цифр и является линейным устройством. Этот блок может иметь очень большое количество входов-выходов, однако в силу линейности систему нельзя считать криптоустойчивой.

Криптоанализ ключа для n-разрядного p-блока проводится путём подачи на вход n-1 различных сообщений, каждое из которых состоит из n-1 нуля («0») и 1 единицы («1») (или наоборот, из единиц и нуля).

Циклический сдвиг

Шаблон:Main

Можно показать, что циклический сдвиг является частным случаем p-блока.

В простейшем случае (сдвиг на 1 бит), крайний бит отщепляется и перемещается на другой конец регистра или шины. В зависимости от того какой бит берётся, правый или левый, сдвиг называется вправо или влево. Сдвиги на большее число бит можно рассматривать, как многократное применение сдвига на 1.

Циклический сдвиг на m бит для n-разрядного входа (m < n)
Направление сдвига	Порядок следования битов до сдвига	Порядок следования битов после сдвига
Влево	$b_{0}, b_{1}, b_{2}, . . ., b_{n - 1}$	$b_{m}, b_{m + 1}, . . . b_{n - 1}, b_{0}, b_{1}, . . ., b_{m - 1}$
Вправо	$b_{0}, b_{1}, b_{2}, . . ., b_{n - 1}$	$b_{n - m}, b_{n - m + 1}, . . . b_{n - 1}, b_{0}, b_{1}, . . ., b_{n - m - 1}$

Сложение по модулю n

Шаблон:Main

Операция «сложение по модулю n» обозначается как

(A + B) mod n

и представляет собой остаток от деления суммы Шаблон:Nobr на n, где A и B — числа.

Можно показать, что сложение двух чисел по модулю n представляется в двоичной системе счисления в виде s-блока, у которого на вход подаётся число A, а в качестве системы коммутации s-блока используется циклический сдвиг влево на B разрядов.

В компьютерной технике и электронике операция сложения, как правило, реализована как сложение по модулю $n = 2^{m}$ , где m — целое (обычно m равно разрядности машины). Для получения в двоичной системе

A + B mod

2^{m}

достаточно сложить числа, после чего отбросить разряды начиная с m-го и старше.

Умножение по модулю n

Умножение по модулю n обозначается как

(A * B) mod n

и представляет собой остаток от деления произведения Шаблон:Nobr на n, где A и B — числа.

В персональных компьютерах на платформе x86 при перемножении двух m-разрядных чисел получается число разрядностью 2*m. Чтобы получить остаток от деления на $2^{m}$ , нужно отбросить m старших бит.

Пример реализации на языке Си

Общий вид алгоритма шифрования, использующего сеть Фейстеля:

/* Функция, выполняющая преобразование подблока с учётом значения ключа (по ключу). 
Реализация зависит от выбранного алгоритма блочного шифрования. */
int f (
        int subblock,  /* преобразуемый подблок */
        int key        /* ключ */
);  /* возвращаемое значение - преобразованный блок */

/* Функция, выполняющая шифрование открытого текста */
void crypt (
        int * left,   /* левый входной подблок */
        int * right,  /* правый входной подблок */
        int rounds,   /* количество раундов */
        int * key     /* массив ключей (по ключу на раунд) */
) {
    int i, temp;
    for ( i = 0; i < rounds; i++ )
    {
        temp = *right ^ f( *left, key[i] );
        *right = *left;
        *left = temp;
    }
}

/* Функция, выполняющая расшифрование текста */
void decrypt (
        int * left,   /* левый зашифрованный подблок */
        int * right,  /* правый зашифрованный подблок */
        int rounds,   /* количество раундов */
        int * key     /* массив ключей (по ключу на раунд) */
) {
    int i, temp;
    for ( i = rounds - 1; i >= 0; i-- )
    {
        temp = *left ^ f( *right, key[i] );
        *left = *right;
        *right = temp;
    }
}

Достоинства и недостатки

Достоинства:

простота аппаратной реализации на современной электронной базе;
простота программной реализации в силу того, что значительная часть функций поддерживается на аппаратном уровне в современных компьютерах (например, сложение по модулю 2 («xor»), сложение по модулю $2^{n}$ , умножение по модулю $2^{n}$ , и т. д.);
хорошая изученность алгоритмов, построенных на основе сетей Фейстеля^[4].

Недостатки:

за один раунд шифруется только половина входного блокаШаблон:Sfn.

Теоретические исследования

Сети Фейстеля были широко изучены криптографами в силу их обширного распространения. В 1988 году Шаблон:Iw и Шаблон:Iw провели исследования сети Фейстеля и доказали, что если раундовая функция является криптостойкой псевдослучайной, а используемые ключи независимы в каждом раунде, то 3 раундов будет достаточно для того, чтобы блочный шифр являлся псевдослучайной перестановкой, тогда как четырёх раундов будет достаточно для того, чтобы сделать сильную псевдослучайную перестановку.

«Псевдослучайной перестановкой» Люби и Ракофф назвали такую, которая устойчива к атаке с адаптивным выбором открытого текста, а «сильной псевдослучайной перестановкой» — псевдослучайную перестановку, устойчивую к атаке с использованием выбранного шифрованного текста.

Иногда в западной литературе сеть Фейстеля называют «Luby-Rackoff block cipher» в честь Люби и Ракоффа, которые проделали большой объём теоретических исследований в этой области.

В дальнейшем, в 1997 году Шаблон:Iw и Шаблон:Iw предложили упрощённый вариант конструкции Люби — Ракоффа, состоящий из четырёх раундов. В этом варианте в качестве первого и последнего раунда используются две попарно-независимые перестановки. Два средних раунда конструкции Наора — Рейнголда идентичны раундам в конструкции Люби — Ракоффа^[5].

Большинство же исследований посвящено изучению конкретных алгоритмов. Во многих блочных шифрах на основе сети Фейстеля были найдены те или иные уязвимости, однако в ряде случаев эти уязвимости являются чисто теоретическими и при нынешней производительности компьютеров использовать их на практике для взлома невозможно.

Модификации сети Фейстеля

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

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

Алгоритм IDEA

Шаблон:Main

Источник Шаблон:Sfn:

Схема одной итерации полного раунда алгоритма IDEA

В алгоритме IDEA используется глубоко модифицированная сеть Фейстеля. В нём 64-битные входные блоки данных (обозначим за $X_{0}$ ) делятся на 4 подблока длиной 16 бит $X_{0} = {X^{(0)} X^{(1)} X^{(2)} X^{(3)}}$ . На каждом этапе используется 6 16-битных ключей. Всего используется 8 основных этапов и 1 укороченный.

Формулы для вычисления значения подблоков на i-м раунде (для раундов c 1-го по 8-й):

предварительные вычисления:

A_{i} = ((X_{i - 1}^{(0)} * K_{i}^{(1)}) \oplus (X_{i - 1}^{(2)} + K_{i}^{(3)})) * K_{i}^{(5)};

B_{i} = (((X_{i - 1}^{(1)} + K_{i}^{(2)}) \oplus (X_{i - 1}^{(3)} * K_{i}^{(4)}) + A_{i}) * K_{i}^{(6)});

C_{i} = ((X_{i - 1}^{(1)} + K_{i}^{(2)}) \oplus (X_{i - 1}^{(3)} * K_{i}^{(4)}) + ((X_{i - 1}^{(0)} * K_{i}^{(1)}) \oplus (X_{i - 1}^{(2)} + K_{i}^{(3)})) * K_{i}^{(5)}) * K_{i}^{(6)};

финальные вычисления:

X_{i}^{(0)} = (X_{i - 1}^{(0)} * K_{i}^{(1)}) \oplus B_{i};

X_{i}^{(1)} = (X_{i - 1}^{(2)} + K_{i}^{(3)}) \oplus B_{i};

X_{i}^{(2)} = (X_{i - 1}^{(1)} + K_{i}^{(2)}) \oplus (A_{i} + C_{i});

X_{i}^{(3)} = (X_{i - 1}^{(3)} * K_{i}^{(4)}) \oplus (A_{i} + C_{i}),

где $K_{i}^{(j)}$ — j-й ключ на i-м раунде.

Формула для вычисления 9-го раунда:

X_{9}^{(0)} = X_{8}^{(0)} * K_{9}^{(1)};

X_{9}^{(1)} = X_{8}^{(2)} + K_{9}^{(2)};

X_{9}^{(2)} = X_{8}^{(1)} + K_{9}^{(3)};

X_{9}^{(3)} = X_{8}^{(3)} * K_{9}^{(4)} .

Выходом функции будет

Y = {X_{9}^{(0)} X_{9}^{(1)} X_{9}^{(2)} X_{9}^{(3)}} .

Можно заметить, что s- и p-блоки в чистом виде не используются. В качестве основных операций используются:

умножение по модулю $2^{16} + 1 = 65537$ ;
сложение по модулю $2^{16} = 65536$ .

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

Люцифер (Lucifer)

Шаблон:Main

Файл:S-chooser.png

Модуль, выбирающий используемую таблицу подстановок по битовому ключу

Файл:Lucifer v1.png

Упрощённая схема s- и p-слоёв в алгоритме «Люцифер» (июнь 1971)

Файл:Ones Propagation.png

Схема генерации и распространения единиц

Исторически первым алгоритмом, использующим сеть Фейстеля, был алгоритм «Люцифер», при работе над которым Фейстелем и была, собственно, разработана структура, впоследствии получившая название «сеть Фейстеля». В июне 1971 года Фейстелем был получен американский патент № 3798359^[6].

Первая версия «Люцифера» использовала блоки и ключи длиной по 48 бит и не использовала конструкцию «сеть Фейстеля». Последующая модификация алгоритма была запатентована на имя Джона Л. Смитта (Шаблон:Lang-en) в ноябре 1971 года (US Patent 3,796,830; Nov 1971)^[7], и в патенте содержится как описание собственно самой «сети Фейстеля», так и конкретной функции шифрования. В ней использовались 64-разрядные ключи и 32-битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-битными блоками и ключами. Наиболее полное описание алгоритма «Люцифер» было приведено в статье Артура Соркина (Шаблон:Lang-en) «Люцифер. Криптографический алгоритм» («Lucifer, A Cryptographic Algorithm») в журнале «Криптология» («Cryptologia») за январь 1984^[8].

Хотя изначальная модификация «Люцифера» обходилась без «ячеек Фейстеля», она хорошо демонстрирует то, как только применением s- и p-блоков можно сильно исказить исходный текст. Структура алгоритма «Люцифер» образца июня 1971 года представляет собой «сэндвич» из слоёв двух типов, используемых по очереди — так называемые SP-сети (или подстановочно-перестановочные сети). Первый тип слоя — p-блок разрядности 128 бит, за ним идёт второй слой, представляющий собой 32 модуля, каждый из которых состоит их двух четырёхбитных s-блоков, чьи соответствующие входы закорочены и на них подаётся одно и то же значение с выхода предыдущего слоя. Но сами блоки подстановок различны (отличаются таблицами замен). На выход модуля подаются значения только с одного из s-блоков, какого конкретно — определяется одним из битов в ключе, номер которого соответствовал номеру s-блока в структуре. Упрощённая схема алгоритма меньшей разрядности и неполным числом раундов приведена на рисунке. В ней используется 16 модулей выбора s-блоков (всего 32 s-блока), таким образом такая схема использует 16-битный ключ.

Рассмотрим теперь, как будет меняться шифротекст, в приведённом выше алгоритме, при изменении всего одного бита. Для простоты возьмём таблицы замен s-блоков такими, что если на вход s-блока подаются все нули, то и на выходе будут все нули. В силу нашего выбора s-блоков, если на вход шифрующего устройства подаются все нули, то и на выходе устройства будут все нули. В реальных системах такие таблицы замен не используются, так как они сильно упрощают работу криптоаналитика, но в нашем примере они наглядно иллюстрируют сильную межсимвольную взаимосвязь при изменении одного бита шифруемого сообщения. Видно, что благодаря первому p-блоку единственная единица сдвигается перемещается в центр блока, затем следующий нелинейный s-блок «размножает» её, и уже две единицы за счёт следующего p-блока изменяют своё положение и т. д. В конце устройства шифрования, благодаря сильной межсимвольной связи, выходные биты стали сложной функцией от входных и от используемого ключа. В среднем на выходе половина бит будет равна «0» и половина — «1».

По своей сути сеть Фейстеля является альтернативой сложным SP-сетям и используется намного шире. С теоретической точки зрения раундовая функция шифрования может быть сведена к SP-сети, однако сеть Фейстеля является более практичной, так как шифрование и дешифрование может вестись одним и тем же устройством, но с обратным порядком используемых ключей. Вторая и третья версия алгоритма (использующие сеть Фейстеля) оперировали над 32-битными блоками с 64-битным ключом и 128-битными блоками со 128-битными ключами. В последней (третьей) версии раундовая функция шифрования была устроена очень просто — сначала шифруемый подблок пропускался через слой 4-битных s-блоков (аналогично слоям в SP-сетях, только s-блок является константным и не зависит от ключа), затем к нему по модулю 2 добавлялся раундовый ключ, после чего результат пропускался через p-блок.

DES

Шаблон:Main

Функция $f (L_{i}, K_{i})$ (где:

$L_{i}$ — 32-разрядный входной блок на i-й итерации;
$K_{i}$ — 48-разрядный ключ на данной итерации)

в алгоритме DES состоит из следующих операций:

расширение входного блока L до 48 разрядов (некоторые входные разряды могут повторяться);
Сложение по модулю 2 с ключом $K_{i}$ :

\tilde{L_{i}} = L_{i} \oplus K_{i};

деление результата на 8 блоков длиной по 6 бит каждый:

\tilde{L_{i}} = {{\tilde{L_{i}}}^{(0)} {\tilde{L_{i}}}^{(1)} {\tilde{L_{i}}}^{(2)} {\tilde{L_{i}}}^{(3)} {\tilde{L_{i}}}^{(4)} {\tilde{L_{i}}}^{(5)} {\tilde{L_{i}}}^{(6)} {\tilde{L_{i}}}^{(7)}};

полученные блоки информации $\tilde{L_{i}^{(j)}}$ подаются на блоки подстановок, имеющие 6-разрядные входы и 4-разрядные выходы;
на выходе 4-битные блоки объединяются в 32-битный, который и является результатом функции $f (L_{i}, K_{i})$ .

Полное число раундов в алгоритме DES равно 16.

«Магма»

Шаблон:Main

Функция $f (L_{i}, K_{i})$ (где $L_{i}$ и $K_{i}$ — 32-битные числа) вычисляется следующим образом:

складываются $L_{i}$ и $K_{i}$ по модулю $2^{32}$ :

\tilde{L_{i}} = (L_{i} + K_{i}) mod 2^{32};

результат разбивается на 8 4-битных блоков, которые подаются на вход 4-разрядных s-блоков (которые могут быть различными);
выходы s-блоков объединяют в 32-битное число, которое затем сдвигается циклически на 11 битов влево;
полученный результат является выходом функции.

Количество раундов в алгоритме ГОСТ 28147—89 равно 32.

Сравнительный список алгоритмов

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

Алгоритм	Год	Число раундов	Длина ключа	Размер блока	Количество подблоков
Blowfish	1993	16	от 32 до 448	64	2
Camellia	2000	18/24	128/192/256	128	2
CAST-128	1996	12/16	40-128	64	2
CAST-256	1998	12×4=48	128/192/256	128	2
CIPHERUNICORN-A	2000	16	128/192/256	128	2
CIPHERUNICORN-E	1998	16	128	64	2
CLEFIA	2007	16	128/192/256	128	16
DEAL	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	8	128/192/256	128	?
FEAL	1987	4-32	64	64	2
ГОСТ 28147-89	1989^[2]	32/16	256	64	2
IDEA	1991	8+1	128	64	4
KASUMI	1999	8	128	64	2
Khufu	1990	16-32/64	512	64	2
LOKI97	1997	16	128/192/256	128	2
Lucifer	1971	16	48/64/128	48/32/128	2
MacGuffin	1994	32	128	64	4
MAGENTA	1998	6/8	128/192/256	128	2
MARS	1998	32	128—1248	128	2
Mercy	2000	6	128	4096	?
MISTY1	1995	4×n(8)	128	64	4
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	4
RC5	1994	1-255(12)	0-2040(128)	32/64/128	2
RC6	1998	20	128/192/256	128	4
RTEA	2007	48/64	128/256	64	2
SEED	1998	16	128	128	2
Sinople	2003	64	128	128	4
Skipjack	1998	32	80	64	4
TEA	1994	64	128	64	2
Triple DES	1978	32/48	112/168	64	2
Twofish	1998	16	128/192/256	128	4
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	4
XXTEA	1998	12-64	128	64	2

Примечания

Шаблон:Примечания

Литература

Шаблон:^ Шаблон:Симметричные криптоалгоритмы Шаблон:Хорошая статья

↑ ^1,0 ^1,1 ^1,2 Хорст Фейстель «Cryptography and computer privacy»Шаблон:Ref-en («Криптография и компьютерная безопасность»). Перевод Шаблон:Wayback Андрея Винокурова.
↑ ^2,0 ^2,1 Винокуров А. Статья Шаблон:Wayback «Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86». Часть материалов, вошедших в данную статью, была опубликована в выпуске «#1,5/1995 год» журнала «Монитор».
↑ Шаблон:Cite web
↑ Сергей Панасенко. «Современные алгоритмы шифрования Шаблон:Wayback» // Журнал «Byte». Выпуск № 8 (60), август 2003.
↑ On the construction of pseudo-random permutation: Luby-Rackoff revisited.
↑ Шаблон:US patent
↑ Шаблон:US patent
↑ Arthur Sorkin. Lucifer, A Cryptographic Algorithm. Cryptologia, Выпуск 8(1), Январь 1984, стр. 22—41, с дополнением в выпуске 8(3), стр. 260—261

[cacp-1] 1,0 ^1,1 ^1,2 Хорст Фейстель «Cryptography and computer privacy»Шаблон:Ref-en («Криптография и компьютерная безопасность»). Перевод Шаблон:Wayback Андрея Винокурова.

[gost-2] 2,0 ^2,1 Винокуров А. Статья Шаблон:Wayback «Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86». Часть материалов, вошедших в данную статью, была опубликована в выпуске «#1,5/1995 год» журнала «Монитор».

[3] Шаблон:Cite web

[4] Сергей Панасенко. «Современные алгоритмы шифрования Шаблон:Wayback» // Журнал «Byte». Выпуск № 8 (60), август 2003.

[5] On the construction of pseudo-random permutation: Luby-Rackoff revisited.

[6] Шаблон:US patent

[7] Шаблон:US patent

[8] Arthur Sorkin. Lucifer, A Cryptographic Algorithm. Cryptologia, Выпуск 8(1), Январь 1984, стр. 22—41, с дополнением в выпуске 8(3), стр. 260—261

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

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

Содержание

История

Конструкция блочного шифра на основе сетей Фейстеля

Простое описание

Шифрование

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

Алгоритмическое описание

Математическое описание

Функции, используемые в сетях Фейстеля

S-блок

P-блок

Циклический сдвиг

Сложение по модулю n

Умножение по модулю n

Пример реализации на языке Си

Достоинства и недостатки

Теоретические исследования

Модификации сети Фейстеля

Алгоритм IDEA

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

Люцифер (Lucifer)

DES

«Магма»

Сравнительный список алгоритмов

Примечания

Литература

Навигация

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

История

Конструкция блочного шифра на основе сетей Фейстеля

Простое описание

Шифрование

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

Алгоритмическое описание

Математическое описание

Функции, используемые в сетях Фейстеля

S-блок

P-блок

Циклический сдвиг

Сложение по модулю n

Умножение по модулю n

Пример реализации на языке Си

Достоинства и недостатки

Теоретические исследования

Модификации сети Фейстеля

Алгоритм IDEA

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

Люцифер (Lucifer)

DES

«Магма»

Сравнительный список алгоритмов

Примечания

Литература

Навигация

Поиск