WikiSort.ru - Не сортированное

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

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

• Блок открытого текста делится на две равные части: ${\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-блоки будут цифровыми микросхемами (цифровыми блоками).

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

Основные статьи: Битовые операции, Битовый сдвиг

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

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

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

/* Функция, выполняющая преобразование подблока с учётом значения ключа (по ключу). 
Реализация зависит от выбранного алгоритма блочного шифрования. */
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].

Алгоритм 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.

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

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