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

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

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

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

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

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

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

 

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

2. ОПИСАНИЕ  АЛГОРИТМА 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. Первые два выходных фрагмента складываются по модулю 2³².
3. Результат предыдущего шага складывается операцией XOR с третьим выходным фрагментом.
4. Выходное значение функции F получается путем сложения результата предыдущего шага с четвертым выходным фрагментом по модулю 2³².

     Иначе говоря, функцию 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 при наличии 2^8r+1 выбранных открытых текстов. Это неактуально для полнораундовой версии алгоритма (и тем более для описанной выше полноценной версии с вычисляемыми таблицами замен), но при использовании слабого ключа (а Воденэ обнаружил также у алгоритма Blowfish наличие слабых ключей, которые приводят к генерации слабых таблиц замен) выбранных открытых текстов требуется существенно меньше: 2^4r+1. Вероятность, что произвольный ключ окажется слабым, составляет 2^-14. Данная атака некритична, поскольку для полноценной версии алгоритма слабые ключи не страшны [3].

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

 

3. ПРАКТИЧЕСКАЯ  РЕАЛИЗАЦИЯ АЛГОРИТМА 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);