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

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ»

КУРСКИЙ ИНСТИТУТ СОЦИАЛЬНОГО ОБРАЗОВАНИЯ

(ФИЛИАЛ) РГСУ

Инженерно-технический факультет

Кафедра информационных систем и информационного права

РЕФЕРАТ

по дисциплине: «Методы и средства защиты компьютерной информации»

на тему: «Блочные алгоритмы. Алгоритм Blowfish»

Выполнил студентка 4 курса группы 1

специальности «Автоматизация и управление»

очной формы обучения

Буранчикова Екатерина Викторовна

Проверил: Погосян Сергей Левонович

Реферат защищен с оценкой

_______________

«__»_______20__г.

Курск 2013г.

АЛГОРИТМ BLOWFISH

Алгоритм Blowfish был разработан Брюсом Шнайером в 1994 г. Автор алгоритма предложил его в качестве замены стандарту DES.
Blowfish оказался весьма удачным алгоритмом. Он широко реализован в различных шифровальных средствах - на сайте Брюса Шнайера (http://www.schneier.com) приведен список из примерно 150 продуктов, которые шифруют алгоритмом Blowfish.

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

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

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

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

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

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

Структура алгоритма представлена на рисунке 1.

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

Функция F (рис. 2) обрабатывает субблок следующим образом:
1. 32-битное входное значение делится на четыре фрагмента по 8 бит, каждый из которых прогоняется через одну из таблиц замен S1... S4 с получением четырех 32-битных выходных фрагментов. Таблицы замен содержат по 256 значений по 32 бита, они не являются фиксированными и зависят от ключа шифрования. Принципы их вычисления подробно описаны ниже.
2. Первые два выходных фрагмента складываются по модулю .
3. Результат предыдущего шага складывается операцией XOR с третьим выходным фрагментом.
4. Выходное значение функции F получается путем сложения результата предыдущего шага с четвертым выходным фрагментом по модулю .
Функцию F можно определить так:
F(x) = ((S1(x1) + S2(x2) mod ) (+) S3(x3)) + S4(x4) mod , где x1...x4 - 8-битные фрагменты входного значения x.

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

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

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

Подключи вычисляются с использованием самого алгоритма Blowfish.

Задача процедуры расширения ключа состоит в вычислении на основе ключа шифрования значений ключей раунда K 1... K 18 и таблиц замен S1... S4.

Расширение ключа выполняется в 5 этапов:
1. Исходные значения ключей раунда и таблиц замен инициализируются фиксированной псевдослучайной строкой, в качестве которой используется шестнадцатеричная запись дробной части числа pi (пи).

2. Операцией XOR на K 1 накладываются первые 32 бита ключа шифрования, на K 2 - следующие 32 бита и т. д. - до K 18. Если ключ шифрования короче, чем необходимо для наложения на K 1... K 18, то он накладывается циклически.

3. С использованием полученных ключей раунда и таблиц замен выполняется шифрование алгоритмом Blowfish блока данных, состоящего из 64 нулевых бит. Результат становится новым значением ключей K 1 и K 2.

4. Результат предыдущего этапа снова шифруется алгоритмом Blowfish (причем уже с измененными значениями ключей K 1 и K 2), в результате получаются новые значения ключей K 3 и K 4.

5. Шифрование выполняется до тех пор, пока новыми значениями не будут заполнены все ключи раунда и таблицы замен.

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

В процедуре расширения ключа мы видим, что для создания ключа необходима какая-то фиксированная псевдослучайная строка S (набор из любых шестнадцитеричных символов). На строку S c помощью операции XOR накладывается ключ принадлежащий пользователю. В теории для каждого ключа должна соответствовать своя фиксированная псевдослучайная строка S.

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

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

· высокая скорость шифрования на развернутом ключе (как уже упоминалось выше);

· простота алгоритма, снижающая вероятность ошибок при его реализации;

· отсутствие успешных атак на полнораундовую версию алгоритма.

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