Лабораторная работа №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 и т.д. Эту перестановку можно описать выражением Т₀ = IP(Т). Полученная последовательность битов Т₀ разделяется на две последовательности: L₀ – левые или старшие биты, R₀ – правые или младшие биты, каждая из которых содержит 32 бита.

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

Т_i = L_i R_i

где L_i=t₁, t₂,…,t₃₂ (первые 32 бита), R_i=t₃₃, t₃₄,…,t₆₄ (последние 32 бита). Тогда результат i -й итерации описывается следующими формулами:

L_i = R_i_–1, i = 1, 2,…,16;

R_i== L_i–1 Å f(R_i–1, K_i), i = 1, 2,…,16.

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

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

По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы обратной перестановки 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 раундов преобразования, но ключи K_i используются в обратной последовательности: K ₁₆ используется на первом раунде, K ₁ используется на последнем раунде. После последнего раунда процесса расшифрования две половины выхода меняются местами и подвергаются обратной перестановке IP ^–1. Выходом этой стадии является незашифрованный текст.

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

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

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

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

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

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

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

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

E(R_i_–1) Å K_i. = B₁, B₂,…, B₈.

Таблица Л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 –блоках): S₁, S₂,..., S₈, содержащих 4-битовые значения (табл. Л3.4).

Следует отметить, что выбор элемента в матрице S_j, осуществляется достаточно оригинальным образом. Пусть на вход матрицы S_j; поступает 6-битовый блок B_j =b₁b₂b₃b₄b₅b₆, тогда 2-битовое число b₁b₆ указывает номер строки матрицы, а 4-битовое число b₂b₃b₄b₅ – номер столбца.

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

B₁ =b₁b₂b₃b₄b₅b₆= 100110,

то 2-битовое число b₁b₆= 10₍₂₎=2₍₁₀₎ указывает строку с номером 2 матрицы S₁, а 4-битовое число b₂b₃b₄b₅= 0011₍₂₎=3₍₁₀₎ – указывает столбец с номером 3 матрицы S₁. Это означает, что в матрице S₁ блок B₁ = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8₍₁₀₎ = 1000₍₂₎. Совокупность 6-битовых блоков B₁, B₂,…, B₈ обеспечивает выбор 4-битового элемента в каждой из матриц S₁, S₂,..., S₈.

В результате получаем S ₁(B ₁), S ₂(B ₂), ..., S₈(B ₈), т.е. 32-битовый блок. Этот 32-битовый блок преобразуется с помощью функции перестановки битов P (табл. Л3.5).

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

f(R_i_–1,K_i) = P(S₁(B₁), S₂(B₂),…,S₈(B₈)).

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

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

Таблица Л3.4

Функции преобразования S₁, S₂,..., S₈

Номер столбца

S ₁

S ₂

S ₃

S ₄

S ₅

S ₆

S ₇

S ₈

Таблица Л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, для генерации последовательностей C₀ и D₀ не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56-битовым.

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

Таблица Л3.7

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

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

Операции сдвига выполняются для последовательностей C_i и D_i независимо. Например, последовательность C₃ получается посредством циклического сдвига влево на две позиции последовательности C₂, а последовательность D₃ – посредством сдвига влево на две позиции последовательности D₂, C₁₆ и D₁₆ получаются из C₁₅ и D₁₅ посредством сдвига влево на одну позицию.

Ключ K_i, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последовательности C_i D_i и их перестановки. Другими словами, ключ K_i = H(C_i D_i), где функция Н определяется матрицей, завершающей обработку ключа (табл. Л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, первым битом ключа K_i будет 14-й бит последовательности C_i D_i, вторым – 17-й бит, 47-м битом ключа K_i, будет 29-й бит C_i D_i, а 48-м битом – 32-й бит C_i D_i.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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