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

Рис. 2а. Шифрование Рис. 2б. Расшифрование
При выполнении операции шифрования сеть Фейстеля имеет следующую структуру (рис. 2а):
-
вся информация разбивается на блоки фиксированной длины. В случае, если длина входного блока меньше, чем размер, который шифруется заданным алгоритмом, то блок удлиняется (дополняется) каким-либо способом. Как правило, длина блока является степенью двойки, например: 64 бита, 128 бит. Далее будем рассматривать операции происходящие только с одним блоком, так как с другими блоками в процессе шифрования выполняются те же самые операции.
-
Выбранный блок делится на два равных подблока – «левый» (L0) и «правый» (R0).
-
«Левый подблок» L0 видоизменяется функцией f(L0, K0) (т.н. образующая функция) в зависимости от раундового ключа K0, после чего он складывается по модулю 2 (XOR) с «правым» подблоком R0.
-
Результат сложения присваивается новому левому подблоку L1, который будет половиной входных данных для следующего раунда, а «левый подблок» L0 присваивается без изменений новому правому подблоку R1 (см. рис.2а), который будет другой половиной.
-
После чего операция повторяется N-1 раз (раундов), при этом при переходе от одного этапа к другому меняются раундовые ключи (K0 на K1 и т. д.) по какому-либо математическому правилу, где N – количество раундов в заданном алгоритме.
Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи идут в обратном порядке, то есть не от первого к N-ному, а от N-го к первому (рис.2б).
На сегодня считается, что оптимальное число раундов лежит в диапазоне от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойкость алгоритма. Видимо это свойство и повлияло на столь активное распространение сети Фейстеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алгоритм.
Сеть Фейстеля является обратимой даже в том случае, если функция F не является таковой, так как для дешифрования не требуется вычислять F-1. Для дешифрования используется тот же алгоритм, но на вход подается зашифрованный текст, и ключи используются в обратном порядке.
Основной характеристикой алгоритма, построенного на основе сети Фейстеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, называемые забеливанием (whitening), осуществляются для того, чтобы выполнить начальную рандомизацию («размешивание») входного текста.
В своей работе «Криптография и Компьютерная безопасность» Хорст Фейстель описывает два различных блока преобразований (функций f(Li, Ki)) – блок подстановок S-блок (S-box) и блок перестановок P-блок (P-box). Можно доказать, что любое двоичное преобразование над двоичным блоком фиксированной длины, сводятся к S-блоку, но на практике в силу сложности строения n-разрядного S-блока при больших n, применяют более простые конструкции.
Термин «блок» в оригинальной статье используется вместо функции вследствие того, что речь идёт о блочном шифре и предполагалось, что S- и P-блоки будут цифровыми микросхемами (цифровыми блоками).
Блок подстановок (S-блок) состоит из дешифратора, преобразующего n-разрядный двоичный сигнал в одноразрядный сигнал по основанию 2n, системы коммутаторов внутренних соединений (всего соединений 2n!) и шифратора, переводящего сигнал из одноразрядного 2n-ричного в n-разрядный двоичный. Анализ n-разрядного S-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений крайне велико (2n!). На практике блок подстановок используется как часть более сложных систем.
В общем случае S-блок может иметь несовпадающее число входов/выходов, в этом случае в системе коммутации от каждого выхода дешифратора может идти не строго одно соединение, а 2 или более или не идти вовсе. То же самое справедливо и для входов шифратора.
В электронике можно непосредственно применять приведённую на рис.3 схему:
Рис. 3
В программировании же для этого генерируют таблицы замены:
Таблица замены для приведённого на рис.3 3-разрядного S-блока
№ комбинации
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Вход
|
000
|
001
|
010
|
011
|
100
|
101
|
110
|
111
|
Выход
|
011
|
000
|
001
|
100
|
110
|
111
|
010
|
101
|
Оба этих подхода являются эквивалентными, то есть файл, зашифрованный на компьютере, можно расшифровать на электронном устройстве и наоборот.
Блок перестановок (P-box) всего лишь изменяет положение цифр и является линейным устройством. Этот блок может иметь очень большое количество входов-выходов, однако в силу линейности систему нельзя считать криптоустойчивой. Криптоанализ ключа для n-разрядного P-блока проводится путём подачи на вход n-1 различных сообщений, каждое из которых состоит из n-1 нуля («0») и 1 единицы («1»):
Рис.4 Принципиальная схема 8-разрядного P-блока
Ещё один вариант перестановок данных – циклические сдвиги. Можно показать, что циклический сдвиг является частным случаем P-box.
Достоинства сетей Фейстеля:
-
Простота аппаратной реализации на современной электронной базе.
-
Простота программной реализации, так как значительная часть функций поддерживается на аппаратном уровне в современных компьютерах (например, сложение по модулю 2, сложение по модулю 2n, умножение по модулю 2n и т. д.).
-
Хорошая изученность алгоритмов на основе сетей Фейстеля.
Недостатки:
-
За один раунд шифруется только половина входного блока (можно сказать, что у алгоритма невысокий КПД).
Достарыңызбен бөлісу: |