Извращения с импортозамещением. Работаем с алгоритмом блочного шифрования «Кузнечик» из ГОСТ 34.12—2015

В настоящее время отечественная криптография базируется на нескольких основных государственных стандартах:

• ГОСТ 34.10. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи (действующая на сегодня редакция 2012 года);
• ГОСТ 34.11. Информационная технология. Криптографическая защита информации. Функция хэширования (действующая на сегодня редакция 2012 года);
• ГОСТ 34.12. Информационная технология. Криптографическая защита информации. Блочные шифры (действующая на сегодня редакция 2015 года);
• ГОСТ 34.13. Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров (действующая на сегодня редакция 2015 года).

С ГОСТ 34.11—2012 мы уже познакомились в прошлой статье цикла. Это, если помнишь, был алгоритм вычисления хеш-суммы под названием «Стрибог». Сегодня мы продолжим рассматривать отечественную криптографию, и на очереди у нас алгоритм блочного шифрования под названием «Кузнечик», который описан в ГОСТ 34.12—2015.

Как и положено, данный ГОСТ разработан в научных недрах российских спецслужб и близко к ним стоящих организаций, а если говорить конкретнее, то это Центр защиты информации и специальной связи ФСБ России и открытое акционерное общество «Информационные технологии и коммуникационные системы». Документ вступил в силу с 1 января 2016 года, и все средства шифрования, официально используемые в различных структурах, работающих с информацией ограниченного доступа (гостайна, служебная тайна и прочее), должны ему соответствовать.

В стандарте описываются две разновидности блочного шифра: «Кузнечик» с длиной блока 128 бит и «Магма» с длиной блока 64 бита.

Алгоритм «Кузнечик» более современный и теоретически более стойкий, чем алгоритм «Магма» (который, по сути, практически без изменений был взят из старого ГОСТ 28147—89), и поэтому сегодня мы рассмотрим именно его. Что касается «Магмы», то о нем — как-нибудь в другой раз в следующей статье цикла.

Как уже было сказано, длина шифруемого блока в алгоритме «Кузнечик» — 128 бит. Длина ключа шифрования — 256 бит.

WARNING

При чтении ГОСТа учти, что во всех 16-байтовых массивах тестовых последовательностей нулевой байт находится в конце массива, а пятнадцатый, соответственно, в начале (если ты внимательно читал статью про «Стрибог», то эта особенность наших криптостандартов тебе должна быть знакома).

Одна из главных легенд российской криптографии гласит, что название алгоритма «Кузнечик» никакого отношения к зеленому насекомому не имеет, а представляет собой сокращение от фамилий создателей алгоритма — Кузнецова и Нечаева. Скорее всего, это действительно так, хотя нигде официального подтверждения этому я найти не смог.

Немного теории

Основу алгоритма составляет не сеть Фейстеля, как в большинстве блочных шифров, а так называемая SP — Substitution-Permutation network, или, по-русски, подстановочно-перестановочная сеть. Шифр на основе SP-сети получает на вход блок и ключ и совершает несколько чередующихся раундов, состоящих из стадий подстановки и стадий перестановки. В «Кузнечике» каждый раунд включает в себя линейное и нелинейное преобразование плюс операцию наложения так называемого итерационного ключа. Всего таких раундов девять и один последний неполный раунд, в котором выполняется только наложение последнего (десятого) итерационного ключа.

Схема работы алгоритма при зашифровании и при расшифровании

Итерационные (или раундовые) ключи получаются путем определенных преобразований на основе мастер-ключа, длина которого, как мы уже знаем, составляет 256 бит. Этот процесс начинается с разбиения мастер-ключа пополам, так получается первая пара раундовых ключей. Для генерации каждой последующей пары раундовых ключей применяется восемь итераций сети Фейстеля, в каждой итерации используется константа, которая вычисляется путем применения линейного преобразования алгоритма к значению номера итерации.

Схема получения итерационных (раундовых) ключей

Итак, после краткого и небольшого погружения в теорию начинаем кодить.

Базовые функции стандарта

Поскольку в алгоритме используются 128-битные блоки (в виде так называемых двоичных векторов), для начала определим этот самый блок:

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

