ФЕДЕРАЛЬНЫЙ СТАНДАРТ США – DES

Стандарт шифрования данных DES (Data Encryption Standart), котрый ANSI называет Алгоритмом шифрования данных DEA (Data Encryption Algorithm), а ISO – DEA-1, за 20 лет стал мировым стандартом. За годы своего существования он выдержал натиск различных атак и при известных ограничениях все еще является криптостойким.

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

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

Криптостойкость полностью определяется ключом. Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES состоит из 16 циклов (см. рис. 1.1).

В общем виде цикл преобразования представлен на рис. 1.2.

Если L_i и R_i – левая и правая половины, полученные в результате i-й итерации, К_i – 48-битный ключ для цикла i, а f – функция, выполняющая все подстановки, перестановки и XOR с ключом, то один цикл преобразования можно представить как

(L_i, R_i) = (R_i-1, L_i-1Åf (R_i-1, K_i)).

Учитывая подстановку F_i(×) и перестановку Т(×), цикл преобразования можно представить так, как это сделано на рис. 1.3.

Из рис. 1.3 видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями – подстановкой F_i(×) и перестановкой Т(×) (за исключением последнего, шестнадцатого цикла, где перестановка опускается).

Подстановка

F_i(L_i-1, R_i-1) = (R_i-1, L_i-1Åf (R_i-1, K_i))

является инволюцией, так как

F_i (F_i (L_i-1, R_i-1)) = F_i(R_i-1, L_i-1Åf (R_i-1, K_i)) =

= (R_i-1, L_i-1Å(f (R_i-1, K_i)) Å(f (R_i-1, K_i))) =

= (L_i-1, R_i-1).

В свою очередь подстановка T(L’_i, R’_i) = (R’_i, L’_i) так же является инволюцией, поскольку

Т(T(L’_i, R’_i)) = T(R’_i, L’_i) = (L’_i, R’_i).

Если обозначить начальную и завершающую перестановки как IP и IP^-1, то прямое DES преобразование (шифрование) реализует функцию

DES = IPF₁TF₂T…F₁₅TF₁₆IP^-1,

а обратное DES-преобразование (дешифрование) реализует функцию

DES^-1 = IP^-1F₁₆TF₁₅T…F₂TF₁IP.

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

То есть, если при шифровании использовались ключи К₁, К₂, К₃,… К₁₆, то ключами дешифрования будут К₁₆, К₁₅, К₁₄,… К₁. Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому легко реализуется на аппаратном уровне.

DES работает с 64-битовыми блоками открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 преобразований (функция f), в которых данные объединяются с ключом. После шестнадцатого цикла правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной). На каждом цикле (см. рис. 1.4) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции выполняются функцией f.

Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16 циклов DES.

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

Таблица 1.1

DES – начальная перестановка

 

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

Начальная перестановка и соответствующая заключительная перестановка не влияют на криптостойкость DES.

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

Таблица 1.2

DES – преобразование ключа

 

После извлечения 56-битного ключа для каждого из 16 циклов генерируется новый 48-битный подключ. Эти подключи, К_i, определяются следующим образом. Сначала 56-битный ключ делится на две 28-битные половины. Затем половины циклически сдвигаются влево на один или два бита в зависимости от номера цикла. Этот сдвиг показан в таблице 1.3.

Таблица 1.3

DES – сдвиг ключа в зависимости от номера цикла

Номер цикла

Сдвиг(бит)

 

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

Таблица 1.4

DES – перестановка со сжатием

 

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

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

Операция перестановки с расширением правой половины данных, R_i, от 32 до 48 битов и изменением их порядка, называется перестановкой с расширением. У этой операции две задачи: привести размер правой половины в соответствие с ключом для операции XOR и получить более длинный результат, который можно будет сжать в ходе операции подстановки.

 

Однако криптографический смысл данной операции состоит в том, что за счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Данная зависимость называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифртекста от каждого бита открытого текста и каждого бита ключа. Перестановка с расширением показана на рис. 1.5. Иногда она называется E-блоком (от expansion). Для каждого 4-битного входного блока первый и четвертый биты представляют собой два бита выходного блока. В таблице 1.5 показано соответствие позиций результата и исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 – в позиции 30 и 32 выходного блока. Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

Таблица 1.5

DES – перестановка с расширением

 

После объединения сжатого блока с расширенным блоком с помощью операции XOR над 48-битным результатом выполняется операция подстановки. Подстановка производится в восьми блоках, или S-блоках (от substitution). У каждого S-блока есть свой 6-битный вход и 4-битный выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти). 48 битов делятся на восемь 6-битовых подблоков. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - первым S-блоком, второй – вторым S-блоком и так далее (см. рис. 1.6).

Каждый S-блок представляет собой таблицу из четырех строк и шестнадцати столбцов. Каждый элемент в блоке является 4-битным столбцом. По шести входным битам S-блока определяется, под какими номерами столбцов и строк следует искать выходное значение. Все восемь S-блоков показаны в таблицах 1.6 – 1.13.

Таблица 1.6

DES – S-блок 1

 

Таблица 1.7

DES – S-блок 2

 

Таблица 1.8

DES – S-блок 3

 

Таблица 1.9

DES – S-блок 4

 

Таблица 1.10

DES – S-блок 5

 

Таблица 1.11

DES – S-блок 6

 

Таблица 1.12

DES – S-блок 7

 

Таблица 1.13

DES – S-блок 8

 

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b₁, b₂, b₃, b₄, b₅ и b₆. Биты b₁ и b₆ объединяются, образуя 2-битное число от 0 до 3, соответствующее строке таблицы. Средние четыре бита, с b₂ по b₅, объединяются, образуя 4-битное число от 0 до15, соответствующее столбцу таблицы. Необходимо учитывать, что строки и столбцы нумеруются с нуля, а не с единицы. Например, пусть на вход шестого S-блока (то есть биты функции XOR с 31 по 36) попадает 110011. Первый и последний биты, объединяясь, образуют 11, что соответствует строке три шестого S-блока. Средние четыре бита образуют 1001, что соответствует столбцу девять того же S-блока. Элемент шестого S-блока, находящийся на пересечении строки три и столбца девять, - это 14. В результате этой подстановки получается восемь 4-битных блоков, которые вновь объединяются в единый 32-битный блок. Этот блок поступает на вход следующего этапа – перестановки с помощью Р-блока.

32-битный выход подстановки с помощью S-блоков перетасовывается в соответствии с Р-блоком. Эта перестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой, или просто перестановкой. Позиции, в которые перемещаются биты, показаны в таблице 1.14. Например, двадцать первый бит перемещается в позицию четыре, а четвертый бит – в позицию тридцать один.

Таблица 1.14

DES – перестановка с помощью Р-блока

 

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

Заключительная перестановка является обратной по отношению к первоначальной и описана в таблице 1.15.

Таблица 1.15

DES – заключительная перестановка

 

Отметим, что левая и правая части не меняются местами после завершения последнего цикла DES, вместо этого объединенный блок R₁₆L₁₆ используется как вход заключительной перестановки. Перестановка половин с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм шифрования можно было использовать как для шифрования, так и для дешифрования.

Алгоритм, который создает ключ для каждого цикла, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.