Шифрование данных. Алгоритм Blowfish

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТАМБОВСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 

ИМЕНИ Г.Р. ДЕРЖАВИНА

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

УДК  004.056.55 
 
 
 

Козиков Антон Юрьевич 

ШИФРОВАНИЕ  ДАННЫХ. АЛГОРИТМ BLOWFISH 

Курсовая  работа

по курсу  «Программирование на С++» 
 
 
 

                Студент 4 курса (48 группы)

                дневного  отделения. 

                Научный руководитель:

                к.ф.м.н. Зуев М.С. 
                 
                 

Тамбов  – 2010 

РЕФЕРАТ 

     Козиков А.Ю. Шифрование данных. Алгоритм Blowfish: курсовая работа / Козиков Антон Юрьевич; Тамб. гос. ун-т им. Г.Р. Державина: Каф. информатики и информационных технологий; Науч. рук:  к.м.н., доцент Зуев М.С. – Тамбов 2010.

     Ключевые  слова: сеть Файстеля, криптографический алгоритм, шифрование, расшифрования, блочные алгоритмы.

     Предмет исследования – криптографический  алгоритм Blowfish. Цель работы – разработка программного продукта обеспечивающего шифрование/расшифрование данных по алгоритму Blowfish. Алгоритм Blowfish — блочный шифр, основанный на сети Файстеля. Алгоритм прост в реализации, он является стойким ко всем, известным на сегодняшний день, методам криптоанализа.

 

СОДЕРЖАНИЕ 

Введение 4

1 Понятие шифрования данных 7

2 Описание алгоритма blowfish 11

2.1 Структура алгоритма 11

2.2 Процедура расширения  ключа 13

2.3 Достоинства и  недостатки алгоритма 14

3 Практическая реализация алгоритма blowfish 16

4 Описани работы с программным продуктом 21

4.1 Минимальные требования для работы программного продукта 21

4.2 Шифрование данных 21

4.3 Расшифрование данных 23

4.4 Генерация пароля 25

Заключение 26

Список  использованных источников 27

Приложение 1. Содержимое заголовочного  файла 28

