Программная реализация режима сцепления блоков шифра «Blowfish»

Министерство образования и науки РФ БРЯНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра «Информатика и программное обеспечение»

программная Реализация режима сцепления блоков шифра «BlowFish»

КУРСОВАЯ РАБОТА Руководитель доц. Дергачев К.В.

Студент Реденков А.Н.

БРЯНСК 2013

1. АНАЛИТИЧЕСКАЯ ЧАСТЬ

1.1 Blowfish

1.2 DES

1.3 IDEA

1.4 ГОСТ 28 147–89

1.5 Вывод

1.6 Режимы работы

1.6.1 Режим электронной кодовой таблицы (ECB)

1.6.2 Режим сцепления блоков (CBC)

1.6.3 Режим обратной связи по шифр-тексту

1.6.4 Режим обратной связи по выходу (OFB)

2. Конструкторская часть

2.1 Общий алгоритм

2.2 Расширение ключа

2.3 Реализация сети Фейстеля

2.4 Режим сцепления блоков

3. Экспериментальная часть

3.1 Руководство пользователя

3.2 Эксперименты

3.2.1 Стандартный сценарий

3.2.2 Проверка использования инициализирующего вектора

3.2.3 Проверка распространения ошибки

3.2.4 Проверка на потерю части сообщения

3.2.5 Проверка идентифицирующего блока Список литературы

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

Отличительными особенностями этого алгоритма стала более высокая степень криптостойкости, нежели алгоритма DES (в том числе за счет использования переменной длины ключа, до 448 бит), высокая скорость шифрации/дешифрации (за счет генерации таблиц замены) и конечно — возможность его свободного применения для любых целей.

Название алгоритма символизирует один из этапов работы: расширение ключа от 448 бит до 4168 байт, подобно иглобрюхой рыбе (англ. Blowfish).

ключ алгоритм ошибка шифр blowfish

1. АНАЛИТИЧЕСКАЯ ЧАСТЬ

1.1 Blowfish

BlowFish — алгоритм 64-битного блочного шифра с ключом переменной длины (до 448 бит).

В общем случае алгоритм состоит из двух этапов — расширение ключа и шифрация/дешифрация исходных данных (Рис.1).

Рис. 1 Общий алгоритм

Шифрация данных, а также создания матрицы раундовых ключей и подстановки, происходит через использование сети Фейстеля, состоящей в свою очередь из 16 раундов, но с некоторыми особенностями генерации и использования раундовых ключей (Рис.2).

Рис. 2 Измененная сеть Фейстеля Функция раунда F весьма проста и использует только операции XOR и сложение по модулю 2³².

На этапе расширения ключа, исходный ключ преобразуется в матрицу раундовых ключей (P) и матрицу подстановки (S, Substitution-box) (или замены), общим объемом в 4168 байт. При этом выполняется 521 полная итерация сети Фейстеля. Всё это является весьма трудозатратной операцией, и именно поэтому алгоритм Blowfish не рекомендуется использовать там, где требуется частая смена ключа.

1.2 DES

Симметричный блочный шифр с длиной ключа 56 бит.

Процесс шифрования заключается в начальной перестановке битов 64-битового блока с помощью специальной таблицы, шестнадцати циклах шифрования и, наконец, обратной перестановке битов (рис.3). Цикл шифрования представляет собой сеть Фейстеля. Из-за небольшого числа возможных ключей (всего 2⁵⁶), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время.

Рис. 3 Алгоритм DES

1.3 IDEA

Симметричный блочный шифр с длиной ключа 128 бит и размером блока 64 бита.

Процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции:

· умножение по модулю 2¹⁶ + 1 = 65 537, причем вместо нуля используется 2¹⁶

· сложение по модулю 2¹⁶

· побитовое исключающее ИЛИ После выполнения выходного преобразования конкатенация подблоков D₁', D₂', D₃' и D₄' представляет собой зашифрованный текст. Затем берется следующий 64-битный блок незашифрованного текста и алгоритм шифрования повторяется. Так продолжается до тех пор, пока не зашифруются все 64-битные блоки исходного текста (рис. 4).

Рис. 4 Алгоритм IDEA

1.4 ГОСТ 28 147–89

Блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — сеть Фейстеля. Для зашифровывания в этом режиме 64-битный блок открытого текста сначала разбивается на две половины (младшие биты — A, старшие биты — B). На i-ом цикле используется подключ K_i:

