1.1 Шифрование

Общая структура DES представлена на рисунке 1. Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:

1. начальная подготовка блока данных;

2. 16 раундов "основного цикла";

3. конечная обработка блока данных.

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

На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа, получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.

Рисунок 1  Общая схема DES

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

Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES.

На первом этапе 64-разрядный блок исходных данных подвергается начальной перестановке IP . В литературе эта операция иногда называется "забеливание" – whitening. При начальной перестановке биты блока данных определенным образом переупорядочиваются. Эта операция придает некоторую "хаотичность" исходному сообщению, снижая возможность использования криптоанализа статистическими методами.

Одновременно с начальной перестановкой блока данных выполняется начальная перестановка 56 бит ключа. Из рисунка 1 видно, что в каждом из раундов используется соответствующий 48-битный частичный ключ K_i. Ключи K_i получаются по определенному алгоритму, используя каждый из битов начального ключа по нескольку раз. В каждом раунде 56-битный ключ делится на две 28-битовые половинки. Затем половинки сдвигаются влево на один или два бита в зависимости от номера раунда. После сдвига определенным образом выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, то эта операция называется "перестановка со сжатием". Ее результатом является набор из 48 битов. В среднем каждый бит исходного 56-битного ключа используется в 14 из 16 подключей, хотя не все биты используются одинаковое количество раз.

Далее выполняется основной цикл преобразования. Полученный после начальной перестановки 64-битовый блок IP(T) участвует в 16-циклах преобразования Фейстеля. При этом в каждом раунде (рисунок 2) получается промежуточное 64-битное значение, которое затем обрабатывается в следующем раунде.

Рисунок 2  Структура одного раунда DES

Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения. IP(T _i-1) разбивается на две части L _i-1, R _i-1, где:

L _i-1, R _i-1 — соответственно 32 старших битов и 32 младших битов блока T _i-1;

IP(T _i-1)= L _i-1R _i-1.

Вначале расширяем правую часть блока R _i-1 до 48 битов с помощью функции расширения E. E(R _i-1), используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа. Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется "лавинным эффектом"). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.

После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K _i-1. Полученный после перестановки блок E(R _i-1) складывается по модулю 2 с ключом k _i-1 .

Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution - подстановка), результатом которой является 32-битное значение. Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes).

E(R _i-1) k _i-1 = B₁ B₂ B₃ B₄ B₅ B₆ B₇ B₈

При выполнении этой операции 48 битов данных делятся на восемь 6-битовых подблоков, каждый из которых по своей таблице замен заменяется четырьмя битами. Подстановка с помощью S-блоков является одним из важнейшим этапом DES. Таблицы замен для этой операции специально спроектированы специалистами так, чтобы обеспечивать максимальную безопасность. В результате выполнения этого этапа получаются восемь 4-битовых блоков (B₁’ B₂’ B₃’ B₄’ B₅’ B₆’ B₇’ B₈’), которые вновь объединяются в единое 32-битовое значение.

Далее полученное 32-битовое значение обрабатывается с помощью перестановки Р (от англ. Permutation – перестановка), которая не зависит от используемого ключа. Целью перестановки является максимальное переупорядочивание битов такое, чтобы в следующем раунде шифрования каждый бит с большой вероятностью обрабатывался другим S-блоком.

f (R _i-1, k _i-1) = P (B₁’ B₂’ B₃’ B₄’ B₅’ B₆’ B₇’ B₈’)

И, наконец, результат перестановки объединяется с помощью операции XOR с левой половиной первоначального 64-битового блока данных.

T _i-1= L _i-1R _i-1 - результат (i-1) итерации, тогда

T _i= L _iR _i - результат i-ой итерации, где:

L _i = R _i-1

R _i = L _i-1 f (R _i-1, k _i-1)

Левая половина L _i равна правой половине предыдущего вектора

L _i-1R _i-1. А правая половина R _i — это битовое сложение L _i-1 и f (R _i-1, k _i-1) по модулю 2.

После шестнадцати раундов шифрования выполняется конечная перестановка результата. Эта перестановка инверсна (обратна) начальной перестановке.

После выполнения всех указанных шагов блок данных считается полностью зашифрованным и можно переходить к шифрованию следующего блока исходного сообщения.

Разработчики DES приложили все силы для того, чтобы сделать процесс вскрытия зашифрованных сообщений как можно более трудным. Даже простое описание DES на бумаге выглядит достаточно сложным, что уж говорить про его программную реализацию! Разработать правильно и оптимально функционирующую программу полностью в соответствии с DES, наверно, под силу только опытным программистам. Некоторые трудности возникают при программной реализации, например, начальной перестановки или перестановки с расширением. Эти сложности связаны с тем, что первоначально планировалось реализовывать DES только аппаратно. Все используемые в стандарте операции легко выполняются аппаратными блоками, и никаких трудностей с реализацией не возникает. Однако через некоторое время после публикации стандарта разработчики программного обеспечения решили не стоять в стороне и тоже взяться за создание систем шифрования. В дальнейшем DES реализовывался и аппаратно, и программно.