Это преобразование в нашем случае повторяет S-преобразование из алгоритма «Стрибог» ГОСТ 34.11—2012. Массив S-преобразований тоже аналогичен ГОСТ 34.11—2012:

Здесь для экономии места показаны не все значения, определенные в стандарте, а только три первых и два последних. Когда будешь писать код, не забудь про остальные значения и про то, что в стандарте они записаны в десятичном виде.

Код самой функции преобразования S получается такой:

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

Отличие только в массиве преобразования, обратном к массиву прямого преобразования (в стандарте этот массив не приводится, поэтому напишем здесь его полностью):

Для выполнения данного преобразования необходима функция умножения чисел в конечном поле (или поле Галуа) над неприводимым полиномом x^8 + x^7 + x^6 + x + 1 . Это самое сложное место для понимания в данном стандарте (даже Википедия не очень помогает). Реализуется это следующим образом:

В целом, если внимательно посмотреть на код, можно увидеть, что это по большому счету умножение в столбик с добавлением числа 0xс3, которое и представляет нужный нам полином.

Далее, используя приведенную выше функцию, реализуем преобразование R, которое является частью линейного преобразования L. Преобразование R выполняется с использованием линейного регистра сдвига с обратной связью. Каждый байт из блока умножается с помощью функции GOST_Kuz_GF_Mul на один из коэффициентов из ряда (148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148, 1) в зависимости от порядкового номера байта. Байты складываются между собой по модулю 2, и все 16 байт блока сдвигаются в сторону младшего разряда, а полученное число записывается на место считанного байта.

Схема преобразования R

Для реализации R-преобразования сначала определим массив нужных нам коэффициентов:

Далее пишем саму функцию R-преобразования:

Линейное преобразование L образуется сдвигом регистра 16 раз, или шестнадцатикратным повторением функции GOST_Kuz_R :

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

Это запишется следующим образом:

Как ты наверняка догадался, функция GOST_Kuz_reverse_R — это не что иное, как обратное преобразование R. Выглядит это таким образом:

Развертывание ключей

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

Для начала определим место для хранения этих итерационных констант:

Далее вычислим их:

Конечно, все это можно (и нужно, если ты хочешь, чтобы все работало немного быстрее) вычислить заранее и определить в тексте программы в виде констант. Мы же, чтобы соблюсти наглядность, пишем так, как показано в первоисточнике.

Далее определим функцию F, которая будет представлять одну итерацию развертывания ключа:

На вход функции подаем очередную пару ключей, очередную итерационную константу, на выходе получаем промежуточную пару итерационных ключей.

Для того чтобы получить нужные нам десять итерационных (раундовых) ключей, нужно прокрутить функцию GOST_Kuz_F 32 раза. Но для начала определим место, где будут храниться полученные значения ключей:

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

Результат работы GOST_Kuz_Expand_Key с мастер-ключом из примеров, приведенных в стандарте

Зашифровываем

Как мы уже говорили, шифрование производится путем девяти итераций, включающих в себя преобразование X (сложение по модулю 2 исходного сообщения с очередным итерационным ключом), преобразование S и преобразование L, а также неполной десятой итерации, состоящей из преобразования X (сложение по модулю 2 с последним итерационным ключом):

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

Расшифровываем

Расшифрование производится в обратном порядке и с использованием обратных преобразований:

Здесь также не стоит забывать про GOST_Kuz_Expand_Key , так как для расшифрования используются те же итерационные ключи, что и для зашифрования.

Расшифрованные и зашифрованные строки из примеров, приведенных в стандарте

Заключение

Зашифровали блок, а что дальше? Если у нас сообщение больше, чем размер одного блока (128 бит)? О том, что делать дальше с зашифрованными блоками и как зашифровать какой-нибудь большой файл, говорится в другом стандарте — ГОСТ 34.13—2015. Данный ГОСТ предусматривает несколько режимов:

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

Все это дело мы разберем позже, а если нужно срочно, то качай ГОСТ, изучай, разбирайся. Самое сложное (как зашифровать один 128-битный блок) мы уже выяснили. Дальше, как говорится, дело техники.

Код, используемый в статье, можно скачать здесь. Сам текст ГОСТ 34.12—2015 можно посмотреть здесь.