VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Данная статья посвящена разработке методов для высокоскоростного шифрования данных по блочному алгоритму «Кузнечик». В ней рассмотрены и показаны все ключевые операции, которые есть в алгоритме. Описана и объяснена методика, благодаря которой достигается значительный прирост скорости, приведено обоснование, почему данная методика работает. Пошагово разъяснен алгоритм создания таблиц предвычислений, которые являются основой высокоскоростного шифрования. Присутствует сравнительный анализ и временные затраты для реализаций на языках C и Python.

This article is dedicated to the development of techniques for high-speed data encryption on the block algorithm "Kuznechik". It discusses and shows all the key operations that are in the algorithm. We describe and explain the procedure by which achieved significant growth rate, given the explanation why this technique works. Explained step by step algorithm for creating tables precomputations, which are the basis of high-speed encryption.. There is a comparative analysis of the costs and time for implementation in C and Python.

Ключевые слова: криптография, блочный шифр, «Кузнечик», ГОСТ Р 34.12-2015, таблица предвычислений.

Keywords: cryptography, block cipher, "Kuznechik", GOST R 34.12-2015, table precomputations.

Блочный шифр «Кузнечик» (Kuznechik, Kuznyechik) — симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа 256 бит, для генерации которого используется сеть Фейстеля.

Данный шифр утверждён в качестве стандарта ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» приказом от 19 июня 2015 года №749-ст. Стандарт вступил в действие с 1 января 2016 года. Шифр разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «Информационные технологии и коммуникационные системы» (ОАО «ИнфоТеКС»). Внесен Техническим комитетом по стандартизации ТК 26 «Криптографическая защита информации»[Криптографическая защита 2015].

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

Новый шифр построен не на сети Фейстеля, а на так называемой SP-сети – это преобразование, которое состоит из нескольких одинаковых раундов, где каждый раунд включает линейное и нелинейное преобразование плюс операция наложения ключа. В SP-сети преобразуется весь входной блок, а не половина, как в сети Фейстеля. Длина входного блока алгоритма – 128 бит, мастер-ключа – 256 бит. Особенности «Кузнечика»:

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

• линейное преобразование можно реализовать сдвиговым регистром.

В алгоритме используется циклически повторяемое раундовое шифрование. Каждый раунд состоит из трех операций: преобразование в подстановочном блоке (Рис.1), линейное преобразование (Рис.2) и сложение с соответствующим раундовым ключом[В ГОСТе…2015].

Рисунок 1 – Преобразование S

Рисунок 2 – Преобразование R

Генерация раундовых ключей начинается с разбиения мастер-ключа пополам, так получается первая пара раундовых подключей. Для генерации последующих пар применяется 8 итераций сети Фейстеля, в каждой итерации используется константа, которая вычисляется путем применения линейного преобразования алгоритма к значению номера итерации (Рис.3)[Бабенко 2015].

Рисунок 3 – Процедура выработки раундовых ключей

На Рис.4 представлена схема шифрования/дешифрования одного блока входных данных, дешифрование реализуется обращением базовых преобразований и применением их в обратном порядке.

Рисунок 4 – Шифрование/дешифрование одного блока данных

Идея скоростного шифрования/дешифрования заключена в построении таблиц предвычислений, имея которые не нужно будет использовать преобразования S/S^-1 и L/L^-1 для каждого байта, тем самым значительно уменьшить количество операций для обработки блока входных данных.

Для реализации скоростного шифрования понадобится всего 1 таблица предвычислений (№1), отражающая совместную работу функций L и S: . Данная таблица содержит все возможные варианты каждого отдельного байта, прошедшего преобразования Sи L. Используется таблица следующим образом: поступивший на вход алгоритма блок данных последовательно сдвигается вправо на необходимое число бит (x % 8 = 0) и логически умножается на 255 (0xff), чтобы получить значение очередного обрабатываемого байта. Это значение выступает индексом для таблицы предвычислений, где по данному индексу содержится значение, прошедшее через преобразования S и L.

В реализации на сайте tk26.ru имеется таблица предвычислений для значений РСЛОС (таблица для умножения размерностью 256*256 значений в поле Галуа), позволяющая быстро вычислять значения R(a). Данная таблица используется для построения необходимых таблиц предвычислений. Т.к. L(a) имеет размер 16 байт, а 1 байт = 8 бит, то всего возможно 4096 различных вариантов входных/выходных данных. В силу того, что каждый байт может изменяться от 00 до ff в 16-ой системе, строим таблицу всех возможных значений входных данных, последовательно изменяя каждый байт 256 раз, на выходе получается таблица из 4096 значений. Для каждого значения полученной таблицы применяется преобразование L, после чего вся таблица подвергается перестановке по S, используя имеющиеся значения как индексы (Рис.5).

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

Рисунок 5 – Генерация таблицы предвычислений №1

Ниже приведен фрагмент стартовой таблицы, в которой для исходного состояния один байт принимает значения от 00 до ff и соответствующий ему фрагмент таблицы №1, отражающий состояние всех байтов после преобразований S и L.

Фрагмент стартовой таблицы:

{0x900000000000000, 0x000000000000000},

{0xa00000000000000, 0x000000000000000},

{0xb00000000000000, 0x000000000000000},

{0xc00000000000000, 0x000000000000000},

{0xd00000000000000, 0x000000000000000},

…………………………………………………………...

{0x000000000000000, 0x00000000000000fa},

{0x000000000000000, 0x00000000000000fb},

{0x000000000000000, 0x00000000000000fc},

{0x000000000000000, 0x00000000000000fd},

{0x000000000000000, 0x00000000000000fe},

{0x000000000000000, 0x00000000000000ff}

Фрагмент таблицы №1:

{0x9bc014fda80bb302,0xe2f5f73397c767f0}, {0x5ddc87ece4d890f4,0xb3ba4eb92079cbeb}, {0xe8b46dff022b323b,0xb91328ea7205eb99}, {0xdbebd6d7ddeeb4c9,0xef75bc0628f689a1}, {0x82c8f4711a1ca9cc,0x99c70b986f3995fa}, {0xbe84685128596eda,0x60bf6596274482a5}, {0xb8e57e3efb6644b2,0x26b3014392a9df4d}, {0xe7a74af7efab73df,0x160dd208608b9efe}, {0x25447cac8052ddd8,0x824a92a5b083e555}, {0x8bbac51624a3c240,0x70d595afc85abd75}, {0x3b6232bc99915fd3,0x1f76a5a2945c0f9b}, {0x5af229704f0c0831,0x55b48515fc58d32f}, {0xc7532be23438915b,0xf14d16f3de72e937}, {0xef9ac363a9ffaafe,0x5f1de346ae24f35d}, {0x321003dba72e345f,0xf6643b95333f2714}, {0x6c1d8fe1cb08b19f,0x66d847a7a8d1238b}, {0x8e0ad8af7f62fd1c,0x15dfc3f1c6202fe9}...

После построения таблицы можно приступать к шифрованию по следующей схеме (прямой порядок ключей): входной блок данных складывается по модулю два с первым ключом, каждый байт полученного значения будет выступать индексом для таблицы №1, таким образом получится 16 значений, которые необходимо сложить по модулю два между собой и со следующим ключом, повторив операцию 9 раз на выходе получится шифртекст (Рис.6).

Рисунок 6 – Процедура шифрования блока данных

Для дешифрования используется метод, описанный в М. Бородиным и соавторами [Borodin et al. 2014].

Исходный алгоритм дешифрования:

Допишем в конец преобразования Sи S^-1:

(1)

В силу линейности преобразования L^-1:

(2)

Выделим и заменим все сочетания из (1) полученными в (2), алгоритм примет вид:

(3)

Для реализации скоростного дешифрования по (3) понадобятся 2 таблицы предвычислений: №2 - , №3 - .

Ввиду того, что алгоритм дешифрования содержит нелинейные операции S/S^-1, скорость обработки входного блока заведомо будет ниже.

Массив №2 строится также как массив №1, только здесь используются обратные операции: нелинейное преобразование S^-1 и линейное L^-1 (Рис.7). Массив №3 строится, также как массив №2, но без применения нелинейного преобразования S^-1 (Рис.8).

Схема дешифрования использует обратный порядок раундовых подключей: входной блок данных подвергается перестановке S, затем следует 9 раундов, в каждом из которых происходит сложение по модулю два 16 значений из таблицы №2 для переставленного блока и 16 значений ключа, полученных из таблицы №3. Полученный результат подвергается перестановке S^-1 и складывается по модулю два с последним (первым) ключом, образуя в результате открытый текст (Рис.9).

Рисунок 7 - Генерация таблицы предвычислений №2

Рисунок 8 - Генерация таблицы предвычислений №3

Рисунок 9 - Процедура дешифрования блока данных

Согласно данным июльской конференции Яндекс «Криптография в России: проблемы применения», а именно словам Станислава Смышляева, на данный момент при реализации на 64-битных системах скорость шифрования составляет 130 МБ/с. (см.:[Рудской 2015]).

На HP Pavilion dv6 Notebook PC Intel(R) Core(TM) i5 CPU M 480 2.67GHz, в системе Linux Mint 17.3 Rosa, реализация шифрования по вышеописанному принципу на языке Python показывает скорость около 5,4 МБ/с, а на языке C – 59 МБ/с. Для шифрования одного блока данных на языке Python требуется 0.000102с, в C - 0.000010c. Из этого следует, что реализация на языке C работает примерно в 10 раз быстрее.

Реализация на языке C выбрана основной, в перспективе проведение анализа кода и проработка участков, которые позволят повысить быстродействие.

Выполненная реализация в дальнейшем будет использована для сокращения времени анализа алгоритма Кузнечик с использованием распределенных многопроцессорных вычислений [Бабенко и соавт. 2014]. Будут рассмотрены различные варианты анализа с использованием современных методов криптоанализа, которые рассматривались авторами ранее применительно к анализу алгоритма шифрования ГОСТ 28147-89 [Babenko et al. SIN 2012; Babenko et al. 2013; Ищукова 2014].

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Бабенко Л.К., Ищукова Е.А., Ломов И.С. Математическое моделирование криптографического алгоритма «Кузнечик» // Информационное противодействие угрозам терроризма. 2015. – № 24. – С. 166 – 176.

2. L. Babenko, E. Ischukova, E. Maro, GOST Encryption Algorithm and Approaches to its Analysis // Theory and Practice of Cryptography Solutions for Secure Information Systems, IGI Global book series Advances in Information Security, Privacy, and Ethics (AISPE) Book Series, Published in the United States of America by Information Science Reference. – P. 34 – 61.

3. Babenko L.K., Ishchukova E.A., Maro E.A., Research about Strength of GOST 28147-89 Encryption Algorithm // Proceedings of the 5th international conference on Security of information and networks (SIN 2012), ACM, New York, NY, USA, pp. 80-84.

4. Бабенко Л.К. Ищукова Е.А. Сидоров И.Д. Параллельные алгоритмы для решения задач защиты информации. - М.: Горячая линия Телеком, 2014. - 304 с.

5. Borodin M., Rybkin A., Urivskiy A. High-Speed Software Implementationof the Prospective 128-bit Block Cipherand Streebog Hash-Function [Электронный ресурс]. URL: https://mjos.fi/doc/rus/ctcrypt14-pre.pdf (дата обращения: 9.11.15).

6. В ГОСТе сидел «Кузнечик» [Электронный ресурс]. URL: http://habrahabr.ru/post/266359/ (дата обращения: 26.10.15).

7. Ищукова Е.А. Оценка стойкости блочных алгоритмов шифрования с использованием линейного криптоанализа // Международный журнал прикладных и фундаментальных исследований №11, 2014. - C.560 - 564. URL: rae.ru/upfs/?section=content&op=show_ article&article_id=6180 (дата обращения: 25.09.15).

8. Рудской В. Российские криптографические стандарты: функции хэширования, блочные шифры и режимы их работы [Электронный ресурс]. URL: https://events.yandex.ru/lib/talks/2973/ (дата обращения: 29.10.15).

9. Криптографическая защита информации Блочные шифры [Электронный ресурс]. URL: https://www.tc26.ru/standard/gost/GOST_R_3412-2015.pdf (дата обращения: 25.11.15).

Код для цитирования: Скопировать