Содержание
- 1
Четыре слона отечественной криптографии
- 2
Немного теории
- 3
Базовые функции стандарта
-
- 3.0.1
Сложение двух двоичных векторов по модулю 2
- 3.0.2
Нелинейное биективное преобразование (преобразование S)
- 3.0.3
Обратное нелинейное биективное преобразование (обратное преобразование S)
- 3.0.4
Линейное преобразование (преобразование L)
- 3.0.5
Обратное линейное преобразование (обратное преобразование L)
- 3.0.6 Источник
- 3.0.1
-
Четыре слона отечественной криптографии
В настоящее время отечественная криптография базируется на нескольких основных государственных стандартах:
- ГОСТ 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 бит.
Немного теории
Основу алгоритма составляет не сеть Фейстеля, как в большинстве блочных шифров, а так называемая SP — Substitution-Permutation network, или, по-русски, подстановочно-перестановочная сеть. Шифр на основе SP-сети получает на вход блок и ключ и совершает несколько чередующихся раундов, состоящих из стадий подстановки и стадий перестановки. В «Кузнечике» каждый раунд включает в себя линейное и нелинейное преобразование плюс операцию наложения так называемого итерационного ключа. Всего таких раундов девять и один последний неполный раунд, в котором выполняется только наложение последнего (десятого) итерационного ключа.
Итерационные (или раундовые) ключи получаются путем определенных преобразований на основе мастер-ключа, длина которого, как мы уже знаем, составляет 256 бит. Этот процесс начинается с разбиения мастер-ключа пополам, так получается первая пара раундовых ключей. Для генерации каждой последующей пары раундовых ключей применяется восемь итераций сети Фейстеля, в каждой итерации используется константа, которая вычисляется путем применения линейного преобразования алгоритма к значению номера итерации.
Итак, после краткого и небольшого погружения в теорию начинаем кодить…
Базовые функции стандарта
Поскольку в алгоритме используются 128-битные блоки (в виде так называемых двоичных векторов), для начала определим этот самый блок:
Сложение двух двоичных векторов по модулю 2
Данная функция в стандарте определена как X-преобразование. Каждый байт первого вектора ксорится с соответствующим байтом второго вектора, и результат пишется в третий (выходной) вектор:
Нелинейное биективное преобразование (преобразование S)
Это преобразование в нашем случае повторяет S-преобразование из алгоритма «Стрибог» ГОСТ 34.11–2012. Массив S-преобразований тоже аналогичен ГОСТ 34.11–2012:
Здесь для экономии места показаны не все значения, определенные в стандарте, а только три первых и два последних. Когда будешь писать код, не забудь про остальные значения и про то, что в стандарте они записаны в десятичном виде.
Код самой функции преобразования S получается такой:
Обратное нелинейное биективное преобразование (обратное преобразование S)
Поскольку нам нужно не только зашифровывать сообщения, но и расшифровывать тоже, то каждому преобразованию зашифрования необходимо ставить в соответствие обратное преобразование для расшифрования. Сама функция обратного S-преобразования выглядит практически так же, как и прямое S-преобразование:
Отличие только в массиве преобразования, обратном к массиву прямого преобразования (в стандарте этот массив не приводится, поэтому напишем здесь его полностью):
Линейное преобразование (преобразование L)
Для выполнения данного преобразования необходима функция умножения чисел в конечном поле (или поле Галуа) над неприводимым полиномом 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-преобразования:
Линейное преобразование L образуется сдвигом регистра 16 раз, или шестнадцатикратным повторением функции GOST_Kuz_R
:
Обратное линейное преобразование (обратное преобразование L)
Для того чтобы можно было не только зашифровывать сообщения, но и расшифровывать их, нам необходимо обратное линейное преобразование.
Это запишется следующим образом:
Как ты наверняка догадался, функция GOST_Kuz_reverse_R
— это не что иное, как обратное преобразование R. Выглядит это таким образом:
Источник