Курс лекций «Проблемы безопасности в информационных технологиях»

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

При выполнении операции шифрования сеть Фейстеля имеет следующую структуру (рис. 2а):

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

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

На сегодня считается, что оптимальное число раундов лежит в диапазоне от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойкость алгоритма. Видимо это свойство и повлияло на столь активное распространение сети Фейстеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алгоритм.

Сеть Фейстеля является обратимой даже в том случае, если функция F не является таковой, так как для дешифрования не требуется вычислять F^-1. Для дешифрования используется тот же алгоритм, но на вход подается зашифрованный текст, и ключи используются в обратном порядке.

Основной характеристикой алгоритма, построенного на основе сети Фейстеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, называемые забеливанием (whitening), осуществляются для того, чтобы выполнить начальную рандомизацию («размешивание») входного текста.

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

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

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

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

В электронике можно непосредственно применять приведённую на рис.3 схему:

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

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


Рис.4 Принципиальная схема 8-разрядного P-блока
Ещё один вариант перестановок данных – циклические сдвиги. Можно показать, что циклический сдвиг является частным случаем P-box.

Достоинства сетей Фейстеля:

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

Недостатки:

• 
  За один раунд шифруется только половина входного блока (можно сказать, что у алгоритма невысокий КПД).