Реализация алгоритма симметричного шифрования ГОСТ 28147-89

Размещено на http://www.allbest.ru/

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

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

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»

ФАКУЛЬТЕТ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Контрольная работа

по дисциплине Криптографические методы защиты информации

Реализация алгоритма симметричного шифрования ГОСТ 28147-89

Выполнил

Скворцова А.С.

Проверила

Коковихина Н.А.

г. Йошкар-Ола 2015

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

2. КРИПТОАНАЛИЗ АЛГОРИТМА

2.1 Анализ таблицы замен

2.2 Узлы замены (S - блоки)

2.3 Модификации алгоритма и их анализ

2.4 Анализ полнораундового алгоритма

ЗАКЛЮЧЕНИЕ

ИСТОЧНИКИ ИНФОРМАЦИИ

ВВЕДЕНИЕ

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

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

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

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

Задачей данной работы является реализация алгоритма симметричного шифрования ГОСТ 28147-89.

ГОСТ 28147-89 -- советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название -- «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием может выполнять функции поточного шифроалгоритма.

По некоторым сведениям, история этого шифра гораздо более давняя. Алгоритм, положенный впоследствии в основу стандарта, родился, предположительно, в недрах Восьмого Главного управления КГБ СССР (ныне в структуре ФСБ), в Воронежском НИИ Связи, вероятно, ещё в 1980-х годах в рамках проектов создания программных и аппаратных реализаций шифра для различных вычислительных платформ.

С момента опубликования ГОСТа на нём стоял ограничительный гриф «для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года. История создания шифра и критерии разработчиков по состоянию на 2015 год не обнародованы.

Позже вместе с новым алгоритмом «Кузнечик» был опубликован как часть стандарта ГОСТ Р 34.12-2015 [1].

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

Отечественный алгоритм шифрования ГОСТ 28147-89 определен в стандарте. Алгоритм шифрует данные 64-битными блоками с использованием 256-битного ключа шифрования. Выполняется 32 раунда преобразований, в каждом из которых предусмотрены операции в соответствии с рисунком 1.

Рисунок 1.1.

1. Один из 32-битных субблоков данных складывается с 32-битным значением ключа раунда Ki по модулю 232.

2. Результат предыдущей операции разбивается на 8 фрагментов по 4 бита, которые параллельно «прогоняются» через 8 таблиц замен S1…S8.

3. 4-битные фрагменты (после замен) объединяются обратно в 32-битный субблок, значение которого циклически сдвигается влево на 11 бит.

4. Обработанный предыдущими операциями субблок накладывается на необработанный с помощью побитовой логической операции «исключающее или» (XOR).

5. Субблоки меняются местами [2].

Процедура расширения ключа в алгоритме ГОСТ 28147-89, фактически, отсутствует: в раундах шифрования последовательно используются 32-битные фрагменты K1…K8 исходного 256-битного ключа шифрования в следующем порядке: K1, K2, K3, K4, K5, K6, K7, K8, за исключением последних 8 раундов - в раундах с 25-го по 31-й фрагменты используются в обратном порядке.

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

1. В прямом порядке - в первых 8 раундах;

2. В остальных раундах - в обратном порядке.

Выделяют четыре режима работы ГОСТ 28147-89:

· Описанный выше режим простой замены;

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

· Режим вычисления имитовставки - криптографической контрольной суммы, используемой для подтверждения целостности данных; в данном режиме выполняется 16 раундов преобразований вместо 32-х.

Алгоритм ГОСТ 28147-89 можно использовать и в различных общеупотребительных режимах шифрования. Кроме того, на основе данного алгоритма построен отечественный стандарт хеширования ГОСТ Р 34.11-94.

Как видно из описания, алгоритм ГОСТ 28147-89 является весьма простым в реализации, что является его несомненным достоинством [3].

2. КРИПТОАНАЛИЗ АЛГОРИТМА

В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на английский язык и опубликовано, именно после этого стали появляться результаты его анализа, выполненного зарубежными специалистами; однако, в течение значительного времени не было найдено каких-либо атак, приближающихся к практически осуществимым [4].

2.1 Анализ таблицы замен

Поскольку таблицы замен в стандарте не приведены, в ряде работ высказывается предположение, что «компетентная организация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако известнейший эксперт Брюс Шнайер (Bruce Schneier) называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен, применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно привести два следующих факта из истории стандарта шифрования США DES:

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

Были попытки усилить DES против линейного и дифференциального криптоанализа путем использования более стойких таблиц замен. Такие таблицы были предложены, например, в алгоритме s5DES. Но заменить DES на s5DES было невозможно, поскольку таблицы замен жестко определены в стандарте, соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.

В ряде работ ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом). Однако, доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически:

1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т.е. значения z = f(0), где f() - функция раунда алгоритма. Этот этап занимает порядка 232 операций шифрования.

2. С помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 211 операций [5].

