Программная реализация криптографических систем DES, 3-DES и DESX

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Кафедра компьютерной инженерии

 

 

 

 

Дисциплина «Основы информационной безопасности»

КУРСОВОЙ ПРОЕКТ

Тема: «Программная реализация криптографических систем DES, 3-DES и DESX»

Вариант 2

 

 

 

Выполнили: студенты 3 курса ФИТ

Бактыгерей Айгерим

Ким Инна

Хакимова Асия

Шотаева Гаухар

Проверила: к.т.н., доцент кафедры

компьютерной инженерии

Дюсенбина А.Б.

 

 

 

 

Алматы 2012

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 3

ИСТОРИЯ 3

ОСНОВНАЯ  ФУНКЦИЯ ШИФРОВАНИЯ 5

РЕЖИМЫ  РАБОТЫ АЛГОРИТМА DES 14

ШИФРОВАНИЕ  И РАСШИФРОВАНИЕ В РЕЖИМЕ ЭЛЕКТРОННОЙ  КОДОВОЙ КНИГИ (ECB) 14

ШИФРОВАНИЕ  И РАСШИФРОВАНИЕ В РЕЖИМЕ СЦЕПЛЕНИЯ  БЛОКОВ ШИФРА (CBC) 15

ШИФРОВАНИЕ  И РАСШИФРОВАНИЕ В РЕЖИМЕ ОБРАТНОЙ СВЯЗИ ПО ШИФРОТЕКСТУ (CFB) 16

ШИФРОВАНИЕ  И РАСШИФРОВАНИЕ В РЕЖИМЕ ОБРАТНОЙ СВЯЗИ ПО ВЫХОДУ (OFB) 17

ШИФРОВАНИЕ  И РАСШИФРОВКА ПО АЛГОРИТМУ 3-DES В ОДНОМ ИЗ РЕЖИМОВ 18

ШИФРОВАНИЕ  И РАСШИФРОВКА ПО АЛГОРИТМУ DESX В ОДНОМ ИЗ РЕЖИМОВ 19

ПРИЛОЖЕНИЕ 20

 

 

 

ВВЕДЕНИЕ

В 1977 году Национальное бюро Стандартов США (NBS) опубликовало стандарт шифрования данных Data Encryption Standard (DES), предназначенный для использования в государственных и правительственных учреждениях США для защиты от несанкционированного доступа важной, но несекретной информации. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 году был одобрен ANSI. С этого момента DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически. Появляются программное обеспечение и специализированные микро-ЭВМ, предназначенные для шифрования/расшифровки информации в сетях передачи данных и на магнитных носителях. К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того реализация алгоритма DES в таких системах является просто признаком хорошего тона! За примерами далеко ходить не надо. Программа DISKREET из пакета Norton Utilities, предназначенная для создания зашифрованных разделов на диске, использует именно алгоритм DES. "Собственный алгоритм шифрования" отличается от DES только числом итераций при шифровании. Почему же DES добился такой популярности?

Основные достоинства  алгоритма DES:

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

ИСТОРИЯ

В 1972 году, после проведения исследования потребностей правительства  США в компьютерной безопасности, американское НБС (Национальное Бюро Стандартов) — теперь переименовано НИСТ (Национальный Институт Стандартов и Технологий) — определило необходимость в  общеправительственном стандарте шифрования некритичной информации. 15 мая 1973 года, после консультации с АНБ (Агентством национальной безопасности), НБС объявило конкурс на шифр, который удовлетворит строгим критериям проекта, но ни один конкурсант не обеспечивал выполнение всех требований. Второй конкурс был начат 27 августа 1974. На сей раз, шифр Lucifer, представленный IBM и развитый в течение периода 1973—1974 сочли приемлемым, он был основан на более раннем алгоритме Хорста Фейстеля.

