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



жүктеу 4.51 Mb.
бет9/44
Дата13.09.2017
өлшемі4.51 Mb.
түріКурс лекций
1   ...   5   6   7   8   9   10   11   12   ...   44

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


Сеть Фейстеля (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 и т. д.).

  • Хорошая изученность алгоритмов на основе сетей Фейстеля.

Недостатки:



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



Достарыңызбен бөлісу:
1   ...   5   6   7   8   9   10   11   12   ...   44


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет