Алгоритм шифрования DES

 

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

Следует отметить, что все приводимые таблицы являются стандартными и должны включаться в реализацию алгоритма DES в неизменном виде.

Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа.

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

L и R — последовательности битов. (левая и правая).

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

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

 

Таблица 4.1.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

 

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

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

Т_i= L_iR_i,

где L_i=t₁t₂…t₃₂ (первые 32 бита),

R_i=t₃₃t₃₄…t₆₄ (последние 32 бита).

Тогда результат i-той операции описывается следующими формулами:

;

.

 

 

Рисунок 4.1.1 — Структура алгоритма DES

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

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

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

 

Таблица 4.1.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

 

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке.

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f(R_i-1,K_i) показана ниже.

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

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

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

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

 

 

 

Рисунок 4.1.2 — Схема вычисления функции шифрования

 

Таблица 4.1.3 — Функция расширения Е

 

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

 

Таблица 4.1.4 — Функция 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

 

Таблица 4.1.5 — Функции преобразования S₁, S₂, … S₈

 

		Номер столбца
		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	4	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
	0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
	1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
	2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
	3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9
	0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
	1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
	2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
	3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12
	0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
	1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
	2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
	3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14
	0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
	1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
	2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
	3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3
	0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
	1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
	2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	1	6
	3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13
	0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
	1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
	2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
	3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12
	0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
	1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
	2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
	3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

 

Рисунок 2.13 — Схема алгоритма вычисления ключей К_i

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

 

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

 

Данная таблица разделена на две части. Результат преобразования G(K) разбивается на две половины С₀ и D₀ по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются биты последовательности С₀.

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности.

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

После определения С₀  и D₀ рекурсивно определяются С_i  и D_i, i = 1,2…16.

Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации.

Операции сдвига выполняются для последовательностей С_i  и D_i независимо.

Таблица 4.1.7 — Таблица количества сдвигов

 

Номер итерации	Количество Si сдвигов влево, бит	Номер итерации	Количество Si сдвигов влево, бит
1	1	9	1
2	1	10	2
3	2	11	2
4	2	12	2
5	2	13	2
6	2	14	2
7	2	15	2
8	2	16	1

 

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

 

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

 

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