Лабораторная работа №3. Изучение принципов создания блочных шифров на примере алгоритма DES

Целью лабораторной работы является изучение принципов построения блочных шифров, основанных на сети Фейстеля, на примере алгоритма DES.

Требования к содержанию, оформлению и порядку выполнения

Отчет по выполнению лабораторной работы должен содержать: титульный лист, название работы, цель работы и содержательную часть.

В содержательной части отчета по выполнению лабораторной работы требуется привести:

· общее описание алгоритма DES;

· результаты шифрования сообщения на заданном ключе (сообщение и ключ определяются индивидуальным заданием);

· выводы по лабораторной работе.

Теоретическая часть

Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES(Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46).

В основу алгоритма DES положена классическая сеть Фейстеля с двумя ветвями (см. раздел 3.1). Он осуществляет шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит – проверочные биты для контроля на четность). Обобщенная схема процесса шифрования в алгоритме DES показана на рис. Л3.1. Этот процесс заключается в начальной перестановке битов 64-битового блока, шестнадцати раундах шифрования и, наконец, в конечной перестановке битов.

При описании алгоритма DES применены следующие обозначения:

· L и R – последовательности битов (левая (left) и правая (right));

· LR – конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

· Å – операция побитового сложения по модулю 2.

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помощью матрицы начальной перестановки IP (табл. Л3.1).

 

Рис. Л3.1. Структура алгоритма DES.

 


Таблица Л3.1

Матрица начальной перестановки IP

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

 

Биты входного блока Т (64 бита) переставляются в соответствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50 – битом 2 и т.д. Эту перестановку можно описать выражением Т0 = IP(Т). Полученная последовательность битов Т0 разделяется на две последовательности: L0 – левые или старшие биты, R0 – правые или младшие биты, каждая из которых содержит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 раундов. Пусть Тi , – результат i-й итерации:

Тi = Li Ri

где Li=t1, t2,…,t32 (первые 32 бита), Ri=t33, t34,…,t64 (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

Li = Ri–1, i = 1, 2,…,16;

Ri== Li–1 Å f(Ri–1, Ki), i = 1, 2,…,16.

Функция f называется функцией шифрования. Ее аргументами являются последовательность Ri–1, получаемая на предыдущем шаге итерации, и 48-битовый раундовый подключ Ki который является результатом преобразования 64-битового ключа шифра К.

На последнем шаге итерации получают последовательности R16 и L16 , которые конкатенируются в 64-битовую последовательность R16 L16.

По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы обратной перестановки IP –1 (табл. Л3.2).

Таблица Л3.2

Матрица обратной перестановки IP –1

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

Процесс расшифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, который подвергается начальной перестановке IP, затем следуют 16 раундов преобразования, но ключи Ki используются в обратной последовательности: K16 используется на первом раунде, K1 используется на последнем раунде. После последнего раунда процесса расшифрования две половины выхода меняются местами и подвергаются обратной перестановке IP –1. Выходом этой стадии является незашифрованный текст.

Схема вычисления функции шифрования f(Ri–1, Ki) показана на рис. Л3.2.

 

Рис. Л3.2. Схема вычисления функции шифрования f.

 

Для вычисления значения функции f используются:

· функция E (расширение 32 бит до 48);

· функция S1 , S2 ,..., S8 (преобразование 6-битового числа в 4-битовое);

· функция P (перестановка битов в 32-битовой последовательности).

Аргументами функции шифрования f являются Ri–1 (32 бита) и Ki (48 бит). Результат функции E(Ri–1) есть 48-битовое число. Функция расширения E, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), определяется табл. Л3.3.

В соответствии с этой таблицей первые три бита E(Ri–1) – это биты 32, 1 и 2, а последние – 31, 32, 1. Полученный результат складывается по модулю 2 (операция XOR) с текущим значением ключа Ki и затем разбивается на восемь 6-битовых блоков B1 , B2 ,…, B8:

E(Ri–1) Å Ki.= B1 , B2 ,…, B8 .

Таблица Л3.3

Функция расширения E

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

 

Далее каждый из этих блоков используется как номер элемента в функциях-матрицах (S–блоках): S1 , S2 ,..., S8 , содержащих 4-битовые значения (табл. Л3.4).

Следует отметить, что выбор элемента в матрице Sj , осуществляется достаточно оригинальным образом. Пусть на вход матрицы Sj; поступает 6-битовый блок Bj =b1 b2 b3 b4 b5 b6 , тогда 2-битовое число b1 b6 указывает номер строки матрицы, а 4-битовое число b2 b3 b4 b5 – номер столбца.

Например, если на вход матрицы S1 поступает 6-битовый блок

B1 =b1 b2 b3 b4 b5 b6 = 100110,