Приложение 2. Содержимое основного  файла 29

  

    ВВЕДЕНИЕ

 

     Задача  защиты информации от несанкционированного доступа решалась во все времена  на протяжении почти всей истории человечества. Уже в древнем мире выделилось два основных направления решения этой задачи, существующие и по сегодняшний день: криптография и стеганография. Целью криптографии является скрытие содержимого сообщений за счет их шифрования [6].

     Изначально письмо само по себе было криптографической системой, поскольку в древних обществах подобным знанием обладали лишь избранные. Священные манускрипты различных древних государств тому примеры.

     С тех пор как письменность стала  широко распространенной, криптография становиться вполне самостоятельной наукой. Первые криптографические системы можно встретить уже в начале нашей эпохи. Например, Юлий Цезарь в своей личной переписке пользовался более-менее систематическим шифр, который впоследствии был назван его именем.

     Серьёзное развитие шифровальные системы получили в эпоху первой и второй мировых войн. Начиная с раннего, послевоенного времени и по сей момент появление современных вычислительных аппаратов ускорило создание и усовершенствование криптографических методов. Пробуждение и развитие криптографии связано с зарождением электросвязи. В XX столетии секретные службы большинства развитых стран стали относится к этой дисциплине как к  обязательному инструменту своей деятельности.

     То  же самое касается и разработки криптографических  алгоритмов —   известно множество алгоритмов шифрования, и далеко не все из них разработаны «в недрах спецслужб» или научными институтами — встречаются весьма удачные и широко используемые алгоритмы, разработанные частными лицами. [9]

     Вслед за массовым применением современных  информационных технологий криптография вторгается в жизнь современного человека. На криптографических методах  основано применение электронных платежей, возможность передачи секретной  информации по открытым сетям связи, а также решение большого числа  других задач защиты информации в  компьютерных системах и информационных сетях. Потребности практики привели  к необходимости массового применения криптографических методов, а, следовательно, к необходимости расширения открытых исследований и разработок в этой области. Владение основами криптографии становится важным для учёных и инженеров, специализирующихся в области разработки современных средств защиты информации, а также в областях эксплуатации и проектирования информационных и  телекоммуникационных систем.

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

     Во-первых, расширилась сфера применения компьютерных сетей, таких как World Wide Web, с помощью которых передаются огромные объемы информации государственного, военного, коммерческого и личного характера, не дающего возможности доступа к ней сторонних лиц.

     Во-вторых, появление современных сверхмощных  компьютеров, продвинутых технологий сетевых и нейронных вычислений делает возможным дискредитацию шифровальных систем еще вчера считавшихся совершенно безопасными [8].

     Целью написания курсовой работы является реализация криптографического алгоритма Blowfish на языке программирования С++ и разработка программного продукта, который будет шифровать/расшифровывать данные по реализованному алгоритму.

     Для достижения поставленной цели необходимо будет решить следующие задачи:

  1. Дать определение основным понятием криптографии;
  2. Описать работу алгоритма Blowfish;
  3. Реализовать на практике алгоритм Blowfish;
  4. Описать работу разработанного программного продукта.

     Практическая  значимость: поскольку вопрос защиты информации остается актуальный и по сегодняшней день, то реализованный алгоритм шифрования данных, в рамках данной курсовой работы, и разработанный программный продукт, реализующий шифрование данных по этому алгоритму, найдут свое применение в коммерческих организациях, поскольку именно там наиболее остро стоит вопрос об обеспечении безопасности информации.

 

  1. ПОНЯТИЕ ШИФРОВАНИЯ ДАННЫХ
 

    Криптография  – наука о защите информации от прочтения ее посторонними. Защита достигается путем шифрованием, т.е. преобразованием, делая труднораскрываемым по входным данным, без знания защищенных входных данных специальной ключевой информации – ключа. Под ключом понимается легко изменяемая часть криптосистемы, шифрованное преобразование, хранящаяся в тайне и определяющая возможные случаи. Шифрование является наиболее широко используемым криптографическим методом сохранения конфиденциальности информации, он защищает данные от несанкционированного ознакомления с ними. Криптографическими средствами защиты информации называются специальные методы и средства преобразования информации в результате, которых маскируется ее содержание. Желательно, чтобы методы шифрования обладали минимум двумя свойствами:

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

     Для многих людей слово «шифрование» вызывает образы шпионов, тайных операций и дешифровщиков, которые лихорадочно работают над расшифровкой вражеских сообщений. Собственно, шифрование - бесценный инструмент для безопасного хранения конфиденциальной информации.

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

     Существуют  два основных метода шифрования данных. Один подход заключается в использовании  асимметричного PKI (Public-Key Infrastructure) шифрования. PKI криптография основана на паре криптографических ключей: один ключ является частным, и известен только конечным пользователям, в то время как другой - публичный, и может быть доступен всем.

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

     Другой  метод шифрования данных - использование  симметричного ключа защиты, более  известного как «секретный ключ». В общем случае, он быстрее, но он менее безопасный, чем PKI. Симметричные алгоритмы шифрования используют один и тот же ключ для шифрования и расшифровки сообщений. Симметричные алгоритмы работают лучше, когда ключи распределены среди ограниченного числа доверенных лиц. Поэтому, симметричное шифрования может быть достаточно легко нарушено и используется для сохранения относительно неважной информации только в течении короткого периода времени [10].

     Все алгоритмы симметричного шифрования можно разделить на алгоритмы  блочного шифрования (block ciphers) и алгоритмы потокового шифрования (stream ciphers). Алгоритмы блочного шифрования используют для работы наборы данных фиксированной длины, т.е. шифруемое сообщение разбивается на блоки, последовательно обрабатываемые алгоритмом. Результатом обработки одного блока текста является шифроблок такого же размера. Размер блока зависит от алгоритма (обычно 8, 16, 32 или 64 байта). Каждый блок сообщения может обрабатываться независимо от других (т.н. режим работы Electronic Book, ЕСВ) или для каждого блока может использоваться результат обработки предыдущего блока (т.н. режим работы Cipher Block Chaining, СВС).

     Алгоритмы потокового шифрования используют генератор  псевдослучайной последовательности для получения ключевого потока (keystream), с длиной, равной длине сообщения. После этого ключевой поток и сообщение комбинируются с помощью операции XOR для получения шифротекста [1].

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

     Обмен информацией осуществляется в 3 этапа:

    1. отправитель передает получателю ключ (в случае сети с несколькими абонентами у каждой пары абонентов должен быть свой ключ, отличный от ключей других пар);
    2. отправитель, используя ключ, зашифровывает сообщение, которое пересылается получателю;
    3. получатель получает сообщение и расшифровывает его [5].

     Наибольшую  известность в мире среди алгоритмов шифрования получили алгоритмы, выступавшие  в разное время как стандарты  США: DES, Triple DES и AES. На самом деле алгоритмов шифрования достаточно много, они предназначены для различных применений и реализованы в разных средствах шифрования [7].

     Произведем  сравнение криптографического стандарта России ГОСТ 28147-89 с алгоритмом Blowfish. Сравнение алгоритмов приведено в таблице наже 1.

     Таблица1. Сравнение алгоритмов

