Тема 3.5. Криптографический стандарт DES.

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

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

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

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

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

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

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

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

Шифрование информации выполняется следующим образом:
Этап 1. Над 64-битным блоком данных выполняется начальная перестановка согласно следующей таблице:
Данная таблица означает, что значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита – в бит 2 и т. д.
Этап 2. Результат предыдущей операции делится на 2 субблока по 32 бита (на рис. 1 обозначены A0 и B0), над которыми производятся 16 раундов следующих преобразований:
Ai = Bi-1,
Bi = Ai-1 +О f(Bi-1, Ki),
где i – номер текущего раунда,
Ki – ключ раунда, а +О – побитовая логическая операция «исключающее или» (XOR).
Структура функции раунда f() приведена на рис. 2. Данная функция выполняется в несколько шагов:
Шаг 1. Над 32-битным входом выполняется расширяющая перестановка EP (рис. 3). Данная операция решает две задачи: во-первых, расширяет входное значение до 48 бит для последующего сложения с ключом раунда; во-вторых, обеспечивает влияние «размножаемых» бит на 2 таблицы замен (описаны ниже) вместо одной, что ускоряет возникновение зависимости каждого бита шифртекста от каждого входного бита (2 [4]), что называется лавинным эффектом.
Шаг 2. Результат предыдущего шага складывается с ключом раунда Ki операцией XOR.
Шаг 3. Результат сложения разбивается на 8 фрагментов по 6 бит, каждый из которых прогоняется через соответствующую таблицу замен (S1 … S8). Таблицы замен являются фиксированными и описаны в стандарте (3 [24]). Каждая таблица содержит по 4 строки, содержащих по 16 значений от 0 до 15. Входное значение интерпретируется следующим образом: два крайних бита формируют номер строки (от 0 до 3), из которой выбирается число, расположенное в столбце, номер которого соответствует значению четырех остальных бит входа. Например, при двоичном входе 101100 (десятичное число 44) выбирается значение шестой ячейки второго столбца.
Шаг 4. На последнем шаге 4-битные значения, полученные после выполнения замен, объединяются, после чего над ними выполняется операция P, представляющая собой простую перестановку согласно следующей таблице:
Стоит отметить, что в последнем раунде алгоритма субблоки не меняются местами.
Этап 3. Полученные субблоки A16 и B16 объединяются в 64-битный блок, над которым выполняется финальная перестановка данных согласно следующей таблице:
Финальная перестановка является инверсной по отношению к начальной перестановке, выполняемой на этапе 1. Результат финальной перестановки и является блоком зашифрованных данных.
Расшифрование данных алгоритмом DES выполняется абсолютно так же, как и зашифрование, однако с обратным порядком использования ключей раунда: в i-м раунде расшифрования используется ключ K(17-i).

Процедура расширения ключа
Схема процедуры расширения ключа показана на рис. 4. Ее задача – формирование 16 ключей раунда, которое выполняется следующим образом.
Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 бит. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся бит ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом (3 [24]). Процедура извлечения 56 значащих бит 64-битного ключа на рис. 4 обозначена как E. Помимо извлечения, данная процедура выполняет еще и перестановку бит ключа согласно следующим таблицам:
В результате перестановки формируются два 28-битных значения C и D. Верхняя таблица определяет выборку бит ключа для C, нижняя – для D.
Затем выполняется 16 раундов преобразований, каждый из которых дает один из ключей раунда Ki. В каждом раунде производятся следующие действия:
1. Текущие значения C и D циклически сдвигаются влево на переменное число бит n. Для раундов 1, 2, 9 и 16 n = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.
2. C и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда Ki. Сжимающая перестановка выполняется согласно следующей таблице:
Сочетание циклического сдвига и сжимающей перестановки приводит к тому, что в каждом ключе раунда используется уникальный набор бит ключа шифрования.
При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раунда в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на n бит, где n = 0 для первого раунда, n = 1 для раундов 2, 9, 16 и n = 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифрования ключи раунда K(17-i).
Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровании, так и при расшифровании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей раундов, кроме текущего.