17 марта 1975 года предложенный  алгоритм DES был издан в Федеральном  Регистре. В следующем году было  проведено 2 открытых симпозиума  по обсуждению этого стандарта,  где подверглись жёсткой критике  изменения, внесённые АНБ в  алгоритм: уменьшение первоначальной  длины ключа и S-блоки (блоки  подстановки), критерии проектирования которых не раскрывались. АНБ подозревалось в сознательном ослаблении алгоритма с целью, чтобы АНБ могло легко просматривать зашифрованные сообщения. После чего сенатом США была проведена проверка действий АНБ, результатом которой стало заявление, опубликованное в 1978, в котором говорилось о том, что в процессе разработки DES АНБ убедило IBM, что уменьшенной длины ключа более чем достаточно для всех коммерческих приложений, использующих DES, косвенно помогало в разработке S-перестановок, а также, что окончательный алгоритм DES был лучшим, по их мнению, алгоритмом шифрования и был лишён статистической или математической слабости. Также было обнаружено, что АНБ никогда не вмешивалось в разработку этого алгоритма.

Часть подозрений в скрытой  слабости S-перестановок была снята  в 1990, когда были опубликованы результаты независимых исследований Эли Бихама (Eli Biham) и Ади Шамира (Adi Shamir) по дифференциальному криптоанализу — основному методу взлома блочных алгоритмов шифрования с симметричным ключом. S-блоки алгоритма DES оказались намного более устойчивыми к атакам, чем, если бы их выбрали случайно. Это означает, что такая техника анализа была известна АНБ ещё в 70-х годах XX века.

Но еще в 1998 году используя  суперкомпьютер стоимостью 250 тыс. долл., сотрудники RSA Laboratory «взломали» утвержденный правительством США алгоритм шифрования данных (DES) менее чем за три дня. (Предыдущий рекорд по скорости взлома был установлен с помощью огромной сети, состоящей из десятков тысяч компьютеров, и составил 39 дней). На специально организованной по этому случаю пресс-конференции ученые с беспокойством говорили о том, что злоумышленники вряд ли упустят случай воспользоваться подобной уязвимостью. Эксперимент проходил в рамках исследования DES Challenge II, проводимого RSA Laboratory под руководством общественной организации Electronic Frontier Foundation (EFF), которая занимается проблемами информационной безопасности и личной тайны в Internet. Суперкомпьютер, построенный в RSA Laboratory для расшифровки данных, закодированных методом DES по 56-разрядному ключу, получил название EFF DES Cracker. Как утверждали правительственные чиновники и некоторые специалисты, для взлома кода DES требуется суперкомпьютер стоимостью в несколько миллионов долларов. «Правительству пора признать ненадежность DES и поддержать создание более мощного стандарта шифрования», — сказал президент EFF Барри Штайнхардт. Экспортные ограничения, накладываемые правительством США, касаются технологий шифрования по ключам длиной более 40 бит. Однако, как показали результаты эксперимента RSA Laboratory, существует возможность взлома и более мощного кода. Проблема усугубляется тем, что стоимость постройки подобного суперкомпьютера неуклонно снижается. «Через четыре-пять лет такие компьютеры будут стоять в любой школе», — говорит Джон Гилмор, руководитель проекта DES Challenge и один из основателей EFF.

DES является блочным шифром. Чтобы понять, как работает DES, необходимо  рассмотреть принцип работы блочного  шифра, сеть Фейстеля.

ОСНОВНАЯ ФУНКЦИЯ  ШИФРОВАНИЯ

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

Процесс шифрования заключается  в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).

  Рис.1. Обобщенная схема  шифрования в алгоритме DES

Необходимо сразу же отметить, что ВСЕ таблицы, приведенные  в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма 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

Затем выполняется шифрование, состоящее из 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

Матрицы 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

Результат функции Е(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. Функции преобразования S1, S2, ..., S8

К табл.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 первоначальной подготовки ключа

Результат преобразования 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 завершающей обработки ключа

Ключ 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.

Кстати, если вы написали программу  защиты данных и хотите дать полноценную  рекламу, то автор рекомендует прямо  указывать, какие из режимов поддерживает ваше детище. Это, вообще говоря, признак  хорошего тона на рынке программного обеспечения средств защиты. Нет  смысла раскрывать весь алгоритм, вы просто указываете : DES-CBC или DES-CFB и, как говорится, "умный догадается, а дураку и не надо".