Стандарт шифрования данных DES

DES(Data Encryption Standart) – государственный стандарт США. Cтандарт DES стал одним из первых «открытых» шифроалгоритмов. Все схемы используемые для его реализации, были опубликованы и тщательно проверены. Секретным был только ключ, с помощью которого осуществляется кодирование и декодирование информации.

Алгоритм DES базируется на научной работе Шеннона 1949 г., связавшей криптографию с теорией информации. Шеннон выделил два общих принципа используемых в практических шифрах рассеивание и перемешивание. Рассеиванием он назвал распространение влияния одного знака открытого текста на множество знаков шифротекста, что позволяет скрыть статистические свойства открытого текста. Под перемешиванием Шеннон понимал использование взаимосвязи статистических свойств открытого и шифрованного текста. Однако шифр должен не только затруднять раскрытие, но и обеспечивать легкость шифрования и дешифрования при известном секретном ключе. Поэтому была принята идея использовать произведение простых шифров, каждый из которых вносит небольшой вклад в значительное суммарное рассеивание и перемешивание.

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

Стандарт шифрованных данных DES – один из наиболее удачных примеров криптоалгоритма, разработанного в соответствии с принципами рассеивания и перемешивания. В нем открытый текст, криптограмма и ключ являются двоичными последовательностями длиной соответственно М = 64, N = 64, К = 56 бит. Криптоалгоритм DES представляет собой суперпозицию элементарных шифров, состоящую из 16 последовательных шифроциклов, в каждом из которых довольно простые перестановки с подстановками в четырехбитовых группах В каждом проходе используются лишь 48 бит ключа, однако они выбираются внешне случайным образом из полного 56-битового ключа.

Операции шифрования и дешифрования осуществляются по схеме, представленной на рисунке 9.7.

Рисунок 9.7 - Шифратор (дешифратор) в стандарте DES

Перед началом шифрования в специализированный регистр устройства через входной регистр вводится ключ, содержащий 64 бит, из которых 56 используется для генерации субключей, а 8 являются проверочными. Ключ из устройства вывести нельзя. Предусмотрена возможность формирования нового ключа внутри устройства. При этом ключ, вводимый в устройство, шифруется ранее использовавшимся ключом и затем через выходной регистр вводится в специализированный регистр в качестве нового ключа. Шестнадцать субключей по 48 бит каждый, сформированных в генераторе субключей, используется для шифрования блока из 64 символов, поступающих во входной регистр устройства. Шифрование осуществляется из 16 логически идентичных шагов, на каждом из которых используется один из субключей.

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

Алгоритм DES используется как для шифрования, так и для установления подлинности (аутентификации) данных. С точки зрения системы ввода-вывода DES может считаться блочной системой шифрования с алфавитом в 2⁶⁴ символа. Входной блок из 64 бит, который является в этом алфавите символом открытого текста, заменяется новым символом шифрованного текста. На рисунке 9.8 в виде блочной диаграммы показаны функции системы. Алгоритм шифрования начинается с начальной перестановки 64 бит открытого текста, описанной в таблице начальной перестановки (таблица 9.12). Таблица начальной перестановки читается слева направо и сверху вниз, так что после перестановки биты превращаются в После этой начальной перестановки начинается основная часть алгоритма шифрования, состоящая из 16 итераций, которые используют стандартный блок, показанный на рисунке 9.9. Для преобразования 64 бит входных данных в 64 бит выходных, определенных как 32 бит левой половины и 32 бит правой, стандартный блок использует 48 бит ключа. Выход каждого стандартного блока становится входом следующего стандартного блока. Входные 32 бит правой половины ( ) без изменений подаются на выход и становятся 32 бит левой половины ( ). Эти бит с помощью таблицы расширения (таблица 9.13) также расширяются и преобразуются в 48 бит, после чего суммируются по модулю 2 с 48 бит ключа. Как и в случае таблицы начальной перестановки, таблица расширения читается слева направо и сверху вниз.

Таблица 9.12 – Начальная перестановка