2.2 Узлы замены (S - блоки)

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

В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, то есть разработчиком алгоритма.

2.3 Модификации алгоритма и их анализ

Криптоанализ модификаций алгоритма ГОСТ 28147-89:

1. Алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно, в раундах с 25-го по 32-й подключи используются в прямом порядке, т.е. точно так же, как и в предыдущих раундах алгоритма;

2. 20-раундового алгоритма GOSTA, в раунде которого для наложения ключа используется операция XOR вместо сложения по модулю 232.

По результатам анализа сделан вывод о том, что GOST-H и GOSTA слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей.

Еще одна модификация алгоритма:

Таблицы S1…S8 обязательно должны быть различными; в каждом раунде алгоритма должна выполняться их перестановка по определенному закону. Данная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т.е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.

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

2.4 Анализ полнораундового алгоритма

Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо модификаций. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако, сильные таблицы замен делают такую атаку абсолютно непрактичной.

Отечественные ученые А.Г. Ростовцев и Е.Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью.

В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 бит секретного ключа. Для атаки требуется 235 выбранных открытых текстов и 236 операций шифрования. Как видно, данная атака, практически, бесполезна для реального вскрытия алгоритма.

ПРАКТИЧЕСКАЯ ЧАСТЬ

В данной работе выполняется реализация одного из режимов работы ГОСТ 28147 - 89: режима гаммирования. При работе в режиме гаммирования описанным ниже образом формируется криптографическая гамма, которая затем побитно складывается по модулю 2 с исходным открытым текстом для получения шифротекста.

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

Выработка гаммы происходит на основе ключа и так называемой синхропосылки, которая задает начальное состояние генератора.

Основные шаги реализованы в структуре BasicStep:

Метод BasicStep. 64-битный блок открытого текста сначала разбивается на две половины (младшие биты -- A, старшие биты -- B).

Метод FirstStep. Вычисляется функция : Ai и Ki складываются по модулю 232.

Метод SecondStep. Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа -- восемь, то есть столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15 (конкретный вид S-блоков в стандарте не определен). Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая -- на вход второго и т.д, в соответствии с рисунком 2.1.

Рисунок 2.1.

Если узел S-блока выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12., и если на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Метод StartGamma. Полученные значения записываются во вспомогательные 32-разрядные регистры N1 и N2 - младшие и старшие биты соответственно. N1 суммируется по модулю 232 с константой C2 = 101010116. N2 суммируется по модулю 232-1 с константой C1 = 101010416. N1 и N2 переписываются соответственно в S0 и S1, которые затем шифруются с использованием алгоритма простой замены. Полученный результат является 64 битами гаммы.

Код описанных методов представлен в приложении А.

Рисунок 2.2. Схема работы в режиме гаммирования

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

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

ЗАКЛЮЧЕНИЕ

Произведя анализ и произведя реализацию алгоритма шифрования ГОСТ 28147 - 89, можно подвести итоги.

С точки зрения создания эффективных реализаций алгоритм ГОСТ 28147-89 обладает целым рядом преимуществ.

Во-первых, это простое ключевое расписание.

Во-вторых, это использование 4-битовых узлов замены, которые в программных реализациях хорошо осуществляются с помощью векторных инструкций, а в аппаратных требуют крайне мало ресурсов.

И в-третьих, это простое раундовое преобразование в целом, которое хорошо ложится как на программные, так и на аппаратные реализации. При этом алгоритм до сих пор обладает колоссальным, с точки зрения практики, запасом прочности.

Также можно привести в промер возможные применения данного алгоритма:

· Использование в S/MIME (PKCS#7, Cryptographic Message Syntax).

· Использование для защиты соединений в TLS (SSL, HTTPS, WEB).

· Использование для защиты сообщений в XML Encryption.

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Мельников В. В. Защита информации в компьютерных системах. -- М.: Финансы и статистика, 1997.

2. Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях. -- М.: Радио и связь, 1999.

3. Харин Ю. С., Берник В. И., Матвеев Г. В. Математические основы криптологии. -- Мн.: БГУ, 1999.

4. Герасименко В. А., Малюк А. А. Основы защиты информации. -- М.: МГИФИ, 1997.

5. Леонов А.П., Леонов К.П., Фролов Г.В. Безопасность автоматизированных банковских и офисных технологий. -- Мн.: Нац. кн. палата Беларуси, 1996.

6. Зима В. М., Молдовян А. А., Молдовян Н. А. Компьютерные сети и защита передаваемой информации. -- СПб.: СПбГУ, 1998.

7. Шнайер Б. 14.1 Алгоритм ГОСТ 28147-89 // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. -- М.: Триумф, 2002. -- С. 373-377. -- 816 с. -- 3000 экз. -- ISBN 5-89392-055-4.

8. Popov, V., Kurepkin, I., and S. Leontiev Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms (англ.) // RFC 4357. -- IETF, January 2006.

Размещено на Allbest.ru