Тема 3. Симметричные криптосистемы

Цели и задачи изучения темы

Целью данной темы является рассмотрение вопросов построения современных симметричных криптосистем.

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

Наиболее широкое распространение среди блочных алгоритмов получили алгоритмы, построенные на так называемой сети Фейстеля, так как, с одной стороны, они удовлетворяют всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, достаточно просты и компактны.

Сеть Фейстеля имеет следующую структуру. Входной блок делится на несколько подблоков, имеющих равную длину и называемых ветвями. В классической сети Фейстеля (предложенной Х. Фейстелем) используются две ветви. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколько циклов или раундов. В случае двух ветвей сеть Фейстеля приведена на рис. 3.1.

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

Для раунд i отображает следующим образом:

, (3.1)

, (3.2)

где Å – операция побитового сложения по модулю 2, – функция шифрования, вычисляющая значения последовательности из t битов на основании входной t-битовой последовательности и раундового подключа . Каждый из подключей K_i выводится из ключа шифра K. Процедура формирования раундовых подключей и функция шифрования в сети Фейстеля особо не оговаривается.

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

Рис. 3.1. Структура классической сети Фейстеля.

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

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

,

,

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

Описанная выше сеть Фейстеля положена в основу таких широко известных государственных стандартов шифрования, как стандарт США старого поколения DES (Data Encryption Standard), и стандарт Российской Федерации ГОСТ 28147-89. В этих криптосистемах размер блока составляет 64 бита, и соответственно, каждая из ветвей имеет размер 32 бита.

В настоящее время все чаще используются различные разновидности сети Фейстеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются процессоры с 32-разрядными словами, следовательно, оперировать 32-разрядными словами эффективнее, чем с 64-разрядными.