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

Бывший стандарт шифровании данных США — DES

Несмотря на то, что с мая 2002 г. в США в силу вступил новый стандарт шифрования данных AES, предыдущий стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет алгоритмом шифрования данных DEA (Data Encryption Algorithm), a ISO — DEA-1, остается одним из самых известных алгоритмов. Можно даже сказать, что в настоящий момент алгоритм шифрования DES используется в основном для обучения специалистов по защите информации, являясь открытым, и в то же время стойким алгоритмом шифрования. В том числе до сих пор широко используется схема тройного алгоритма DES с двумя ключами. За годы своего существования алгоритм выдержал натиск различных атак и утратил свою былую силу лишь потому, что вычислительная мощность за 25 лег использования DES в качестве стандарта выросла во много раз. Так, если во время разработки шифра перебор всех вариантов секретного ключа занял бы несколько сотен лет при использовании самого мощного компьютера того времени, то в настоящий момент иа это требуются считанные часы при использовании самого мощного из существующих суперкомпьютеров.

DES представляет собой блочный симметричный шифр, построенный по схеме Фейстеля, и преобразует 64-битовый блок исходных данных в блок шифрованных данных такой же длины под воздействием секретного ключа шифрования, длина которого равна 56 бит.

Так как DES является симметричным алгоритмом, то для шифрования и расшифрования используются одинаковые алгоритмы с той лишь разницей, что при расшифровании раундовыс подключи используются в обратном порядке. То есть, если при шифровании использовались раундовые подключи К|, К₂, К₃,… К|6, го подключами расшифрования соответственно будут K_i6, К]5, К|₄,… Ki. Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.

Длина секретного ключа равна 56 битам. Ключ обычно представляется 64-битным числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.

Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES работает с 64- битовыми блоками открытого текста и состоит из 16 раундов. Работа алгоритма начинается с первоначальной перестановки, выполняемой до начала работы раундов шифра в соответствии с табл. 6. В оригинале описания данная перестановка названа IP (от англ. Initial Permutation).

Эту и все последующие таблицы для алгоритма DES следует читать слева направо и сверху вниз. Например, начальная перестановка перемещает бит 58 в позицию 1, бит 50 — в позицию 2, бит 42 — в позицию 3 и так далее.

Таблица 6.

Начальная перестановка.

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

В каждом раунде правая половина данных увеличивается с 32 до 48 битов путем дублирования некоторых битов с помощью перестановки с расширением в соответствии с табл. 7.

Расширенные данные объединяются с 48-битным раундовым подключом посредством сложения по модулю 2 (операция XOR), после чего проходит через восемь S-блоков замены. На вход каждого S-блока поступает 6-битный вход и в результате замены образуется 4-битный выход. Всего используется восемь различных S-блоков. Каждый S-блок представляет собой таблицу из четырех строк и шестнадцати столбцов. Каждый элемент в блоке является 4-битным столбцом. По шести входным битам S-блока определяется, под какими номерами столбцов и строк следует искать выходное значение. Первый из восьми Sблоков показан в табл. 8. Остальные блоки замены легко можно найти в книгах и справочниках по криптографии, например, в работах [2, 6 — 9].

Таблица 7.

Перестановка с расширением.

Таблица 8.

Блок Si.

Входные биты особым образом определяют элемент Sблока. Рассмотрим 6-битовый вход S-блока: Ь_ь Ь₂, Ь₃, Ь₄, Ь₅ и Ь₆. Биты bi и Ьб объединяются, образуя 2-битное число от 0 до 3, соответствующее строке таблицы. Средние четыре бита, с Ь₃ по Ь₅, объединяются, образуя 4-битное число от 0 до15, соответствующее столбцу таблицы. Необходимо учитывать, что строки и столбцы нумеруются с нуля, а не с единицы. Например, пусть на вход блока Si попадает значение 110 011. Первый и последний биты, объединяясь, образуют 11, что соответствует строке 3 блока S|. Средние 4 бита образуют 1001, что соответствует столбцу 9 того же S-блока. Элемент блока Si, находящийся на пересечении строки 3 и столбца 9, — это 11, т. е. на выходе будет образовано значение 1011 (рис. 12).

Рис. 11. Общий вид работы алгоритма шифрования DES.

В результате подстановки с помощью восьми блоков замены получается восемь 4-битных блоков, которые вновь объединяются в единый 32-битный блок. Этот блок поступает на вход следующего этапа — перемешивания с использованием Рперсстановки. Эта перестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой, или просто перестановкой. Перестановка выполняется в соответствии с табл. 9. Например, бит 21 перемещается в позицию 4, а бит 4 — в позицию 31.

Рис. 12. Пример работы S-блока замены.

Таблица 9.

Перестановка Р.

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

Результат функции F объединяется с левой половиной с помощью операции сложения по модулю 2 (XOR). В итоге этих действии появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 15 раз, образуя 15 циклов DES. В последнем, шестнадцатом раунде выполняются все те же действия за тем исключением, что правая и левая части местами нс меняются.

Рис. 13. Функция F.

После 16 раундов преобразования выполняется заключительная перестановка, которая является обратной по отношению к первоначальной и преобразует данные в соответствии с табл. 10. В оригинале описания данная перестановка обозначена как IP"¹.

Начальная перестановка IP и заключительная перестановка IP ¹ связаны между собой. Говорят, что они взаимно-обратны.

Это означает, что если вы к некоторому сообщению X примените сначала одну перестановку, а затем вторую, то в результате такого действия вы получите исходное сообщение X. И при этом не важно, какую из перестановок вы будете применять первой, а какую последней. То есть:

Таблица 10.

Заключительная перестановка.

И действительно, если начальная перестановка (см. табл. 6) переставляет бит 58 в позицию 1, бит 50 в позицию 1, бит 42 — в позицию 3; то заключительная перестановка (табл. 10) возвращает их на места, переставляя бит 1 в позицию 58, бит 2 в позицию 50, бит 3 в позицию 42 и г. д.

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

Таблица 11.

Начальное преобразование ключа.

После извлечения 56-битного ключа для каждого раунда шифрования генерируется новый 48-битный подключ Kj следующим образом. Сначала 56-битный ключ делится на две 28- битные половины. Затем половины циклически сдвигаются влево на один или два бита в зависимости от номера раунда. Зависимость величины сдвига от номера раунда показана в табл. 12.

Таблица 12.

Сдвиг ключа при выработке подключей для шифрования.

После сдвига выбирается 48 битов из 56. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция получила название перестановка со сжатием. Ее результатом является набор из 48 бит. Перестановка со сжатием выполняется в соответствии с табл. 13.

Таблица 13.

Перестановка со сжатием.

Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбрасывается.

Схема выработки раундовых подключей показана на рис. 14.

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

Рис. 11. Схема выработки раундовых подключей.

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

Таблица 14.

Сдвиг ключа при выработке подключей для расшифрования.

Это интересно

Для алгоритма DES существует ряд слабых и условно слабых подключей. Слабых ключей четыре. Это такие ключи, которые позволяют выработать 16 абсолютно идентичных раундовых подключи. Если представить ключ в 16-ричном виде, то эти 4 слабых ключа будут выглядеть следующим образом: 0101 0101 0101 0101 1F1F1F1 °F 1F1F1F1 °F ЕОЕО ЕОЕО ЕОЕО ЕОЕО FEFE FEFE FEFE FEFE

После первоначальной перестановки данные ключи разделятся на две 28-битовых половинки, каждая из которых будет выглядеть следующим образом соответственно для каждого из ключей:

0 0 0 FFFFFFF FFFFFFF 0 FFFFFFFFFFFFFF

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

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

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