Алгоритм des и его модификации. Основные режимы работы алгоритма DES
Прошло уже белее 30 лет с даты принятия алгоритма DES в качестве стандарта шифрования США. DES - алгоритм шифрования с наиболее богатой и интересной историей.
История создания алгоритма
Один из наиболее известных в мире криптологов Брюс Шнайер в своей знаменитой книге «Прикладная криптография» так описал проблемы пользователей средств защиты информации в начале 70-х гг. XX века (естественно, речь идет о пользователях по ту сторону «железного занавеса»):
П не было как общепринятого стандарта шифрования данных, так и просто достаточно широко используемых алгоритмов защиты информации, поэтому о совместимости между различными программными или аппаратными средствами шифрования не могло быть и речи;
Практически любое средство шифрования представляло собой «черный ящик» с достаточно неясным содержимым: какой алгоритм шифрования используется, насколько он является криптографически стойким, грамотно ли он реализован, корректно ли создаются, хранятся, используются ключи шифрования, нет ли в средстве вставленных разработчиками недокументированных возможностей и т. д., - вся эта весьма важная информация для подавляющего большинства покупателей криптографических средств была недоступна.
Данной проблемой озаботилось Национальное Бюро Стандартов (National Bureau of Standards, NBS) США. В результате в 1973 г. был объявлен первый в истории открытый конкурс на стандарт шифрования. NBS было готово исследовать с целью выбора стандарта алгоритмы-претенденты, удовлетворяющие следующим критериям:
Алгоритм должен быть криптографически стойким;
Алгоритм должен быть быстрым;
П структура алгоритма должна быть четкой и ясной;
Стойкость шифрования должна зависеть только от ключа, сам алгоритм не должен быть секретным;
Алгоритм должен быть легко применим для различных целей;
Алгоритм должен легко реализовываться аппаратно на существующей элементной базе.
Предполагалось, что заинтересованные организации или специалисты будут присылать в NBS подробные спецификации алгоритмов, достаточные для их реализации, т. е. не имеющие каких-либо «белых пятен». Предполагалось также, что алгоритм будет сертифицирован NBS для всеобщего использования, с него будут сняты все патентные и экспортные ограничения, в результате чего такой стандарт должен будет решить все проблемы совместимости средств шифрования. Кроме того, NBS брало на себя функции сертификации средств шифрования - т. е. «черные ящики» должны были безвозвратно уйти в прошлое.
Фактически алгоритм-претендент оказался всего один: это был разработанный фирмой ШМ алгоритм шифрования Lucifer {см. разд. 3.31). В течение двух лет проводилась доработка алгоритма:
Во-первых, NBS совместно с Агентством Национальной Безопасности (АНБ, NSA - National Security Agency) США был проведен тщательный анализ алгоритма, результатом которого явилась его достаточно существенная переработка;
Во-вторых, принимались к рассмотрению комментарии и критические замечания от всех заинтересованных организаций и частных лиц.
В результате совместной деятельности IBM, NBS и АНБ в январе 1977 г. DES был опубликован как стандарт США (последняя версия этого стандарта - в документе ) на алгоритм шифрования данных (кроме информации повышенной степени секретности). Алгоритм DES был запатентован фирмой ЮМ, однако NBS получило, фактически, бесплатную и неограниченную лицензию на использование данного алгоритма . Альтернативное, но реже используемое название алгоритма - DEA (Data Encryption Algorithm).
Основные характеристики и структура алгоритма
Алгоритм DES шифрует информацию блоками по 64 бита с помощью 64- битного ключа шифрования, в котором используется только 56 битов (процедура расширения ключа подробно описана далее).
Шифрование информации выполняется следующим образом (рис. 3.56):
1. Над 64-битным блоком данных производится начальная перестановка согласно табл. 3.16.
Таблица 3.16
Таблица трактуется следующим образом: значение входного бита 58 (здесь и далее все биты нумеруются слева направо, начиная с 1-го) помещается в выходной бит 1, значение 50-го бита - в бит 2 и т. д.
2. Результат предыдущей операции делится на 2 субблока по 32 бита (на
рис. 3.56 обозначены А 0 и В 0), над которыми производятся 16 раундов
следующих преобразований:
Как было сказано выше, из 64-битного ключа шифрования алгоритм DES использует только 56 битов. Каждый 8-й бит отбрасывается и никак не применяется в алгоритме, причем использование оставшихся битов ключа шифрования в реализациях алгоритма DES никак не лимитировано стандартом . Процедура извлечения 56 значащих битов 64-битного ключа на рис. 3.59 обозначена как Е. Помимо извлечения, данная процедура выполняет еще и перестановку битов ключа согласно табл. 3.19 и 3.20.
Таблица 3.19
Таблица 3.20
В результате перестановки формируются два 28-битных значения С и D. Таблица 3.19 определяет выборку битов ключа для С, табл. 3.20 - для D.
Затем выполняются 16 раундов преобразований, каждый из которых дает один из ключей раундов K t . В каждом раунде процедуры расширения ключа производятся следующие действия:
1. Текущие значения С и D циклически сдвигаются влево на переменное число битов п. Для раундов 1, 2, 9 и 16 п = 1, в остальных раундах выполняется циклический сдвиг на 2 бита.
2. С и D объединяются в 56-битное значение, к которому применяется сжимающая перестановка CP, результатом которой является 48-битный ключ раунда К (. Сжимающая перестановка выполняется согласно табл. 3.21.
Таблица 3.21
При расшифровании данных можно использовать ту же процедуру расширения ключа, но применять ключи раундов в обратном порядке. Есть и другой вариант: в каждом раунде процедуры расширения ключа вместо циклического сдвига влево выполнять циклический сдвиг вправо на п битов, где гс’ = 0 для первого раунда, и’=1 для раундов 2, 9, 16 и п= 2 для остальных раундов. Такая процедура расширения ключа сразу даст нужные для расшифровывания ключи раундов.
Стоит сказать, что возможность выполнения расширения ключа «на лету» (особенно если эта возможность существует как при зашифровывании, так и при расшифровывании) считается достоинством алгоритмов шифрования, поскольку в этом случае расширение ключа можно выполнять параллельно шифрованию и не тратить память на хранение ключей других раундов, кроме текущего.
Алгоритм DES
Основные достоинства алгоритма DES:
· используется только один ключ длиной 56 битов;
· зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой;
· относительная простота алгоритма обеспечивает высокую скорость обработки информации;
· достаточно высокая стойкость алгоритма.
DES осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности (несмотря на кажущуюся очевидность, так делается далеко не всегда. Позже мы рассмотрим шифры, в которых шифрование и расшифрование осуществляются по разным алгоритмам).
Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).
Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.
Рис.2. Структура алгоритма шифрования DES
Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и т.д., что даст в результате: T(0) = IP(T).
Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) - левые или старшие биты, R(0) - правые или младшие биты.
Таблица 1: Матрица начальной перестановки IP
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:
R(i) = L(i-1) xor f(R(i-1), K(i)) ,
где xor - операция ИСКЛЮЧАЮЩЕЕ ИЛИ.
Функция f называется функцией шифрования. Ее аргументы - это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.
На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16).
Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP -1 (табл.2).
Таблица 2: Матрица обратной перестановки IP -1
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Матрицы IP -1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP -1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP -1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.
Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP-1, а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.
Итеративный процесс расшифрования может быть описан следующими формулами:
R(i-1) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .
На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).
Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки - исходная 64-битовая последовательность.
Теперь рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.
Рис.3. Вычисление функции f(R(i-1), K(i))
Для вычисления значения функции f используются следующие функции-матрицы:
Е - расширение 32-битовой последовательности до 48-битовой,
S1, S2, ... , S8 - преобразование 6-битового блока в 4-битовый,
Р - перестановка бит в 32-битовой последовательности.
Функция расширения Е определяется табл.3. В соответствии с этой таблицей первые 3 бита Е(R(i-1)) - это биты 32, 1 и 2, а последние - 31, 32 и 1.
Таблица 3:Функция расширения E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 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 01
Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:
E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .
Функции S1, S2, ... , S8 определяются табл.4.
Таблица 4
К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.
Например, В(1)=011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011)=0101.
Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2), ..., B(8), получаем 32-битовую последовательность S1(B(1))S2(B(2))S3(B(3))...S8(B(8)).
Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл.5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 - битом 2 и т.д.
Таблица 5:Функция перестановки P
Такимобразом,
f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))
Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1...16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.
Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (табл.6).
Таблица 6
Матрица G первоначальной подготовки ключа
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49, ..., 44, 36 ключа K, а D(0) будет состоять из битов 63, 55, ..., 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1...16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл.7.
Таблица 7
Таблица сдвигов для вычисления ключа
| Номер итерации | Сдвиг (бит) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
Полученное значение вновь "перемешивается" в соответствии с матрицей H (табл.8).
Таблица 8:Матрица H завершающей обработки ключа
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Ключ K(i) будет состоять из битов 14, 17, ..., 29, 32 последовательности C(i)D(i). Таким образом:
K(i) = H(C(i)D(i))
Блок-схема алгоритма вычисления ключа приведена на рис.4.
Рис.4. Блок-схема алгоритма вычисления ключа K(i)
Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ
K(15), затем - K(14) и так далее. Теперь вам должно быть понятно, почему автор настойчиво рекомендует использовать приведенные матрицы. Если вы начнете самовольничать, вы, должно быть, получите очень секретный шифр, но вы сами не сможете его потом раскрыть!
Режимы работы алгоритма DES
Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколько режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:
· электронный шифроблокнот (Electronic Codebook) - ECB;
· цепочкацифровыхблоков (Cipher Block Chaining) - CBC;
· цифровая обратная связь (Cipher Feedback) - CFB;
· внешняя обратная связь (Output Feedback) - OFB.
В этом режиме исходный файл M разбивается на 64-битовые блоки (по 8 байтов): M = M(1)M(2)...M(n). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования (рис.5). Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.
Стандарт DES предназначен для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 г. Был одобрен Национальным институтом стандартов и технологий США. С этого момента DES превращается в стандарт не только по названию, но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных.
К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того, реализация алгоритма DES в таких системах становится признаком хорошего тона.
Основные достоинства алгоритма DES:
· используется только один ключ длиной 56 битов;
· зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой;
· относительная простота алгоритма обеспечивает высокую скорость обработки информации;
· достаточно высокая стойкость алгоритма.
DES осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности (несмотря на кажущуюся очевидность, так делается далеко не всегда. Позже мы рассмотрим шифры, в которых шифрование и расшифрование осуществляются по разным алгоритмам).
Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис. 1).
Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис. 2.
Рис. 2.
Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл. 1) следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и т.д., что даст в результате: T(0) = IP(T).
Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) - левые или старшие биты, R(0) - правые или младшие биты.
Таблица 1: Матрица начальной перестановки IP
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:
R(i) = L (i-1) xor f (R(i-1), K(i)),
где xor - операция ИСКЛЮЧАЮЩЕЕ ИЛИ.
Функция f называется функцией шифрования. Ее аргументы - это 32-битовая последовательность R (i-1), полученная на (i-1) - ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.
На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16) L(16).
Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP -1 (табл. 2).
Таблица 2: Матрица обратной перестановки IP -1
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
Матрицы IP -1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP -1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP -1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.
Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP-1, а затем над последовательностью бит R(16) L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.
Итеративный процесс расшифрования может быть описан следующими формулами:
R (i-1) = L(i), i = 1, 2,…, 16;
L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.
На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0) R(0).
Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки - исходная 64-битовая последовательность.
Теперь рассмотрим функцию шифрования f (R(i-1), K(i)). Схематически она показана на рис. 3.
Рис. 3.
Для вычисления значения функции f используются следующие функции-матрицы:
Е - расширение 32-битовой последовательности до 48-битовой,
S1, S2,…, S8 - преобразование 6-битового блока в 4-битовый,
Р - перестановка бит в 32-битовой последовательности.
Функция расширения Е определяется табл. 3. В соответствии с этой таблицей первые 3 бита Е (R(i-1)) - это биты 32, 1 и 2, а последние - 31, 32 и 1.
Таблица 3: Функция расширения E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 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 01
Результат функции Е (R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). То есть:
E (R(i-1)) xor K(i) = B(1) B(2)… B(8).
Функции S1, S2,…, S8 определяются табл. 4.
Таблица 4
К табл. 4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 - номер столбца. Результатом Sj (B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.
Например, В(1)=011011. Тогда S1 (В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1 (011011)=0101.
Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2),…, B(8), получаем 32-битовую последовательность S1 (B(1)) S2 (B(2)) S3 (B(3))… S8 (B(8)).
Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл. 5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 - битом 2 и т.д.
Таблица 5: Функция перестановки P
Таким образом,
f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))
Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1…16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.
Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (табл. 6).
Таблица 6
Матрица G первоначальной подготовки ключа
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49,…, 44, 36 ключа K, а D(0) будет состоять из битов 63, 55,…, 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1…16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл. 7.
Таблица 7. Таблица сдвигов для вычисления ключа
|
Номер итерации |
Сдвиг (бит) |
Полученное значение вновь «перемешивается» в соответствии с матрицей H (табл. 8).
Таблица 8: Матрица H завершающей обработки ключа
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Ключ K(i) будет состоять из битов 14, 17,…, 29, 32 последовательности C(i) D(i). Таким образом:
K(i) = H (C(i) D(i))
Блок-схема алгоритма вычисления ключа приведена на рис. 4.
Рис. 4.
Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ K(15), затем - K(14) и так далее. Теперь вам должно быть понятно, почему автор настойчиво рекомендует использовать приведенные матрицы. Если вы начнете самовольничать, вы, должно быть, получите очень секретный шифр, но вы сами не сможете его потом раскрыть!
Аннотация: Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. И хотя старый американский стандарт DES в настоящее время утратил свой официальный статус, этот алгоритм все же заслуживает внимания при изучении криптографии. Кроме того в этой лекции объясняется, что такое "двухкратный DES", атака "встреча посередине" и способы ее устранения. В этой же лекции кратко рассматривается новый стандарт США на блочный шифр – алгоритм Rijndael.
Цель лекции : познакомить студента с основными сведениями об алгоритме шифрования DES .
Основные сведения
Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard . Эта система первой получила статус государственного стандарта в области шифрования данных. Она разработана специалистами фирмы IBM и вступила в действие в США 1977 году. Алгоритм DES широко использовался при хранении и передаче данных между различными вычислительными системами; в почтовых системах, в электронных системах чертежей и при электронном обмене коммерческой информацией . Стандарт DES реализовывался как программно, так и аппаратно. Предприятиями разных стран был налажен массовый выпуск цифровых устройств, использующих DES для шифрования данных. Все устройства проходили обязательную сертификацию на соответствие стандарту.
Несмотря на то, что уже некоторое время эта система не имеет статуса государственного стандарта, она по-прежнему широко применяется и заслуживает внимания при изучении блочных шифров с закрытым ключом.
Длина ключа в алгоритме DES составляет 56 бит . Именно с этим фактом связана основная полемика относительно способности DES противостоять различным атакам. Как известно, любой блочный шифр с закрытым ключом можно взломать, перебрав все возможные комбинации ключей. При длине ключа 56 бит возможны 2 56 разных ключей. Если компьютер перебирает за одну секунду 1 000 000 ключей (что примерно равно 2 20), то на перебор всех 2 56 ключей потребуется 2 36 секунд или чуть более двух тысяч лет, что, конечно, является неприемлемым для злоумышленников.
Однако возможны более дорогие и быстрые вычислительные системы, чем персональный компьютер . Например, если иметь возможность объединить для проведения параллельных вычислений миллион процессоров, то максимальное время подбора ключа сокращается примерно до 18 часов. Это время не слишком велико, и криптоаналитик, оснащенный подобной дорогой техникой, вполне может выполнить вскрытие данных, зашифрованных DES за приемлемое для себя время.
Вместе с этим можно отметить, что систему DES вполне можно использовать в небольших и средних приложениях для шифрования данных, имеющих небольшую ценность. Для шифрования данных государственной важности или имеющих значительную коммерческую стоимость система DES в настоящее время, конечно, не должна использоваться. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блочный шифр , названный AES (Advanced Encryption Standard) , в основу которого был положен шифр Rijndael , разработанный бельгийскими специалистами. Этот шифр рассматривается в конце лекции.
Основные параметры DES : размер блока 64 бита, длина ключа 56 бит , количество раундов – 16. DES является классической сетью Фейштеля с двумя ветвями. Алгоритм преобразует за несколько раундов 64-битный входной блок данных в 64-битный выходной блок. Стандарт DES построен на комбинированном использовании перестановки, замены и гаммирования. Шифруемые данные должны быть представлены в двоичном виде.
Шифрование
Общая структура DES представлена на рис. 4.1 . Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:
- начальная подготовка блока данных;
- 16 раундов "основного цикла";
- конечная обработка блока данных.
На первом этапе выполняется начальная перестановка 64-битного исходного блока текста, во время которой биты определенным образом переупорядочиваются.
На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа , получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.
Наконец, на третьем этапе выполняется перестановка результата, полученного после шестнадцати шагов основного цикла . Эта перестановка обратна начальной перестановке.
Рис.
4.1.
Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES .
На первом этапе 64-разрядный блок исходных данных подвергается начальной перестановке. В литературе эта операция иногда называется "забеливание" – whitening . При начальной перестановке биты блока данных определенным образом переупорядочиваются. Эта операция придает некоторую "хаотичность" исходному сообщению, снижая возможность использования криптоанализа статистическими методами.
Одновременно с начальной перестановкой блока данных выполняется начальная перестановка 56 бит ключа. Из рис. 4.1 . видно, что в каждом из раундов используется соответствующий 48-битный частичный ключ K i . Ключи K i получаются по определенному алгоритму, используя каждый из битов начального ключа по нескольку раз. В каждом раунде 56-битный ключ делится на две 28-битовые половинки. Затем половинки сдвигаются влево на один или два бита в зависимости от номера раунда. После сдвига определенным образом выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, то эта операция называется " перестановка со сжатием". Ее результатом является набор из 48 битов. В среднем каждый бит исходного 56-битного ключа используется в 14 из 16 подключей, хотя не все биты используются одинаковое количество раз.
Далее выполняется основной цикл преобразования, организованный по сети Фейштеля и состоящий из 16 одинаковых раундов. При этом в каждом раунде ( рис. 4.2) получается промежуточное 64-битное значение , которое затем обрабатывается в следующем раунде.
Рис. 4.2.
Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения, обозначенные L и R .
Вначале правая часть блока R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа для выполнения операции XOR . Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется "лавинным эффектом"). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.
После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution - подстановка), результатом которой является 32-битное значение . Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes). При выполнении этой DES на бумаге выглядит достаточно сложным, что уж говорить про его программную реализацию! Разработать правильно и оптимально функционирующую программу полностью в соответствии с DES , наверно, под силу только опытным программистам. Некоторые трудности возникают при программной реализации, например, начальной перестановки или перестановки с расширением. Эти сложности связаны с тем, что первоначально планировалось реализовывать DES только аппаратно. Все используемые в стандарте операции легко выполняются аппаратными блоками, и никаких трудностей с реализацией не возникает. Однако через некоторое время после публикации стандарта разработчики программного обеспечения решили не стоять в стороне и тоже взяться за создание систем шифрования. В дальнейшем DES реализовывался и аппаратно, и программно.
DES (Data Encryption Standart) - Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:Блочный шифр
Входными данными для блочного шифра служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.Базовые преобразования:
Преобразования Сетью Фейстеля
Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).
Схема шифрования алгоритма DES
Исходный текст - блок 64 бит.
Шифрованный текст - блок 64 бит.
Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
Рассмотрим подробную схему алгоритма DES:
L i R i =1,2\ldots.левая и правая половины 64-битового блока L i R i
k i - 48 битовые ключи
f - функция шифрования
IP - начальная перестановка
IP -1 - конечная перестановка.
По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.
16 циклов преобразования Фейстеля:
Разбить IP(T) на две части L 0 ,R 0 , где L 0 ,R 0 - соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L 0 R 0
Пусть T i -1 = L i -1 R i -1 результат (i-1) итерации, тогда результат i-ой интерации T i = L i R i определяется:
L i = R i - 1 Левая половина L i равна правой половине предыдущего вектора L i - 1 R i - 1 . А правая половина R i - это битовое сложение L i - 1 и f(R i - 1 , k i) по модулю 2.
В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.
Аргументы функции f являются 32 битовой вектор R i - 1 , 48 битовой ключ k i , которые являются результатом преобразования 56 битового исходного ключа шифра k.
Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.
Функция Е расширяется 32 битовой вектор R i - 1 до 48 битовой вектор E(R i - 1) путем дублирования некоторых битов из R i - 1 при этом порядок битов вектора E(R i - 1) указан в таблице 2.
Первые три бита вектора E(R i - 1) являются битами 32, 1, 2 вектора R i -1 . По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri - 1) - это биты 31, 32, 1 вектора R i - 1 . Полученный после перестановки блок E(R i -1) складывается по модулю 2 с ключами k i и затем представляются в виде восьми последовательных блоков B 1 ,B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Каждый B j является 6-битовым блоком. Далее каждый из блоков B j трансформируется в 4 битовой блок B" j с помощью преобразований S j . Преобразования S j определяется таблицей 3.
Предположим что B 3 = 101111 и мы хотим найти B" 3 . Первый и последний разряды B 3 являются двоичной записью числа а, 0Значение функции f(R i - 1 ,k i) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B" 1 B" 2 ...B" 8 . Перестановка Р задана таблицей 4.
f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f - это бита 16, 7, 20, 21 вектора B" 1 B" 2 ...B" 8
Генерирование ключей k i .
Ключи k i получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.
Эта перестановка определяется двумя блоками C 0 и D 0 по 28 бит каждый. Первые 3 бита C 0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D 0 есть биты 63, 55, 47 расширенного ключа. C i ,D i i=1,2,3…получаются из C i - 1 ,D i - 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.
Ключ k i , i=1,…16 состоит из 48 бит, выбранных из битов вектора C i D i (56 бит) согласно таблице 7. Первый и второй биты k i есть биты 14, 17 вектора C i D i
Конечная перестановка IP - 1 действует на T 16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.
Режимы использования DES
DES может используется в четырех режимах.
