Фейстела. Сеть Фейстела представляет собой общий метод преобразования произвольной функции (обычно называемой F-функцией) в перестановку на множестве блоков. Эта конструкция была изобретена Хорстом Фейстелом и была использована в большом количестве шифров, включая DES и ГОСТ 28147-89. Р-функция, представляющая собой основной строительный блок сети Фейстела, всегда выбирается нелинейной и практически во всех случаях необратимой.

Формально Р-функцию можно представить в виде отображения

F: Z2,N/2 X Z2,k Z2,N/2,

где N - длина преобразуемого блока текста (должна быть четной), к - длина используемого блока ключевой информации.

Пусть теперь X - блок текста, представим его в виде двух подблоков одинаковой длины X = {А, В}. Тогда одна итерация (или раунд) сети Фейстела определяется как

Хм = в,(Р(в„к,)еА,)

где X, = {А/, В,}, II операция конкатенации, а ® - побитовое исключающее ИЛИ. Структура итерации сети Фейстела представлена на рис 2.1. Сеть Фейстела состоит из некоторого фиксированного числа итераций, определяемого соображениями стойкости разрабатываемого шифра, при этом на последней итерации перестановка местами половин блока текста не производится, т.к. это не влияет на стойкость шифра.

Данная структура шифров обладает рядом достоинств, а именно:

процедуры шифрования и расшифрования совпадают, с тем исключением, что ключевая информация при расшифровании используется в обратном порядке;

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

Недостатком является то, что на каждой итерации изменяется только половина блока обрабатываемого текста, что приводит к необходимости увеличивать число итераций для достижения требуемой стойкости.

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

Другим подходом к построению блочных шифров является использование обратимых зависящих от ключа преобразований. В этом случае на каждой итерации изменяется весь блок и, соответственно, общее количество итераций может быть сокращено. Каждая итерация представляет собой последовательность преобразований (так называемых "слоев"), каждое из которых выполняет свою функцию. Обычно используются слой нелинейной обратимой замены, слой линейного перемешивания и один или два слоя подмешивания ключа К недостаткам данного подхода можно отнести то, что для процедур шифрования и расшифрования в общем случае нельзя использовать одни и те же блоки, что увеличивает аппаратные и/или программные затраты на реализацию.

Рис. 2.2. Структура итерации сети Фейстела.

2.4. Алгоритмы блочного шифрования

2.4.1. Алгоритм DES и его модификации

Американский стандарт криптографического закрытия данных DES (Data Encryption Standard), принятый в 1978 г., является типичным представителем семейства блочных шифров. Этот

шифр допускает эффективную аппаратную и программную реализацию, причем возможно достижение скоростей шифрования до нескольких мегабайт в секунду. Шифр DES представляет собой результат 33 отображений:

DES = IP"x7tj хехрхехлт х1Р,

(2.1)

где IP (Initial Permutation - исходная перестановка) представляет собой проволочную коммутацию с инверсией IP:

58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49,41,33,25, 17, 9, 1,59,51,43,35,27, 19, 11,3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7, композиция exTTj , где 0 - перестановка местами правой и левой половин блока данных, представляет собой одну итерацию Фейстела. Отметим, что в последнем цикле шифрования по алгоритму DES перестановка местами половин блока не производится.

Подстановки Лу , 1< / < 16, описываются следуюш,им образом: Шаг 1. На /-М цикле входной блок х длиной 64 символа

делится на два блока по 32 символа Х = (х,;о, Х/д x,3i) и

X - {xifi, Х\\ Xyi).

Правый блок X разбивается на восемь блоков по четыре символа:

Эти восемь блоков путем копирования крайних элементов преобразуются в восемь блоков из шести символов:

Xjfi

Х,,\

Входная последовательность битов

Начальная перестановка Р

1,2,...

€>-[i>

L, = Ro

R, = Loef(Ro,K,)

1>

ц=к,

R2=L, efCRpK)

Ll5~Rl4

R,5=L,4 ®f(R,4.K,5)

R,6=L,5 ®f(R,5,K,6)

Ll6~Rl5

Конечная перестановка IP"

Выходная последовательность битов (шифртекст)

Рис 2.3. Схема алгоритма шифрования DES Шаг 2. На /-циьслической итерации 48 разрядов ьслюча

поразрядно суммируются (по модулю 2) с полученными выше 48 разрядами данных.

Шаг З.у-й блок из шести символов (0< j <8) подается на вход блока подстановки (S-бокс) S[/] имеет шестиразрядный вход и четырехразрядный выход и представляет собой четыре преобразования из Z2,4 в Z2,4; два крайних разряда входного блока служат для выборки одного из этих преобразований. Каждая из восьми подстановок S[0], S[l],..., S[7] осуш,ествляется с использованием четырех строк и 16 столбцов матрицы с элементами {0,1,...,15}. Каждый из массивов размерностью 4x16 определяет подстановку на множестве Z2,4 следуюш,им образом. Если входом является блок из шести символов (zo, z\, zj, z, za,, zs), TO две крайние позиции (zq, zs) интерпретируются как двоичное представление целых чисел из набора {0,1,2,3}.

Эти целые определяют номер строки (от О до 3). Оставшиеся четыре символа (zi, Z2, Z3, Z4) интерпретируются как двоичное представление целых чисел из набора {0,1,...,15} и служат для определения столбца в массиве (от О до 15). Таким образом, входной блок (0,0,1,0,1,1) соответствует строке 1 и столбцу 5.

Шаг 4. 32 разряда, составляюш,ие выход S-бокса, подаются на вход блока проволочной коммутации (Р-бокса):

16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25

Шаг 5. Компоненты правого входного 32-разрядного блока X, преобразованного в Т(Х), поразрядно суммируются по модулю 2 с компонентами левого входного 32-разрядного блока X.

На каждой итерации используется 48-разрядный подключ (kifi, Аг/д А:,;47). Поскольку входным ключом DES является 56-разрядный блок к = = (кф, кц kiss), то каждый его разряд используется многократно.

Какие именно разряды ключа используются на i-циклической итерации, определяется по следуюш,ему алгоритму:

прежде всего 64 разряда ключа преобразуются в 56 путем выбрасывания каждого восьмого бита (который может использоваться для контроля целостности ключа);

производится начальная перестановка КР-1 56-разрядного ключа пользователя к = (кф, кц kiss)-

57, 49, 41, 33, 25, \7, 9, 1, 58, 50, 42, 34, 26, 18,