Алгоритм DES и его варианты

Прошло уже белее 30 лет с даты принятия алгоритма DES в качестве стандарта шифрования США. DES — алгоритм шифрования с наиболее богатой и интересной историей.

История создания алгоритма

Один из наиболее известных в мире криптологов Брюс Шнайер в своей знаменитой книге «Прикладная криптография» [28] так описал проблемы пользователей средств защиты информации в начале 70-х гг. XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»):

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

?     практически любое средство шифрования представляло собой «черный ящик» с достаточно неясным содержимым: какой алгоритм шифрования используется, насколько он является криптографически стойким, грамотно ли он реализован, корректно ли создаются, хранятся, используются ключи шифрования, нет ли в средстве вставленных разработчиками недокументированных возможностей и т. д., — вся эта весьма важная информация для подавляющего большинства покупателей криптографических средств была недоступна.

Данной проблемой озаботилось Национальное Бюро Стандартов (National Bureau of Standards, NBS) США. В результате в 1973 г. был объявлен первый в истории открытый конкурс на стандарт шифрования. NBS было готово исследовать с целью выбора стандарта алгоритмы-претенденты, удовлетворяющие следующим критериям:

?      алгоритм должен быть криптографически стойким;

?      алгоритм должен быть быстрым;

П структура алгоритма должна быть четкой и ясной;

?     стойкость шифрования должна зависеть только от ключа, сам алгоритм не должен быть секретным;

?      алгоритм должен быть легко применим для различных целей;

?     алгоритм должен легко реализовываться аппаратно на существующей элементной базе.

Предполагалось, что заинтересованные организации или специалисты будут присылать в NBS подробные спецификации алгоритмов, достаточные для их реализации, т. е. не имеющие каких-либо «белых пятен». Предполагалось также, что алгоритм будет сертифицирован NBS для всеобщего использования, с него будут сняты все патентные и экспортные ограничения, в результате чего такой стандарт должен будет решить все проблемы совместимости средств шифрования. Кроме того, NBS брало на себя функции сертификации средств шифрования — т. е. «черные ящики» должны были безвозвратно уйти в прошлое.

Фактически алгоритм-претендент оказался всего один: это был разработанный фирмой ШМ алгоритм шифрования Lucifer {см. разд. 3.31). В течение двух лет проводилась доработка алгоритма:

?      во-первых, NBS совместно с Агентством Национальной Безопасности (АНБ, NSA — National Security Agency) США был проведен тщательный анализ алгоритма, результатом которого явилась его достаточно существенная переработка;

?      во-вторых, принимались к рассмотрению комментарии и критические замечания от всех заинтересованных организаций и частных лиц.

В результате совместной деятельности IBM, NBS и АНБ в январе 1977 г. DES был опубликован как стандарт США (последняя версия этого стандарта — в документе [150]) на алгоритм шифрования данных (кроме информации повышенной степени секретности). Алгоритм DES был запатентован фирмой ЮМ, однако NBS получило, фактически, бесплатную и неограниченную лицензию на использование данного алгоритма [150]. Альтернативное, но реже используемое название алгоритма — DEA (Data Encryption Algorithm).

Основные характеристики и структура алгоритма

Алгоритм DES шифрует информацию блоками по 64 бита с помощью 64- битного ключа шифрования, в котором используется только 56 битов (процедура расширения ключа подробно описана далее).

Шифрование информации выполняется следующим образом (рис. 3.56):

1. Над 64-битным блоком данных производится начальная перестановка согласно табл. 3.16.

Таблица 3.16

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

Таблица трактуется следующим образом: значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита — в бит 2 и т. д.



2. Результат предыдущей операции делится на 2 субблока по 32 бита (на

рис. 3.56 обозначены А0 и В0), над которыми производятся 16 раундов

следующих преобразований:

Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 битов. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом [150]. Процедура извлечения 56 значащих битов 64-битного ключа на рис. 3.59 обозначена как Е. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно табл. 3.19 и 3.20.


Таблица 3.19

57

49

41

33

25

17

9

1

58

50

42

34

26

18

10

2

59

51

43

35

27

19

11

3

60

52

44

36

Таблица 3.20

63

55

47

39

31

23

15

7

62

54

46

38

30

22

14

6

61

53

45

37

29

21

13

5

28

20

12

4


В результате перестановки формируются два 28-битных значения С и D. Таблица 3.19 определяет выборку битов ключа для С, табл. 3.20 — для D.

Затем выполняются 16 раундов преобразований, каждый из которых дает один из ключей раундов Kt. В каждом раунде процедуры расширения ключа производятся следующие действия:

1.    Текущие значения С и D циклически сдвигаются влево на переменное число битов п. Для раундов 1, 2, 9 и 16 п = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.

2.     С и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда К(. Сжимающая перестановка выполняется согласно табл. 3.21.

Таблица 3.21

14

17

11

24

1

5

3

28

15

6

21

10

23

19

12

4

26

8

16

7

27

20

13

2

41

52

31

37

47

55

30

40

51

45

33

48

44

49

39

56

34

53

46

42

50

36

29

32

При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на п битов, где гс’ = 0 для первого раунда, и’=1 для раундов 2, 9, 16 и п= 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифровывания ключи раундов .

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

2 коммент. »

 
 

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100