A_i+1 = B_i?f (A_i, K_i)

B_i+1 = A_i

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K₁…K₈.

Ключи K₉…K₂₄ являются циклическим повторением ключей K₁…K₈ (нумеруются от младших битов к старшим). Ключи K₂₅…K₃₂ являются ключами K₈…K₁.

После выполнения всех 32 раундов алгоритма, блоки A₃₃ и B₃₃ склеиваются (обратите внимание, что старшим блоком становится A₃₃, а младшим — B₃₃) — результат есть результат работы алгоритма.

Основные проблемы ГОСТа связаны с неполнотой стандарта в части генерации ключей и таблиц замен.

Рис. 5 Шифрация ГОСТ 28 147–89

1.6 Режимы работы

1.6.1 Режим электронной кодовой таблицы (ECB)

В этом режиме каждый из блоков кодируется независимо с использованием одного и того же ключа (рис.6). Основное достоинство этого алгоритма — простота реализации. Недостаток — относительно слабая устойчивость против криптоанализа.

Рис. 6 Режим ECB

1.6.2 Режим сцепления блоков (CBC)

В этом режиме каждый последующий блок исходного текста складывается по модулю 2 с предыдущим блоком шифр-текста. Самый первый блок складывается со случайно сгенерированным блоком — вектором инициализации IV, который добавляется в начало шифр-текста (рис.7).

Режим CBC является самовосстанавливающимся. Ошибка в шифр-тексте влияет только на текущий и следующий за ним блок. Последний блок шифр-текста может служить кодом аутентификации сообщения.

Рис. 7 Режим CBC

1.6.3 Режим обратной связи по шифр-тексту

Исходный файл считывается последовательными t-битовыми блоками (t <= 64). 64-битовый сдвиговый регистр вначале содержит вектор инициализации IV, выравненный по правому краю.

Для всех i = 1… n блок шифртекста C (i) определяется следующим образом:

C (i) = M (i) XOR P (i-1) ,

где P (i-1) — старшие t битов операции Crypt (С (i-1)).

Обновление сдвигового регистра осуществляется путем удаления его старших t битов и дописывания справа C (i)(рис. 8).

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

Рис. 8 Режим CFB

1.6.4 Режим обратной связи по выходу (OFB)

Данный режим отличается от CFB только способом формирования сдвигового регистра (рис. 9).

Режим OFB имеет следующее преимущество по сравнению с режимом CFB: ошибки, возникающие в результате передачи по каналу с шумом, при дешифровании не «размазываются» по всему шифротексту, а локализуются в пределах одного блока. Однако, это свойство дает дополнительные параметры для криптоанализа, поэтому данный режим используется только при необходимости (высокий уровень помех).

Рис. 9 Режим OFB

1.6 Вывод

В программной реализации по сравнению с DES IDEA в два раза быстрее, что является существенным повышением скорости, длина ключа у IDEA имеет размер 128 бит, против 56 бит у DES, что является хорошим улучшением против полного перебора ключей. Вероятность использования слабых ключей очень мала и составляет 2^-64. IDEA быстрее алгоритма ГОСТ 28 147–89. Преимуществом также является хорошая изученность и устойчивость к общеизвестным средствам криптоанализа.

Blowfish показывает более высокие результаты при использовании кэша для хранения всех подключей. В этом случае он опережает алгоритмы DES, IDEA. На отставание IDEA влияет операция сложения по модулю 2³²+1.

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

Среди режимов шифрования наиболее предпочтительными являются CBC и CFB, за счет высокой криптостойкости. Выбор зависит от способа применения шифра — блочный или поточный.

2. Конструкторская часть

2.1 Общий алгоритм

Рис. 10 Общий алгоритм работы

Реализация алгоритма осуществляется классом Blowfish.

При создании экземпляра класса, конструктор принимает на вход ключ шифрования и сразу проводит операцию расширения.

public BlowFish (string hexKey)

{

randomSource = new RNGCryptoServiceProvider ();

SetupKey (HexToByte (hexKey));

}

Шифрация в режиме сцепления блоков производится методом Crypt_CBC (byte[] text, bool decrypt), который принимает на вход текст для шифрации и флаг действия.

2.2 Расширение ключа

Рис. 11 Алгоритм расширения ключа

В программе расширение ключа реализовано функцией SetupKey (byte[] cipherKey), которая принимает на вход массив байтов исходного ключа.

private void SetupKey (byte[] cipherKey)

