Криптоалгоритм DES. Тема 4.2

1.

1
Тема 4.2
Криптоалгоритм DES

2.

Содержание
1. Общая характеристика блочных шифров
2. Криптоалгоритм DES
2

3.

3
1. Криптоалгоритм DES

4.

История создания
4
Официальная история стандарта шифрования США началась в 1972 г. с
того, что национальное бюро стандартов (НБС, National Bureau of
Standards, NBS) США выдвинуло программу разработки системы
стандартов по защите от НСД к данным, хранящимся и
обрабатываемым на ЭВМ.
Это направление было признано одной из самых приоритетных
областей, остро нуждающейся в регламентирующих документах.
Одним из важнейших направлений была признана разработка
стандартного алгоритма шифрования.
Шифр DES (Data Encryрtion Standard) был разработан фирмой IBM и
сертифицирован NSA (Национальное Агентство Безопасности США).
В 1977 г. принят в качестве федерального стандарта США
Национальным институтом стандартов и технологий и в течение
двух десятилетий считался достаточно надежным и
универсальным.

5.

История создания
Стандарт DES предназначен для защиты от НСД к важной, но
несекретной информации в государственных и коммерческих
организациях США.
К настоящему времени DES является наиболее распространенным
алгоритмом, используемым в системах защиты коммерческой
информации.
Более того, реализация алгоритма DES в таких системах
становится признаком хорошего тона.
5

6.

Алгоритм DES
6
Основные достоинства алгоритма DES:
используется только один ключ длиной 56 бит,
что требует от злоумышленника перебора
256 7,2·1016 возможных ключевых комбинаций.
зашифровав сообщение с помощью одного пакета
программ, для расшифровки можно использовать любой
другой пакет программ, соответствующий стандарту
DES;
относительная простота алгоритма обеспечивает
высокую скорость обработки.

7.

Алгоритм DES
Недостатки алгоритма DES:
битовые операции в узлах замены неэффективно
реализуются программным путем;
короткая длина ключа (56 бит),
что позволяет организовать полный перебор;
современные технические средства криптоанализа позволяют
взломать шифр DES за несколько часов;
поэтому использовать их для серьезных приложений
нецелесообразно;
обнаружена теоретическая возможность уменьшить
пространство перебора с помощью
дифференциального криптоанализа (с выбором
шифрограммы)
и линейного криптоанализа (с известным сообщением),
если известно достаточно много (порядка 247) пар сообщениешифрограмма;
независимый выбор подключей практически не
увеличивает стойкость алгоритма.
7

8.

Алгоритм DES
8
Общие принципы шифрования и дешифрования алгоритма
DES показаны на рисунке.
На стороне шифрования DES принимает 64-битовый исходный
текст и порождает 64-битовый зашифрованный текст;
на стороне дешифрования DES принимает 64-битовый
зашифрованный текст и порождает 64-битовый исходный текст;
на обеих сторонах для шифрования и дешифрования
применяется один и тот же 56-битовый ключ.

9.

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

10.

Обобщенная схема зашифровывания
10
Алгоритм DES использует комбинацию подстановок и
перестановок.
DES осуществляет зашифровывание 64-битовых блоков
данных с помощью 64-битого ключа, в котором
значащими являются 56 бит,
остальные 8 бит – проверочные биты для контроля на
четность.
Расшифровывание в DES является операцией, обратной
шифрованию,
и выполняется путем повторения операций
зашифровывания в обратной последовательности.

11.

Алгоритм шифрования DES
Схема алгоритма
шифрования:
11

12.

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

13.

Алгоритм шифрования DES
13
Пусть из файла исходного текста считан 64-битовый блок T0.
Он преобразуется в соответствии с матрицей помощью
начальной перестановки IP (табл. ):
бит 58 входного блока T0 становится битом 1,
бит 50 – битом 2 и т.д.
Эту перестановку можно описать выражением T0=IP(T).
Начальная перестановка 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