Название  характеристики ГОСТ 28147-89 Blowfish
Размер  ключа, бит 256 32-448
Длина блока, бит 64 64
Число раундов 32 16
Скорость  шифрования на Intel 486SX/33МГц (Кбайт/с) 65 135
Основные  операции Сложение по модулю 232,перестановка, побитовое исключающее ИЛИ, циклический сдвиг Сложение по модулю 232,подстановка, побитовое исключающее ИЛИ
Криптостойкость Для атаки требуется 235 выбранных открытых текстов Для атаки требуется  2129 выбранных открытых текстов
Примечание Эффективность и высокое быстродействие, наличие защиты от навязывания ложных данных и одинаковый цикл. Сеть Фейстеля; быстр при шифровании, медленная установка ключа; сравнительно прост; имеет небольшое пространство слабых ключей; имеет большой запас прочности
 

     Как видно из таблицы алгоритм Blowfish обеспечивает наибольшую скорость шифрования данных и является наиболее устойчив к криптоанализу по сравнению с ГОСТ 28147-89. Но надо заметить, что скорость шифрования алгоритма во многом зависит от используемой техники и системы команд. На различных архитектурах один алгоритм может значительно опережать по скорости его конкурентов, а на другом ситуация может сравняться или даже измениться прямо в противоположную сторону. Более того, программная реализация значительно зависит от используемого компилятора. Использование ассемблерного кода может повысить скорость шифрования. На скорость шифрования влияет время выполнения операций mov, add, xor, причём время выполнения операций увеличивается при обращении к оперативной памяти. 

  1. ОПИСАНИЕ  АЛГОРИТМА BLOWFISH
 

     Алгоритм  Blowfish был разработан Брюсом Шнайером в 1994 г. Автор алгоритма предложил его в качестве замены стандарту DES. Несомненно, в тот момент замена DES новым стандартом шифрования была уже актуальна из-за короткого ключа DES, который к тому времени было возможно найти путем полного перебора.

     Blowfish оказался весьма удачным алгоритмом. Он широко реализован в различных  шифровальных средствах. Однако  заменой стандарту DES Blowfish все  же не стал [4].

    2.1 Структура алгоритма

 

     Поскольку Blowfish предполагался в качестве замены алгоритма DES, он так же, как и DES, шифрует  данные 64-битными блоками. Ключ алгоритма  имеет переменный размер - от 32 до 448 бит.

     Алгоритм  представляет собой сеть Файстеля, его структура приведена на рис. 1. Шифрование данных выполняется за 16 раундов, в каждом из которых над левым 32-битным субблоком данных проводятся следующие действия:

    1. Значение субблока складывается с ключом i-го раунда Ki операцией XOR, результат операции становится новым значением субблока.
    2. Субблок обрабатывается функцией F (описана ниже), результат обработки накладывается на правый субблок операцией XOR.
    3. Субблоки меняются местами во всех раундах, кроме последнего.

Рисунок 1. – Структура алгоритма Blowfish

     После 16 раундов выполняется наложение  на субблоки еще двух подключей: K17 и K18 складываются операцией XOR с правым и левым субблоками соответственно.

     Функция F (рис. 2) обрабатывает субблок следующим образом:

    1. 32-битное входное значение делится на четыре фрагмента по 8 бит, каждый из которых прогоняется через одну из таблиц замен S1...S4 с получением четырех 32-битных выходных фрагментов. Таблицы замен содержат по 256 значений по 32 бита, они не являются фиксированными и зависят от ключа шифрования. Принципы их вычисления подробно описаны ниже.
    2. Первые два выходных фрагмента складываются по модулю 232.
    3. Результат предыдущего шага складывается операцией XOR с третьим выходным фрагментом.
    4. Выходное значение функции F получается путем сложения результата предыдущего шага с четвертым выходным фрагментом по модулю 232.

     Иначе говоря, функцию F можно определить так:

     F(x) = ( (S1(x1) + S2(x2) mod 232) (+) S3(x3) ) + S4(x4) mod 232,

     где x1...x4 - 8-битные фрагменты входного значения x.