то 2-битовое число b1 b6= 10(2)=2(10) указывает строку с номером 2 матрицы S1, а 4-битовое число b2 b3 b4 b5=0011(2)=3(10) – указывает столбец с номером 3 матрицы S1. Это означает, что в матрице S1 блок B1 = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8(10) = 1000(2) . Совокупность 6-битовых блоков B1 , B2 ,…, B8 обеспечивает выбор 4-битового элемента в каждой из матриц S1 , S2 ,..., S8.

В результате получаем S1(B1), S2(B2),...,S8(B8), т.е. 32-битовый блок. Этот 32-битовый блок преобразуется с помощью функции перестановки битов P (табл. Л3.5).

Таким образом, функция шифрования есть

f(Ri–1,Ki) = P(S1(B1), S2(B2),…,S8(B8)).

На каждой итерации используется новое значение ключа Ki (длиной 48 бит). Новое значение ключа Ki вычисляется из начального ключа K (рис. Л3.3). Ключ K представляет собой 64-битовый блок с 8 битами контроля по четности, расположенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. Л3.6).

Таблица Л3.6 разделена на две части. Результат преобразования G(K) разбивается на две половины C0 и D0 по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются биты последовательности C0 (первым битом C0 будет бит 57 ключа шифра, затем бит 49 и т.д., а последними битами – биты 44 и 36 ключа). Следующие четыре строки матрицы G определяют, как выбираются биты последовательности D0 (т.е. последовательность D0 будет состоять из битов 63, 55, 47, ...,12, 4 ключа шифра).

Таблица Л3.4

Функции преобразования S1 , S2 ,..., S8

    Номер столбца
     
   
  S1
   
   
   
  S2
   
   
Н  
о S3
м  
е  
р  
  S4
   
   
   
с S5
т  
р  
о  
к S6
и  
   
   
  S7
   
   
   
  S8
   
   

 

Таблица Л3.5

Функция перестановки битов P

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

 

Рис. Л3.3. Схема алгоритма вычисления ключей.

 

Таблица Л3.6

Функция G первоначальной подготовки ключа

(переставленная выборка 1)

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

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

 

Как видно из табл. Л3.6, для генерации последовательностей C0 и D0 не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56-битовым.

После определения C0 и D0 рекурсивно определяются Ci и Di,
i=1, 2,…,16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в табл. Л3.7.

Таблица Л3.7

Таблица сдвигов для вычисления ключа

Номер итерации Количество сдвигов влево Номер итерации Количество сдвигов влево

 

Операции сдвига выполняются для последовательностей Ci и Di независимо. Например, последовательность C3 получается посредством циклического сдвига влево на две позиции последовательности C2 , а последовательность D3 – посредством сдвига влево на две позиции последовательности D2 , C16 и D16 получаются из C15 и D15 посредством сдвига влево на одну позицию.

Ключ Ki , определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последовательности Ci Di и их перестановки. Другими словами, ключ Ki = H(Ci Di ), где функция Н определяется матрицей, завершающей обработку ключа (табл. Л3.8).

Таблица Л3.8

Функция Н завершающей обработки ключа

(переставленная выборка 2)

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

 

Как следует из табл. Л3.8, первым битом ключа Ki будет 14-й бит последовательности Ci Di , вторым – 17-й бит, 47-м битом ключа Ki , будет 29-й бит Ci Di , а 48-м битом – 32-й бит Ci Di.

Общая постановка задачи

В лабораторной работе требуется:

1. Изучить раздел 3.1 и теоретическую часть к данной лабораторной работе.

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

Для выполнения этого задания следует воспользоваться программой DES Tutorial, разработанной Кабановым Е.В. и Прокоповым М.В. (см. рис. Л3.4), которую Вы можете взять в приложении №2 данного УМК.

 

Рис. Л3.4. Окно "О программе" DES Tutorial.

 

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

DES Tutorial позволяет пользователю работать в 2 режимах:

1) Режим тестирования – программа вместе с пользователем проводит процесс шифрования данных. В этом режиме программа поэтапно выполняет шифрование данных и просит пользователя закончить за нее работу на том или ином этапе.

2) Режим шифрования/расшифрования – программа зашифровывает и расшифровывает текстовые строки, используя введенный ключ. В этом режиме программа сама выполняет шифрование и дешифрование данных.

Режим тестирования предусматривает следующие задания:

· Тест 1 "Начальная перестановка";

· Тест 2 "Получение последовательностей R0 и L0";

· Тест 3 "Функция выборки и перестановки ключевой последовательности G";

· Тест 4 "Получение последовательностей C0 и D0";

· Тест 5 "Получение последовательности Ci";

· Тест 6 "Получение последовательности Di";

· Тест 7 "Получение последовательности Ki (ключа раунда i)";

· Тест 8 "Функция E";

· Тест 9 "Функции Si";

· Тест 10 "Функция шифрования f";

· Тест 11 "Конечная перестановка".

Для своих индивидуальных данных необходимо без ошибок пройти все предусмотренные программой тесты и их результаты привести в отчет.