1. 1 Основные понятия и определения криптографии 8 2 Симметричные и асимметричные криптосистемы 11
 Скачать 193.57 Kb.
|
2. Алгоритм DESСтандарт шифрования данных DES опубликован в 1977 г. Национальным бюро стандартом США. Стандарт DES предназначен для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 г. Был одобрен Национальным институтом стандартов и технологий США. С этого момента DES превращается в стандарт не только по названию, но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных. К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того, реализация алгоритма DES в таких системах становится признаком хорошего тона. Основные достоинства алгоритма DES: используется только один ключ длиной 56 битов; зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой; относительная простота алгоритма обеспечивает высокую скорость обработки информации; достаточно высокая стойкость алгоритма. DES осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности (несмотря на кажущуюся очевидность, так делается далеко не всегда. Позже мы рассмотрим шифры, в которых шифрование и расшифрование осуществляются по разным алгоритмам). Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (Рисунок 1).  Рисунок 1 Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа [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-й итерации описывается следующими формулами: L(i) = R (i-1) 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)). Наконец, для получения результата функции шифрования надо переставить биты этой последовательности [2]. Для этого применяется функция перестановки P (табл. 5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 – битом 2 и т.д. Таблица 5: Функция перестановки P 16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10 02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25 Таким образом, 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(i) Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ K(15), затем – K(14) и так далее. Теперь вам должно быть понятно, почему автор настойчиво рекомендует использовать приведенные матрицы. Если вы начнете самовольничать, вы, должно быть, получите очень секретный шифр, но вы сами не сможете его потом раскрыть! |