Американский стандарт шифрования данных DЕS

Стандарт шифрования данных DЕS (Data Еnсгурtіоn Standard) опубликован в 1977г. Национальным бюро стандартов США. Стандарт DЕS предназначен для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 г. был одобрен Национальным институтом стандартов и технологий США (НИСТ). С этого момента DЕS превращается в стандарт не только по названию (Data Еnсгурtіоn Standard), но и фактически. Появляются программное обеспечение и специализированные микро ЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных.

К настоящему времени DЕS является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того, реализация алгоритма DЕS в таких системах становится признаком хорошего тона.

Основные достоинства алгоритма DЕS:

• используется только один ключ длиной 56 бит;

• зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет программ. соответствующий стандарту ОЕЗ;

• относительная простота алгоритма обеспечивает высокую скорость обработки;

• достаточно высокая стойкость алгоритма.

Первоначально метод, лежащий в основе стандарта DES, был разработан фирмой ІВМ для своих целей и реализован в виде системы "Люцифер". Система "Люцифер" основана на комбинировании методов подстановки и перестановки и состоит из чередующейся последовательности блоков перестановки и подстановки. В ней использовался ключ длиной 128 бит, управлявший состояниями 78 блоков перестановки и подстановки. Система "Люцифер" оказалась весьма сложной для практической реализации из-за относительно малой скорости шифрования (2190 байт/с-программная реализа- ция, 96970 байт/с-аппаратная реализация).

Алгоритм DES также использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит-проверочные биты для контроля на четность). Дешифрование в является операцией, обратной шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности. Обобщенная схема процесса шифрования в алгоритме DES показана на рис.3.1. Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрованияи, наконец, в конечной перестановке битов.

Рис.3.1. Обобщенная схема шифрования в алгоритме DЕS

Следует сразу отметить, что все приводимые таблицы являются стандартными и должны включаться в реализацию алгоритма DЕS в неизменном виде.

Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс рас- шифровки путем подбора ключа. При описании алгоритма DЕS (рис.3.2) применены следующие обозначения:

L и R-последовательности битов (левая (Іеft) и правая (гіght));

LR-конкатенация последовательностей L_ и R, т.е. такая по- следовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

O+-операция побитового сложения по модулю 2.

1, 2, ... 64

Рис.3.2. Структура алгоритма DЕS

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помощью матрицы начальной перестановки ІР (табл.3.1).

Биты входного блока Т (64 бита) переставляются в соответствии с матрицей ІР: бит 58 входного блока Т становится битом 1, бит 50-битом 2 и т.д. Эту перестановку можно описать выражением Т₀=ІР(Т). Полученная последовательность битов Т₀ разделяется на две последовательности: Ц-левые или старшие биты, Р₀-пра- вые или младшие биты, каждая из которых содержит 32 бита.

Таблица 3.1 Матрица начальной перестановки ІР

Таблица 3.2 Матрица обратной перестановки ІР^_1

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т_і-результат і-й итерации:

Т_і = L_і R_і

где L_і = t_і t₂.. t₃₂ (первые 32 бита); R_і = t₃₃ t₃₄…t₆₄ (последние 32 бита).

Тогда результат і-й итерации описывается следующими формулами:

Функция f называется функцией шифрования. Ее аргументами являются последовательность R_i_-1, получаемая на предыдущем шаге итерации, и 48-битовый ключ Қ_i который является результа- том преобразования 64-битового ключа шифра К. (Подробнее функция шифрования f и алгоритм получения ключа Қ_i описаны ниже.)

На последнем шаге итерации получают последовательности R₁₆ и L₁₆ (без перестановки местами), которые конкатенируются в 64-битовую последовательность R₁₆L₁₆.

По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы обратной перестановки ІР^-¹ (табл.3.2).

Пример того, как соотносятся элементы первой строки матрицы ІР^-¹ с элементами матрицы ІР приведен в табл.3.3.

Таблица 3.3

Связь элементов матриц

Элемент матрицы ІР^-¹	Элемент матрицы ІР

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей ІР^_1, а затем над последовательностью битов выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

Итеративный процесс расшифрования может быть описан следующими формулами:

Таким образом, для процесса расшифрования с переставленным входным блоком на первой итерации используется ключ К₁₆, на второй итерации-К₁₅ и т.д. На 16-й итерации используется ключ К₁. На последнем шаге итерации будут получены последовательности L₀ и R₀, которые конкатенируются в 64-битовую последовательность L₀R₀ . Затем в этой последовательности 64 бита переставляются в соответствии с матрицей ІР. Результат такого преоб- разования-исходная последовательность битов (расшифрованное 64-битовое значение).

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f(R_i_-1,K_i ) показана на рис.3.3.

R_і_-1(32 бита)

Рис.3.3. Схема вычисления функции шифрования f

Для вычисления значения функции f используются:

• функция Е (расширение 32 бит до 48);

• функция S₁, S₂,..., S₈ (преобразование 6-битового числа в 4-битовое);

• функция Р (перестановка битов в 32-битовой последовательности).

Приведем определения этих функций.

Аргументами функции шифрования f являются R_i_-1 (32 бита) и K_i(48 бит). Результат функции Е((R_i_-1) есть 48-битовое число. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), определяется табл.3.4.

В соответствии с табл.3.4 первые три бита Е(R_i_-1) - это биты 32,1 и 2, а последние-31, 32,1. Полученный результат (обозначим его Е(R_i_-1)) складывается по модулю 2 (операция ХОR) с текущим значением ключа K_i и затем разбивается на восемь 6-битовых блоков Ві, В₂,…. В₈:

Таблица 3.4 Функция расширения Е

В результате получаем S₁(В₁), S₂ (B₂) …. S₈(В₈), т.е. 32-битовый блок (поскольку матрицы S_j) содержат 4-битовые элементы). Этот 32-битовый блок преобразуется с помощью функции перестановки битов Р (табл.3.6).

Таким образом, функция шифрования

f(R_i-1,K_i) = Р(S₁(В₁), S₂ (B₂) …. S₈(В₈))

Как нетрудно заметить, на каждой итерации используется новое значение ключа Қ_i (длиной 48 бит). Новое значение ключа K_i вычисляется из начального ключа К (рис.3.4). Ключ К представляет собой 64-

битовый блок с 8 битами контроля по четности, расположенными в позициях 8,16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл.3.7).

Табл.3.7 разделена на две части. Результат преобразования G(К) разбивается на две половины С₀ и D₀ по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются биты последовательности С₀ (первым битом С₀ будет бит 57 ключа шифра, затем бит 49 и т.д., а последними битами-биты 44 и 36 ключа).

Рис. 3.4. Схема алгоритма вычисления ключей К_i

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности D₀ (т.е. последовательность D₀ будет состоять из битов 63, 55, 47, ...,12, 4 ключа шифра).

Как видно из табл.3.7, для генерации последовательностей С₀ и D₀ не используются биты 8,16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56-битовым.

После определения С₀ и D ₀ рекурсивно определяются С_i| и D_i, і = 1, 2, ...,16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в табл.3.8.

Операции сдвига выполняются для последовательностей С_i| и D_i независимо. Например, последовательность С₃ получается посредством циклического сдвига влево на две позиции последовательности С₂, а последовательность

D ₃- посредством сдвига влево на две позиции последовательности D₂, С₁₆ и D₁₆ получаются из С₁₅ и D₁₅ посредством сдвига влево на одну позицию.

Таблица 3.8

Таблица сдвигов s_i для вычисления ключа

12 Следующая ⇒