{

bf_P = SetupP ();

bf_s0 = SetupS0();

bf_s1 = SetupS1();

bf_s2 = SetupS2();

bf_s3 = SetupS3();

key = new byte[cipherKey.Length];

Buffer.BlockCopy (cipherKey, 0, key, 0, cipherKey. Length);

int j = 0;

for (int i = 0; i < 18; i++)

{

uint d = (uint)(((key[j % cipherKey. Length] * 256 + key[(j + 1) % cipherKey. Length]) * 256 + key[(j + 2) % cipherKey. Length]) * 256 + key[(j + 3) % cipherKey. Length]);

bf_P[i] ^= d;

j = (j + 4) % cipherKey. Length;

}

xl_par = 0;

xr_par = 0;

for (int i = 0; i < 18; i += 2)

{

encipher ();

bf_P[i] = xl_par;

bf_P[i + 1] = xr_par;

}

for (int i = 0; i < 256; i += 2)

{

encipher ();

bf_s0[i] = xl_par;

bf_s0[i + 1] = xr_par;

}

for (int i = 0; i < 256; i += 2)

{

encipher ();

bf_s1[i] = xl_par;

bf_s1[i + 1] = xr_par;

}

for (int i = 0; i < 256; i += 2)

{

encipher ();

bf_s2[i] = xl_par;

bf_s2[i + 1] = xr_par;

}

for (int i = 0; i < 256; i += 2)

{

encipher ();

bf_s3[i] = xl_par;

bf_s3[i + 1] = xr_par;

}

}

2.3 Реализация сети Фейстеля

Рис. 12 Реализация сети Фейстеля

В программе сеть Фейстеля реализована функцией encipher (). Функция round (uint a, uint b, uint n) реализует функцию итерации. Переменные a и b — левый и правый подблоки, n — номер итерации.

private void encipher ()

{

xl_par ^= bf_P[0];

for (uint i = 0; i < 16; i+= 2)

{

xr_par = round (xr_par, xl_par, i + 1);

xl_par = round (xl_par, xr_par, i + 2);

}

xr_par = xr_par ^ bf_P[17];

uint swap = xl_par;

xl_par = xr_par;

xr_par = swap;

}

private uint round (uint a, uint b, uint n)

{

uint x1 = (bf_s0[wordByte0(b) ] + bf_s1[wordByte1(b) ]) ^ bf_s2[wordByte2(b) ];

uint x2 = x1 + bf_s3[this.wordByte3(b) ];

uint x3 = x2 ^ bf_P[n];

return x3 ^ a;

}

2.4 Шифрация в режиме сцепления блоков

Реализация шифрования в режиме сцепления блоков.

Ниже приведен фрагмент функции Crypt_CBC (byte[] text, bool decrypt), демонстрирующий цикл шифрации текста.

Функция XorBlock () производит операцию XOR над двумя блоками данных.

Функция BlockEncrypt (ref byte[] block) непосредственно шифрует блок данных.

for (int i = 0; i < plainText. Length; i += 8)

{

Buffer.BlockCopy (plainText, i, block, 0, 8);

XorBlock (ref block, iv);

BlockEncrypt (ref block);

Buffer.BlockCopy (block, 0, iv, 0, 8);

Buffer.BlockCopy (block, 0, plainText, i, 8);

}

private void BlockEncrypt (ref byte[] block)

{

SetBlock (block);

encipher ();

GetBlock (ref block);

}

3. Экспериментальная часть

3.1 Руководство пользователя

Интерфейс пользователя состоит из двух кнопок (рис.13).

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

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

Рис. 13 Скриншот программы

Программа корректно работает с текстами содержащими русские и латинские символы, с текстами большого размера.

3.2 Эксперименты

3.2.1 Стандартный сценарий

3.2.2 Проверка использования инициализирующего вектора

3.2.3 Проверка распространения ошибки

3.2.4 Проверка на потерю части сообщения

3.2.5 Проверка идентифицирующего блока

1. IT портал [http://habrahabr.ru].

2. A blog covering security and security technology [www.schneier.com].

3. М. Масленников, Практическая криптография / Масленников М. — Спб.: БХВ-Петербург, 2003. — 458 с.

4. С. Панасенко, Алгоритмы шифрования / Панасенко С. — СПб.: БХВ-Петербург, 2009. — 576 с.

5. И. Ященко, Основные математические понятия криптографии / Ященко И. В. — М.: Москва, 2003.