Алгоритм шифрования DES

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

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

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

При описании алгоритма применены следующие обозначения:

L и R — последовательности битов. (левая и правая).

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

Пусть из файла исходного текста считан 64-битовый блок T. Этот блок преобразуется с помощью матрицы начальной перестановки IP.

Таблица 4.1.1 — Матрица начальной перестановки IP

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

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

Т_i= L_iR_i,

где L_i=t₁t₂…t₃₂ (первые 32 бита),

R_i=t₃₃t₃₄…t₆₄ (последние 32 бита).

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

;

.

Рисунок 4.1.1 — Структура алгоритма DES

Функция f называется функцией шифрования. Её аргументами является последовательность R_i-1, получаемые на предыдущем шаге итерации и 48-битовый ключ K_i, который является результатом преобразования 64-битового ключа шифра K.

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

По окончанию шифрования осуществляется восстановление позиции битов с помощью матрицы обратной перестановки IP^-1.

Таблица 4.1.2 — Матрица обратной перестановки IP^-1

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

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

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

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

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

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

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

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

Таблица 4.1.4 — Функция P перестановки битов

Таблица 4.1.5 — Функции преобразования S₁, S₂, … S₈

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

Таблица 4.1.6 — Функция G первоначальной подготовки ключа

Данная таблица разделена на две части. Результат преобразования G(K) разбивается на две половины С₀ и D₀ по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются биты последовательности С₀.

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности.

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

После определения С₀ и D₀ рекурсивно определяются С_i и D_i, i = 1, 2…16.

Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации.

Операции сдвига выполняются для последовательностей С_i и D_i независимо.

Таблица 4.1.7 — Таблица количества сдвигов

Ключ, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последовательности С_iD_i и их перестановки. Другими словами, ключ K_i = H(С_iD_i), где функция H определяется матрицей, завершающей обработку ключа.

Таблица 4.1.8 — Функция H завершающей обработки ключа