Таблица 9.13 – Таблица расширения

Данная таблица расширяет биты

в биты

(9.2)

Отметим, что биты, обозначенные в первом и последнем столбцах таблицы расширения, - это те битовые разряды, которые дважды использовались для расширения от 32 до 48 бит.

Рисунок 9.8 – Стандарт шифрования данных DES

Рисунок 9.9 – Стандартный компоновочный блок

Далее суммируется по модулю 2 с -м ключом, выбор которого описывается позднее, а результат разделяется на восемь 6-битовых блоков.

Иными словами,

(9.3)

Каждый из восьми 6-битовых блоков используется как вход функции S – блока, возвращающей 4 – битовый блок Таким образом, входные 48 бит с помощью функции S – блока преобразуются в 32 бит. Функция отображения S – блока определена в таблице 9.14. Преобразование выполняется следующим образом. Нужная строка – это а нужный столбец - Например, если то преобразование возвращает значение из строки 3, столбца 8, т.е. число 5 (в двоичной записи 0101). 32-битовый блок, полученный на выходе S – блока, переставляется с использованием таблицы перестановки (таблица 9.15). Как и другие таблицы, Р – таблица читается слева направо и сверху вниз, так что в результате перестановки битов получаем 32-битовый выход Р – таблицы суммируется по модулю 2 с 32 бит левой половины образуя выходные 32 бит правой половины

Алгоритм стандартного блока может быть представлен следующим образом:

(9.4)

(9.5)

Здесь обозначает функциональное соотношение, включающее описанные выше расширение, преобразование в S – блоке и перестановку. После 16 итераций в таких стандартных блоках данные размещаются согласно окончательной обратной перестановке, описанной в таблице 9.16, где, как и ранее, выходные биты читаются слева направо и сверху вниз.

Для дешифрования применяется тот же алгоритм, но ключевая последовательность, используемая в стандартном блоке, берется в обратном порядке. Отметим, что значение которое может быть также выражено через выход i-го блока как , делает процесс дешифрования возможным.

Таблица 9.14 – Функции выбора S-блока

Таблица 9.15 – Таблица перестановки

Таблица 9.16 – Окончательная перестановка

Продолжение таблицы 9.16

Выбор ключа. Выбор ключа также происходит в течение 16 итераций, как показано в соответствующей части рис.9.8. Входной ключ состоит из 64-битового блока с 8 бит четности в разрядах 8, 16, …, 64. Перестановочный выбор 1 отбрасывает биты четности и переставляет оставшиеся 56 бит согласно табл. 9.17. Выход данной процедуры делится пополам на два элемента – С и D, каждый из которых состоит из 28 бит. Выбор ключа проходит в 16 итерациях, проводимых для создания различных множеств 48 ключевых бит для каждой итерации шифрования. Блоки С и D последовательно сдвигаются согласно следующим выражениям:

Таблица 9.17 – Круговая перестановка

	(9.6)

Здесь - левый циклический сдвиг на число позиций, показанных в таблице 9.18. Затем последовательность переставляется согласно перестановочному выбору 2, показанному в таблице 9.19. Результатом является ключевая последовательность которая используется в -й итерации алгоритма шифрования.

Таблица 9.18 – Ключевая последовательность сдвигов

влево

Итерация	Количество сдвигов влево

Продолжение таблицы 9.18

Итерация	Количество сдвигов влево

Таблица 9.19 – Ключевая перестановка 2

DES может реализовываться подобно блочной системе шифрования (см. рисунок 9.8), что иногда называют методом шифровальной книги. Основным недостатком этого метода является то, что (при использовании одного ключа) данный блок входного открытого текста будет всегда давать тот же выходной шифрованный блок. Еще один способ шифрования, называемый способом шифрования с обратной связью, приводит к шифрованию отдельных битов, а не символов, что дает поточное шифрование. В системе шифрования с обратной связью (описанной ниже) шифрование сегмента открытого текста зависит не только от ключа и текущих данных, но и от некоторых предшествующих данных.