14.

Алгоритм шифрования DES
14
Полученная последовательность бит T0 разделяется на
две последовательности:
левые, или старшие, биты,
правые, или младшие, биты
каждая из которых содержит 32 бита.
Затем выполняется итеративный процесс шифрования,
состоящий из 16 циклов.
Пусть Ti - результат i-й итерации:
Ti 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.

15.

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

16.

Алгоритм шифрования DES
На последнем шаге итерации получают
последовательности R16 и L16 (без перестановки
местами), которые объединяются в 64-битую
последовательность R16L16.
По окончании шифрования осуществляется
восстановление позиций бит с помощью матрицы
обратной перестановки IP-1 (табл. ).
Начальная перестановка 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
16

17.

Алгоритм расшифровывания DES
17
Процесс расшифровывания данных является обратным по
отношению к процессу шифрования.
Это означает, что расшифровываемые данные сначала
переставляются в соответствии с матрицей IP-1,
а затем над последовательностью бит R16L16
выполняются те же действия, что и в процессе
зашифровывания,
но в обратном порядке.

18.

Алгоритм расшифровывания DES
18
Итеративный процесс расшифровывания может быть
описан следующими формулами:
Ri 1 Li , i 1,2,
,16;
Li 1 Ri f Li , Ki , i 1,2,
,16.
Т.о., для процесса расшифровывания с переставленным
входным блоком R16L16
на первой итерации используется ключ K16,
на второй итерации – K15
и т.д.
На 16-й итерации используется ключ K1.

19.

Алгоритм расшифровывания DES
На последнем шаге итерации будут получены
последовательности L0 и R0, которые объединяются в
64-битую последовательность L0R0.
Затем в этой последовательности 64 бита
переставляются в соответствии с матрицей IP.
Результат такого преобразования – исходная
последовательность бит (расшифрованное 64-битовое
значение).
19

20.

Функция шифрования в DES
Схема вычисления функции шифрования f Ri 1, Ki
показана на рис.
20

21.

Функция шифрования в DES
Для вычисления значения функции f используются:
функция E – расширение 32 бит до 48;
функция S1, S2, …, S8 – преобразование 6 битового
числа в 4 битовое;
функция P – перестановка бит в 32 битовой
последовательности.
Приведем определения этих функций.
21

22.

Функция шифрования в DES
22
Аргументами функции шифрования f являются Ri-1 (32 бита)
и Ki (48 бит).
Результат функции E(Ri-1) есть 48-битовое число.
Функция расширения E, выполняющая расширение 32 бит
до 48 (принимает блок из 32 бит и порождает блок из 48
бит), определяется табл..
32
4
8
12
16
20
24
28
Функция E
1
2
3
4
5
6
7
8
9 10 11 12
13 14 15 16
17 18 19 20
21 22 23 24
25 26 27 28
29 30 31 32
5
9
13
17
21
25
29
1
В соответствии с табл. первые три бита E(Ri-1) – это биты 32, 1 и 2, а
последние – 31, 32 и 1.

23.

Функция шифрования в DES
23
Полученный результат (обозначим его E(Ri-1) )
складывается по модулю 2 с текущим значением ключа
Ki
и затем разбивается на восемь 6-битовых блоков
B1, B2 ,
, B8 E Ri 1 Ki
Далее каждый из этих блоков используется как номер
элемента в функциях - матрицах S1, S2, …, S8, содержащих
4-битовые значения (табл. на след. слайде).

24.

S18537642
Функция шифрования в DES
Функции 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
S1
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
S2
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
S3
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
S4
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
24
Функции S
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
S5
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
S6
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
S7
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
S8
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

25.

