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

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

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

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

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

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

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

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

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

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

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

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

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

Циклический сдвиг влево на 3 разряда 8-битной шины

Можно показать, что циклический сдвиг является частным случаем 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» обозначается как

(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 обозначается как

(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].

Источник [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}$.

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

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

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

Исторически первым алгоритмом, использующим сеть Фейстеля, был алгоритм «Люцифер», при работе над которым Фейстелем и была, собственно, разработана структура, впоследствии получившая название «сеть Фейстеля». В июне 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-блок.

Функция ${\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.

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