Часть 1

Прошло уже почти 30 лет с момента принятия алгоритма DES в качестве стандарта шифрования США. DES – алгоритм шифрования с наиболее богатой и интересной историей.

Основные характеристики и структура алгоритма
DES шифрует информацию блоками по 64 бита с помощью 64-битного ключа шифрования, в котором используется только 56 бит (процедура расширения ключа подробно описана ниже).
Шифрование информации выполняется следующим образом (рис. 1):
Этап 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).
Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровании, так и при расшифровании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей раундов, кроме текущего.

Режимы работы
Несколько позже, в 1980 году был принят стандарт (4 [25]), определяющий режимы работы алгоритма DES. Можно сказать, что данный стандарт уточнял подробности реализации DES для различных применений.
В стандарте были определены следующие режимы работы алгоритма DES:
- электронная кодовая книга ECB (Electronic Code Book);
- сцепление блоков шифра CBC (Cipher Block Chaining);
- обратная связь по шифртексту CFB (Cipher Feed Back);
- обратная связь по выходу OFB (Output Feed Back).
Наиболее простым из них является режим ECB. Суть его состоит в том (рис. 5), что каждый блок шифруемых данных «прогоняется» через алгоритм шифрования отдельно и независимо от других блоков:
Ci = Ek(Mi),
где Ek – функция зашифрования на ключе k,
Mi и Ci – блоки открытого текста и соответствующие им блоки шифртекста.
Аналогично выполняется и расшифрование – блоки шифртекста обрабатываются поочередно и независимо.
Данный режим плох тем, что если открытый текст содержит какое-либо количество блоков с одинаковым содержимым (например, некий большой массив, проинициализированный нулевыми или единичными битами), то и шифртекст будет содержать такое же количество одинаковых блоков. Это непозволительно, поскольку дает криптоаналитику информацию о структуре зашифрованной информации, что может существенно облегчить вскрытие алгоритма шифрования (т. е. получение открытого текста из зашифрованного или вычисление ключа шифрования). Поэтому данный режим должен использоваться только для шифрования ключей друг на друге в многоключевых схемах (1 [2]). Допускается также шифрование режимом ECB небольших фрагментов данных при условии их неповторяемости (5 [39]).
Есть и еще один недостаток – в данном режиме алгоритм шифрует данные только поблочно. При необходимости, например, зашифровать алгоритмом DES 8 бит придется дополнить эти данные до 64-битного размера блока, зашифровать блок целиком, а при расшифровании отбросить дополняющие биты. Такое не всегда возможно.
Достоинство режима ECB – простота реализации по сравнению с другими режимами. Однако, по словам Брюса Шнайера, «из-за своей простоты в большинстве существующих коммерческих программ используется режим ECB, хотя этот режим наиболее уязвим к в