Функция шифрования в DES
25
Следует отметить, что выбор элемента в матрице S
осуществляется достаточно оригинальным образом.
Пусть на вход матрицы S поступает 6-битовый блок Bj=b1b2b3 b4b5b6,
тогда
2-битовое число b1b6 указывает номер строки матрицы,
а 4-битовое число b2b3 b4b5 - номер столбца.
Например,
если на вход матрицы S1 поступает 6-битовый блок 100110(2),
то 2-битовое число b1b6 =10(2)=2(10) указывает строку с
номером 2 матрицы S1,
а 4-битовое число b2b3 b4b5 =0011(2)=3(10) указывает столбец с
номером 3 матрицы S1.
Это означает, что в матрице S1 блок B1=100110(2) выбирает
элемент на пересечении строки с номером 2 и столбца с
номером 3, т.е. элемент 8(10) =1000(2).
Совокупность 6-битовых блоков B1, B2, …, B8 обеспечивает выбор
4-битового элемента в каждой из матриц B1, B2, …, B8.

26.

Функция шифрования в DES
26
В результате получаем S1(B1), S2(B2), …, S8(B8), т.е. 32-битовый
блок
т.к. матрицы S содержат 4-битовые элементы.
Этот 32-битовый блок преобразуется с помощью функции
перестановки бит P (табл.).
Функция 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
Т.о., функция шифрования математически записывается
f Ri 1, Ki P S1 B1 ,…, S8 B1

27.

Алгоритм вычисления ключей
27
Как нетрудно заметить, на каждой итерации используется
новое значение ключа Ki длиной 48 бит.
Новое значение ключа Ki вычисляется из начального ключа
K (рис. след. слайда).

28.

Алгоритм вычисления ключей
Рисунок – Схема алгоритма
вычисления ключей Ki
28

29.

Алгоритм вычисления ключей
29
Ключ представляет собой 64-битовый блок с 8 битами
контроля по четности, расположенными в позициях 8, 16,
24, 32, 40, 48, 56, 64.
Для удаления контрольных бит и подготовки ключа к работе
используется функция G первоначальной подготовки
ключа (табл.).
57
1
10
19
63
7
14
21
Функция G
49 41 33 25 17
58 50 42 34 26
2 59 51 43 35
11 3 60 52 44
55 47 39 31 23
62 54 46 38 30
6 61 53 45 37
13 5 28 20 12
9
18
27
36
15
22
29
4

30.

Алгоритм вычисления ключей
30
Функция G
Эта таблица разделена на две части.
Результат преобразования разбивается на 57 49 41 33 25 17 9
1 58 50 42 34 26 18
две половины C0 и D0 по 28 бит каждая.
Первые четыре строки матрицы G
10 2 59 51 43 35 27
определяют, как выбираются биты
19 11 3 60 52 44 36
последовательности C0
63 55 47 39 31 23 15
первым битом будет бит 57 ключа
7 62 54 46 38 30 22
шифра, затем бит 49 и т.д.,
14 6 61 53 45 37 29
а последними битами - биты 44 и 36
21 13 5 28 20 12 4
ключа.
Следующие четыре строки матрицы G определяют, как выбираются
биты последовательности D0
т.е. она будет состоять из бит 63, 55, 47,...,12, 4 ключа шифра.
Как видно из таблицы, для генерации последовательностей C0 и D0 не
используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра.
Эти биты не влияют на шифрование и могут служить для других
целей (например, для контроля по четности).
Таким образом, в действительности ключ шифра является
56-битовым.

31.

Алгоритм вычисления ключей
31
После определения C0 и D0 рекурсивно определяются Ci и
Di.
Для этого применяются операции циклического сдвига
влево на один или два бита в зависимости от номера
шага итерации, как показано в табл..
Таблица сдвигов для вычисления ключа
Итерация 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Сдвиг влево 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Операции сдвига выполняются для последовательностей Ci
и Di независимо.
Например,
последовательность C3 получается посредством циклического
сдвига влево на две позиции последовательности C2,
а последовательность D3 - посредством сдвига влево на две
позиции последовательности D2,
C16 и D16 получаются из C15 и D15 посредством сдвига влево на
одну позицию.

