Сеть Фейстеля — Википедия

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

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

В 1971 году Хорст Фейстель запатентовал два устройства, реализующие различные алгоритмы шифрования, позже получившие название «Люцифер» (англ. Lucifer). Одно из этих устройств использовало конструкцию, впоследствии названную «сетью Фейстеля» (англ. Feistel cipher, Feistel network). Тогда Фейстель работал над созданием новых криптосистем в стенах IBM вместе с Доном Копперсмитом. Проект «Люцифер» был скорее экспериментальным, но стал основой для алгоритма DES (англ. data encryption standard). В 1973 году журнал «Scientific American» опубликовал статью Фейстеля «Криптография и компьютерная безопасность» (англ. Cryptography and computer privacy)^[1], в которой раскрыты некоторые важные аспекты шифрования и приведено описание первой версии проекта «Люцифер». В первой версии проекта «Люцифер» сеть Фейстеля не использовалась.

На основе сети Фейстеля был спроектирован алгоритм DES. В 1977 году власти США приняли стандарт FIPS 46-3, признающий 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 (англ. advanced encryption standard) и был утверждён 26 мая 2002 года. В AES вместо сети Фейстеля используется подстановочно-перестановочная сеть.

Конструкция блочного шифра на основе сетей Фейстеля[править | править код]

Простое описание[править | править код]

Шифрование[править | править код]

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

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

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

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

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

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

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

${\displaystyle x=x\oplus L_{0}.}$

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

${\displaystyle R_{1}=x.}$

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

${\displaystyle L_{1}=R_{0}.}$

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

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

Расшифрование[править | править код]

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

Алгоритмическое описание[править | править код]

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

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

${\displaystyle R_{i}\ =\ L_{i-1},}$

где:

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

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

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

${\displaystyle R_{i-1}\ =\ L_{i}.}$

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

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

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

Математическое описание[править | править код]

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

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

${\displaystyle AAX=A^{2}X=X,\forall X;}$

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

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

${\displaystyle Y=AX.}$

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

${\displaystyle AY=AAX=X,\forall X.}$

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

${\displaystyle X=(L,R).}$

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

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

${\displaystyle G(X,K)=G((L,R),K)=(L\oplus F(K,R),R);}$

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

${\displaystyle T(L,R)=(R,L).}$

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

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

${\displaystyle {\tilde {X}}=({\tilde {L}},{\tilde {R}})=GX;}$

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

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

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

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

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

${\displaystyle {\tilde {R}}=R.}$

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

${\displaystyle {\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.}$

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

${\displaystyle G^{2}L=L;}$

${\displaystyle G^{2}R=R,}$

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

${\displaystyle G^{2}X=X}$

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

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

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

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

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

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

${\displaystyle Y_{i+1}=TG_{i}Y_{i}}$.

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

${\displaystyle Y_{1}=TG_{1}X.}$

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

${\displaystyle Y_{m}=TG_{m}Y_{m-1}=TG_{m}TG_{m-1}\ldots TG_{1}X.}$

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

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

${\displaystyle X=G_{1}TG_{2}T\ldots G_{m-1}TG_{m}T(Y_{m})=G_{1}TG_{2}T\ldots G_{m-1}T(Y_{m-1})=\ldots =G_{1}T(Y_{1})=X.}$

Функции, используемые в сетях Фейстеля[править | править код]

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

• блок подстановок (s-блок, англ. s-box);
• блок перестановок (p-блок, англ. p-box).

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

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

S-блок[править | править код]

Блок подстановок (s-блок, англ. s-box) состоит из следующих частей:

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

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

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

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

P-блок[править | править код]

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

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

Циклический сдвиг[править | править код]

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

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

Циклический сдвиг на m бит для n-разрядного входа (m < n)

Направление сдвига	Порядок следования битов до сдвига	Порядок следования битов после сдвига
Влево	${\displaystyle b_{0},b_{1},b_{2},...,b_{n-1}}$	${\displaystyle b_{m},b_{m+1},...b_{n-1},b_{0},b_{1},...,b_{m-1}}$
Вправо	${\displaystyle b_{0},b_{1},b_{2},...,b_{n-1}}$	${\displaystyle b_{n-m},b_{n-m+1},...b_{n-1},b_{0},b_{1},...,b_{n-m-1}}$

Сложение по модулю n[править | править код]

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

(A + B) mod n

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

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

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

A + B mod ${\displaystyle 2^{m}}$

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

Умножение по модулю n[править | править код]

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

(A * B) mod n

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

В персональных компьютерах на платформе x86 при перемножении двух m-разрядных чисел получается число разрядностью 2*m. Чтобы получить остаток от деления на ${\displaystyle 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»), сложение по модулю ${\displaystyle 2^{n}}$, умножение по модулю ${\displaystyle 2^{n}}$, и т. д.);
• хорошая изученность алгоритмов, построенных на основе сетей Фейстеля^[4].

Недостатки:

• за один раунд шифруется только половина входного блока^[5].

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

Сети Фейстеля были широко изучены криптографами в силу их обширного распространения. В 1988 году Майкл Луби^[en] и Чарльз Ракофф^[en] провели исследования сети Фейстеля и доказали, что если раундовая функция является криптостойкой псевдослучайной, а используемые ключи независимы в каждом раунде, то 3 раундов будет достаточно для того, чтобы блочный шифр являлся псевдослучайной перестановкой, тогда как четырёх раундов будет достаточно для того, чтобы сделать сильную псевдослучайную перестановку.

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

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

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

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

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

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

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

Алгоритм IDEA[править | править код]

Источник ^[7]:

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

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

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

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

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

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

${\displaystyle 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)};}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Люцифер (Lucifer)[править | править код]

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

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

Хотя изначальная модификация «Люцифера» обходилась без «ячеек Фейстеля», она хорошо демонстрирует то, как только применением 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[править | править код]

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

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

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

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

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

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

${\displaystyle {\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)}\};}$

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

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

«Магма»[править | править код]

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

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

${\displaystyle {\tilde {L_{i}}}=(L_{i}+K_{i})\ {\bmod {\ }}2^{32};}$

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

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

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

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

Примечания[править | править код]

Литература[править | править код]

• Баричев С. Г., Гончаров В. В., Серов Р. Е. Основы современной криптографии — 3-е изд. — М.: Диалог-МИФИ, 2011. — 176 с. — ISBN 978-5-9912-0182-7
• Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0

Эта статья входит в число хороших статей русскоязычного раздела Википедии.