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

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

Сеть  Фе́йстеля (конструкция Фейстеля) — один из методов построения блочных шифров. Сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции шифрования и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых ключей. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть.

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

Шифрование

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

• Вся информация разбивается на блоки фиксированной длины. В случае, если длина входного блока меньше, чем размер, который шифруется заданным алгоритмом, то блок удлиняется каким-либо способом. Как правило длина блока является степенью двойки, например: 64 бита, 128 бит.
• Выбранный блок делится на два равных подблока — «левый» ( ) и «правый» ( ).
• «Левый подблок» видоизменяется функцией в зависимости от раундового ключа , после чего он складывается по модулю 2 с «правым подблоком» .
• Результат сложения присваивается новому левому подблоку , который будет половиной входных данных для следующего раунда, а «левый подблок» присваивается без изменений новому правому подблоку , который будет другой половиной.
• После чего операция повторяется N-1 раз, при этом при переходе от одного этапа к другому меняются раундовые ключи ( на и т. д.) по какому-либо математическому правилу, где N — количество раундов в заданном алгоритме.

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

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

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

• блок открытого текста делится на 2 равные части
• в каждом раунде вычисляется (  — номер раунда)

,

Где — некоторая функция, а — ключ -го раунда.

Результатом выполнения раундов является . Но обычно в -ом раунде перестановка и не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации:

,

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

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

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

В своей работе «Криптография и Компьютерная безопасность»  Хорст Фейстель описывает два  различных блока преобразований (функций ) — блок подстановок (S-блок) и блок перестановок (P-блок). Можно показать, что любое двоичное преобразование над двоичным блоком фиксированной длины, сводятся к S-блоку, но на практике в силу сложности строения n-разрядного S-блока при больших n, применяют более простые конструкции.

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

S-блок (S-box)

Блок подстановок (S-блок) состоит из дешифратора, преобразующего n-разрядный двоичный сигнал в одноразрядный сигнал по основанию , системы коммутаторов внутренних соединений (всего возможных соединений ) и шифратора, переводящего сигнал из одноразрядного -ричного в n-разрядный двоичный. Анализ n-разрядного S-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений крайне велико ( ). На практике блок подстановок используется как часть более сложных систем.

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

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

P-блок (P-box)

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

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

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

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

Недостатки:

• За один раунд шифруется только половина входного блока