32.

Алгоритм вычисления ключей
32
Ключ Ki, определяемый на каждом шаге итерации, есть
результат выбора конкретных бит из 56-битовой
последовательности CiDi и их перестановки.
Другими словами, ключ Ki=H(CiDi ), где функция H
определяется матрицей, завершающей обработку ключа
(табл.).
14
3
23
16
41
30
44
46
Функция H
17 11 24 1
28 15 6 21
19 22 4 26
7 27 20 13
52 31 37 47
40 51 45 33
49 39 56 34
42 50 36 29
5
10
8
2
55
48
53
32
Как следует из таблицы для H,
первым битом ключа Ki будет 14-й
бит последовательности CiDi,
вторым - 17-й бит,
47-м битом ключа Ki будет 29-й бит
CiDi,
а 48-м битом - 32-й бит CiDi.

33.

Криптостойкость DES
33
В январе 1997г. компания RSA Data Security опубликовала
зашифрованный с помощью DES текст и назначила приз в
10 тыс. долларов тому, кто его расшифрует.
Результат был получен за 4 месяца «грубой силой», путем полного
перебора ключей, в котором участвовало около 78 000 компьютеров
в США и Канаде, в основном обычных персональных (в среднем 14
000 компьютеров ежедневно).
Пользователи этих машин получали по Интернету программу для
перебора и интервалы пространства ключей.
Всего было испробовано около 18×1015 вариантов из примерно
72×1015 возможных.
Пик производительности составил 7×109 вариантов в секунду.
Результат был получен на компьютере с процессором Рentium-90 и
16 мегабайт памяти.

34.

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

35.

Основные режимы работы DES
35
Алгоритм DES вполне подходит
как для шифрования,
так и для аутентификации данных.
Он позволяет непосредственно преобразовывать 64битовый входной открытый текст в 64-битовый выходной
шифрованный текст, однако данные редко ограничиваются
64 разрядами.

36.

Основные режимы работы DES
36
Чтобы воспользоваться алгоритмом DES для решения
разнообразных криптографических задач, разработаны
четыре рабочих режима:
электронная кодовая книга ЕСВ (Electronic Code Book);
сцепление блоков шифра СВС (Ciрher Block Chaining);
обратная связь по шифртексту CFB (Ciрher Feed Back);
обратная связь по выходу OFB (Outрut Feed Back).
Эти режимы могут быть использованы для шифрования с
помощью произвольного блочного шифра (не только DES)
потока данных, который в общем случае длиннее блока
шифрования, хотя впервые они введены в стандарте DES.

37.

Основные режимы работы DES
37
Каждому из перечисленных режимов свойственны свои
достоинства и недостатки, что обусловливает области их
применения.
Режим ЕСВ (Электронная кодовая книга) хорошо
подходит для шифрования ключей.
Режим CFB (Обратная связь по шифру), как правило,
предназначается для шифрования отдельных
символов.
Режим OFB (Обратная связь по выходу) нередко
применяется для шифрования в спутниковых системах
связи.

38.

Основные режимы работы DES
38
Режимы СВС (Сцепление блоков шифра) и
СFВ(Обратная связь по шифру) пригодны для
аутентификации данных. Эти режимы позволяют
использовать алгоритм DES для:
интерактивного шифрования при обмене данными
между терминалом и главной ЭВМ;
шифрования криптографического ключа в практике
автоматизированного распространения ключей;
шифрования файлов, почтовых отправлений,
данных спутников и других практических задач.

39.

Тройной DES
39
Наиболее широко известным предложением по усилению
DES является так называемый «тройной DES», одна из
версий которого определяется формулой
EDE 3k1k2k3 (x) DES k3(DES k-12 (DES k1(x)))
То есть, ключ для EDE3 имеет длину 56 3 = 168 бит, и
шифрование 64-битового блока осуществляется
шифрованием с одним подключом, расшифрованием с
другим и затем шифрованием с третьим.
Причина, по которой вторым шагом является DES k-1, а не
2
DES k2 , является совместимость с DES:
если выбрать K=k,k,k, то EDE3K = DESk.
Причина использования DES три раза вместо двух
заключается в существовании атаки «встреча в
середине» на двойной DES.

