Описание алгоритма DES

Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, с 1980 по 2000 год был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта.

DES является классической сетью Фейштеля с двумя ветвями (см. рис 1). Данные шифруются 64-битными блоками с использованием исходного 64-битного ключа.

Алгоритм преобразует за 16 раундов 64-битный вход X в 64-битный выход Z. Длина ключа Key равна 64 битам, из которых используют для генерирования ключей для каждого раунда шифрования 56 бит (остальные являются контрольными). Общая схема шифрования представлена на рисунке 2.

Процесс шифрования состоит из трех этапов. На первом из них выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Второй этап состоит из 16 раундов выполнения одной и той же функции F (R_i-1, K_i), которая использует операции сдвига и подстановки. На третьем этапе выполняется IP^-1 перестановка результата, полученного на втором этапе. Перестановка IP^-1 инверсна начальной перестановке.

Дешифрование состоит из 16 циклов дешифрования и конечного восстановления порядка бит. Все ниже приведенные таблицы стандартны и должны включаться в программную реализацию алгоритма DES без искажений. Все перестановки и функции подобраны разработчиками шифра так, чтобы максимально усложнить процесс дешифрования путем подбора ключа. В исходном файле отделяют очередной 64-битовый(8–байтный) блок Т. Этот блок преобразуют в соответствии с матрицей начальной перестановки бит (IP – матрица приведена в табл.1). Полученную последовательность разделяют на две последовательности: – L₀ левые или старшие биты и R₀ – правые или младшие биты (каждая длиной 32 бита). Потом реализуют итерационный процесс шифрования, состоящий из 16 циклов (раундов). Пусть T_i – результат итерации.

T_i = L_iR_i,

где L_i – первые 32 бита последовательности;

R_i – последние 32 бита последовательности.

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

L_i = R_i-1, i=1,2,3,…,16;

R_i = L_i-1 xor F (R_i-1, K_i), i=1,2,3,…,16.

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

После 16-го цикла шифрования получают последовательность T₁₆ = L₁₆R₁₆, в которой осуществляют восстановление позиций бит с помощью матрицы обратной перестановки IP^-1 (см. табл. 2).

На рисунке 3 приведена схема реализации функции F (R_i-1, K_i).

Рисунок 3 – Реализация функции F

Таблица 1 – IP – матрица

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

Формирование функции F выполняют так: расширяют блок L_i-1 с 32 бит до 48 бит в соответствии с матрицей Е (табл.3).

Таблица 3 – Матрица расширения Е

Преобразование S-boxes осуществляется так: 48-битовый блок после выполнения расширения в соответствии с матрицей Е и выполнения операции «сложение по модулю 2» с таким же по длине ключом раунда Кi (получение этого ключа из ключа шифрования К будет описано ниже) разбивают на 8 блоков по 6 бит каждый и преобразуют в соответствии с таблицей 4 в 4-х битовые блоки (длина общего блока на выходе 32 бита). После этого полученную последовательность преобразуют перестановкой бит в соответствии с матрицей Р (см. табл. 4).

Таблица 4 – Р-матрица перестановки бит

Таблица 5 – Функция преобразования S-boxes

Пример преобразования Пусть на S₆ подается следующая последовательность бит b₁b₂b₃b₄b₅b₆ (010011). Крайние биты b₁b₆ (01=1) определяют номер строки, а средние b₂b₃b₄b₅ (1001) – номер столбца (в бинарной записи 1001=9). В примере на выход будет выдано 1= 0001.

Рисунок 4 – Схема генерирования ключей раундов k_i

Таблица 6 - G-функция первичной подготовки ключа

Таблица 7 - H-матрица завершающей обработки ключа

Поиск по сайту: