Протоколы Internet

         

Алгоритм DES


6.4.1 Алгоритм DES

Семенов Ю.А. (ГНЦ ИТЭФ)

Стандарт шифрования DES (Data Encryption Standard) был разработан в 1970-х годах, он базируется на алгоритме 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 бит. Такая длина ключа соответствует 1017 комбинаций, что обеспечивало до недавнего времени достаточный уровень безопасности. В дальнейшем можно ожидать расширения ключа до 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-разрядные части L0 и R0. Далее 16 раз повторяются следующие 4 процедуры:

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


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

    Выполняется операция XOR для Ri f(A,J), результат обозначается Ri+1.

    Выполняется операция присвоения Li+1=Ri.

    Структурная схема реализации алгоритма 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 аппаратным образом, что обеспечивает довольно высокое быстродействие.

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



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

    Для описания алгоритма вычисления ключей Kn (функция 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



    PC-1 (Выбор 1)



    PC-2 (Выбор 2)

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



    Номер итерации



    Число сдвигов влево

    1 1
    2 1
    3 2
    4 2
    5 2
    6 2
    7 2
    8 2
    9 1
    10 2
    11 2
    12 2
    13 2
    14 2
    15 2
    16 1

    Содержание раздела