40.

Тройной DES
Проблема с тройным DES состоит в том, что он гораздо
медленнее, чем сам DES – его скорость составляет
ровно одну треть исходной.
При использовании EDE3 в режиме сцепления блоков это
замедление скажется как на аппаратном, так и на
программном (даже если попытаться компенсировать
его дополнительной аппаратной частью) уровнях.
Во многих случаях такое падение производительности
неприемлемо.
40

41.

Расширение DESX (DES eXtended)
41
В 1984г. Рон Ривест предложил расширение DES,
называемое DESX (DES eXtended), свободное от
недостатков тройного DES. DESX определяется как
DES k ,k1 ,k 2 k 2 DES k ( k1 x )
То есть, ключ DESX K = k,k1,k2 состоит из 54+64+64=184 бит
и включает три различных подключа:
ключ «DES» k,
предварительный «зашумляющий» ключ k1
и завершающий «зашумляющий» ключ k2.
Для шифрования блока сообщения мы складываем его
поразрядно по модулю 2 с k1, шифруем его алгоритмом
DES с ключом k и вновь поразрядно складываем его по
модулю 2 с k2.
Таким образом, затраты DESX на шифрование блока всего
на две операции сложения по модулю 2 больше, чем
затраты исходного алгоритма.

42.

Расширение DESX (DES eXtended)
В отношении DESX замечательно то, что эти две операции
«исключающее ИЛИ» делают шифр гораздо менее
уязвимым по отношению к перебору ключей.
DESX затрудняет получение даже одной пары <xi,
DESXK(xi)> в том случае, когда злоумышленник
организует атаку на шифр по выбранному исходному
тексту, получая множество пар <Pj, DESK(Pj)>.
42

43.

Расширение DESX (DES eXtended)
43
DESX предназначался для увеличения защищенности DES
против перебора ключей и сохранения его стойкости
против других возможных атак.
Но DESX в действительности также увеличивает стойкость
против дифференциального и линейного криптоанализа,
увеличивая требуемое количество проб с выбранным
исходным текстом до величины, превышающей 260.

44.

Расширение DESX (DES eXtended)
44
DESX предназначался для увеличения защищенности DES
против перебора ключей и сохранения его стойкости
против других возможных атак.
Но DESX в действительности также увеличивает стойкость
против дифференциального и линейного криптоанализа,
увеличивая требуемое количество проб с выбранным
исходным текстом до величины, превышающей 260.

45.

Расширение DESX (DES eXtended)
Дальнейшее увеличение стойкости против этих атак может
быть достигнуто заменой в DESX операции
«исключающее ИЛИ» на сложение, как это было
сделано в
DES PEPk ,k ,k k 2 DES k ( k1 x )
где сложение определяется следующим образом:
L.R + L'.R' = (L L').(R R'), |L|=|R|=|L'|=|R'|= 32,
а обозначает сложение по модулю 232.
1
2
45

46.

Расширение DESX (DES eXtended)
Сказанное не означает, что невозможно построить машину,
раскрывающую DESX за приемлемое время.
Но оно подразумевает, что такая машина должна
использовать какую-либо радикально новую идею.
Это не может быть машина, реализующая перебор
ключей в общепринятом смысле.
46

47.

Расширение DESX (DES eXtended)
47
Таким образом, практически во всех отношениях DESX
оказывается лучше DES. Этот алгоритм
прост,
совместим с DES,
эффективно реализуем аппаратно,
может использовать существующее аппаратное
обеспечение DES
и в его отношении было доказано, что он увеличивает
стойкость к атакам, основанным на переборе ключей.