Рисунок 2. – Функция F алгоритма Blowfish

     Расшифрование выполняется аналогично шифрованию, но ключи K1...K18 используются в обратном порядке [7].

    2.2 Процедура расширения ключа

 

     Задача  процедуры расширения ключа состоит  в вычислении на основе ключа шифрования значений ключей раунда K1...K18 и таблиц замен S1...S4. Для этого используется весьма сложная процедура расширения ключа, состоящая из следующих шагов:

  1. Исходные значения ключей раунда и таблиц замен инициализируются фиксированной псевдослучайной строкой, в качестве которой используется шестнадцатеричная запись дробной части числа p. Значения таблиц замен инициализируются аналогично инициализации ключей раундов, которые заполняются последующими знаками дробной части числа p.
  2. Операцией XOR на K1 накладываются первые 32 бита ключа шифрования, на K2 - следующие 32 бита и т. д. - до K18. Если ключ шифрования короче, чем необходимо для наложения на K1...K18, то он накладывается циклически.
  3. С использованием полученных ключей раунда и таблиц замен выполняется шифрование алгоритмом Blowfish блока данных, состоящего из 64 нулевых бит. Результат становится новым значением ключей K1 и K2.
  4. Результат предыдущего этапа снова шифруется алгоритмом Blowfish (причем уже с измененными значениями ключей K1 и K2), в результате получаются новые значения ключей K3 и K4.
  5. Шифрование выполняется до тех пор, пока новыми значениями не будут заполнены все ключи раунда и таблицы замен [7].

    2.3 Достоинства и  недостатки алгоритма

 

     В своей книге "Прикладная криптография" Брюс Шнайер отметил следующие ограничения алгоритма Blowfish. Во-первых, "...алгоритм Blowfish не годится для применения в случаях, где требуется частая смена ключей". Процедура расширения ключа ресурсоемка, поэтому одно из достоинств алгоритма Blowfish - высокая скорость шифрования - проявляется только в тех случаях, если на одном ключе шифруется достаточно большой объем информации. И наоборот, если менять ключ после каждого из шифруемых блоков, скорость алгоритма становится катастрофически низкой именно из-за необходимости каждый раз выполнять расширение ключа. Сам Шнайер рекомендует в приложениях, где критична скорость, хранить уже развернутый ключ (т. е. значения K1 ... K18 и S1...S4) и загружать его целиком вместо того, чтобы выполнять расширение исходного ключа.

     Далее, "...большие требования к памяти не позволяют использовать этот алгоритм в смарт-картах". Стоит сказать, что принципиальная возможность  реализации алгоритма в смарт-картах была одним из важных условий при  выборе нового стандарта шифрования США на конкурсе AES, т.е. данный недостаток алгоритма Blowfish можно считать серьезным [7].

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

     Алгоритм Blowfish имеет и достаточно важные преимущества, в частности:

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

     Стоит, однако, сказать, что известный эксперт  Серж Воденэ (Serge Vaudenay) обнаружил, что методом дифференциального криптоанализа r-раундового алгоритма Blowfish с известными таблицами замен можно вычислить значения K1...K18 при наличии 28r+1 выбранных открытых текстов. Это неактуально для полнораундовой версии алгоритма (и тем более для описанной выше полноценной версии с вычисляемыми таблицами замен), но при использовании слабого ключа (а Воденэ обнаружил также у алгоритма Blowfish наличие слабых ключей, которые приводят к генерации слабых таблиц замен) выбранных открытых текстов требуется существенно меньше: 24r+1. Вероятность, что произвольный ключ окажется слабым, составляет 2-14. Данная атака некритична, поскольку для полноценной версии алгоритма слабые ключи не страшны [3].

     Явные достоинства и отсутствие критичных  недостатков предопределили широкое  использование алгоритма Blowfish.

 

  1. ПРАКТИЧЕСКАЯ  РЕАЛИЗАЦИЯ АЛГОРИТМА BLOWFISH
 

     Первым  шагом в реализации алгоритма  будет написание класса с именем TBlofish. Данный класс будет содержать:

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

     Вспомогательные методы класса и поля помещаем в директиву private. А метод, который шифруют, расшифровывает и производит инициализацию таблиц замен и таблицу ключей помещаем в директиву public. В директиву public также помещаем конструктор и деструктор, которые используются для создания и удаления объектов этого класса.

     Данный  класс имеет следующий вид: 

     class TBlowfish{

     private:

           unsigned int S1[256];

           unsigned int S2[256];

           unsigned int S3[256];

           unsigned int S4[256];

           unsigned int key[18];

           unsigned int F(unsigned int);

           void final(unsigned int*, int);