UP: 6.4 Системы шифрования     Next: 6.4.2 Алгоритм шифрования RSA

6.4.1 Алгоритм DES

Семенов Ю.А. (ИТЭФ-МФТИ)
Yu. Semenov (ITEP-MIPT)

Стандарт шифрования DES (Data Encryption Standard) был разработан в 1975 году компанией IBM, он базируется на алгоритме DEA.

Исходные идеи алгоритма шифрования данных DEA (data encryption algorithm) были предложены компанией IBM еще в 1960-х годах и базировались на идеях, описанных Клодом Шенноном в 1940-х годах. Первоначально эта методика шифрования называлась lucifer (разработчик Хорст Фейштель, название dea (см. http//:snoopy.falkor.gen.nz/~rae/des.html) она получила лишь в 1976 году. Lucifer был первым блочным алгоритмом шифрования, он использовал блоки размером 128 бит и 128-битовый ключ. По существу этот алгоритм являлся прототипом DEA. В 1986 в Японии (NIT) разработан алгоритм FEAL(Fast data Encipherment ALgorithm), предназначенный для использования в факсах, модемах и телефонах (длина ключа до 128 бит). Существует и ряд других разработок.

DEA (ANSI x3.92-1981; www.cryptosoft.com/html/fips46-2.htm) оперирует с блоками данных размером 64 бита и использует ключ длиной 56 бит. Такая длина ключа соответствует 10¹⁷ комбинаций, что обеспечивало до недавнего времени достаточный уровень безопасности. В дальнейшем можно ожидать расширения ключа до 64 бит (например, LOKI) или вообще замены DES другим стандартом.

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

Вводится функция f, которая работает с 32-разрядными словами исходного текста (А) и использует в качестве параметра 48-разрядный ключ (J). Схеме работы функции f показана на рис. 6.4.1.1. Сначала 32 входные разряда расширяются до 48, при этом некоторые разряды повторяются. Схема этого расширения показана ниже (номера соответствуют номерам бит исходного 32-разрядного кода).

32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

Для полученного 48-разрядного кода и ключа выполняется операция исключающее ИЛИ (XOR). Результирующий 48-разрядный код преобразуется в 32-разрядный с помощью S-матриц. На выходе S-матриц осуществляется перестановка согласно схеме показанной ниже (числа представляют собой порядковые номера бит).

16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25

Рис. 6.4.1.1. Алгоритм работы функции f

Преобразование начинается с перестановки бит (IP - Initial Permutation) в 64-разрядном блоке исходных данных. 58-ой бит становится первым, 50-ый - вторым и т.д. Схема перестановки битов показана ниже.

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

Полученный блок делится на две 32-разрядные части L₀ и R₀. Далее 16 раз повторяются следующие 4 процедуры:

• Преобразование ключа с учетом номера итерации i (перестановки разрядов с удалением 8 бит, в результате получается 48-разрядный ключ)

Пусть A=L_i, а J - преобразованный ключ. С помощью функции f(A,J) генерируется 32-разрядный выходной код.
Выполняется операция XOR для R_i f(A,J), результат обозначается R_i+1.
Выполняется операция присвоения L_i+1=R_i.

Структурная схема реализации алгоритма dea показана на рис. 6.4.1.2.

Рис. 6.4.1.2. Структурная схема реализации алгоритма DEA

Инверсная перестановка разрядов предполагает следующее размещение 64 бит зашифрованных данных (первым битом становится 40-ой, вторым 8-ой и т.д.).

40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25

S-матрицы представляют собой таблицы содержащие 4-ряда и 16 столбцов. Матрица S(1) представлена ниже (эта матрица, также как и те, что приведены в ссылке 2, являются рекомендуемыми).

No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Исходный 48-разрядный код делится на 8 групп по 6 разрядов. Первый и последний разряд в группе используется в качестве адреса строки, а средние 4 разряда - в качестве адреса столбца. В результате каждые 6 бит кода преобразуются в 4 бита, а весь 48-разрядный код в 32-разрядный (для этого нужно 8 S-матриц). Существуют разработки, позволяющие выполнять шифрование в рамках стандарта DES аппаратным образом, что обеспечивает довольно высокое быстродействие.

Преобразования ключей K_n (n=1,…,16; K_n = KS(n,key), где n - номер итерации) осуществляются согласно алгоритму, показанному на рис. 6.4.1.3.

Рис. 6.4.1.3. Алгоритм вычисления последовательности ключей K_n

Для описания алгоритма вычисления ключей K_n (функция KS) достаточно определить структуру “Выбора 1” и “Выбора 2”, а также задать схему сдвигов влево (табл. 6.4.1.2). “Выбора 1” и “Выбора 2” представляют собой перестановки битов ключа (PC-1 и PC-2; табл. 6.4.1.1). При необходимости биты 8, 16,…, 64 могут использоваться для контроля четности.

Для вычисления очередного значения ключа таблица делится на две части С0 и D0. В С0 войдут биты 57, 49, 41,…, 44 и 36, а в D0 - 63, 55, 47,…, 12 и 4. Так как схема сдвигов задана (табл. 6.4.1.2) C1,D1; Cn, Dn и так далее могут быть легко получены из C0 и D0. Так, например, C3 и D3 получаются из C2 и D2 циклическим сдвигом влево на 2 разряда

Таблица 6.4.1.1

Таблица 6.4.1.2