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

Четыре слона отечественной криптографии

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

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

INFO

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

 

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

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

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

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

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

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

 

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

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

#define BLOCK_SIZE 16 // Размер блока 16 байт (или 128 бит)
...
typedef uint8_t vect[BLOCK_SIZE]; // Определяем тип vect как 16-байтовый массив
 

Сложение двух двоичных векторов по модулю 2

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

static void GOST_Kuz_X(const uint8_t *a, const uint8_t *b, uint8_t *c)
{
    int i;
    for (i = 0; i < BLOCK_SIZE; i++)
        c[i] = a[i] ^ b[i];
}
 

Нелинейное биективное преобразование (преобразование S)

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

static const unsigned char Pi[256] = {
    0xFC, 0xEE, 0xDD, ... 0x63, 0xB6
};

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

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

static void GOST_Kuz_S(const uint8_t *in_data, uint8_t *out_data)
{
    int i;
    for (i = 0; i < BLOCK_SIZE; i++)
        out_data[i] = Pi[in_data[i]];
}
Преобразование S
Преобразование S
 

Обратное нелинейное биективное преобразование (обратное преобразование S)

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

static void GOST_Kuz_reverse_S(const uint8_t *in_data, uint8_t *out_data)
{
    int i;
    for (i = 0; i < BLOCK_SIZE; i++)
           out_data[i] = reverse_Pi[in_data[i]];
}

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

static const unsigned char reverse_Pi[256] = {
    0xA5, 0x2D, 0x32, 0x8F, 0x0E, 0x30, 0x38, 0xC0,
    0x54, 0xE6, 0x9E, 0x39, 0x55, 0x7E, 0x52, 0x91,
    0x64, 0x03, 0x57, 0x5A, 0x1C, 0x60, 0x07, 0x18,
    0x21, 0x72, 0xA8, 0xD1, 0x29, 0xC6, 0xA4, 0x3F,
    0xE0, 0x27, 0x8D, 0x0C, 0x82, 0xEA, 0xAE, 0xB4,
    0x9A, 0x63, 0x49, 0xE5, 0x42, 0xE4, 0x15, 0xB7,
    0xC8, 0x06, 0x70, 0x9D, 0x41, 0x75, 0x19, 0xC9,
    0xAA, 0xFC, 0x4D, 0xBF, 0x2A, 0x73, 0x84, 0xD5,
    0xC3, 0xAF, 0x2B, 0x86, 0xA7, 0xB1, 0xB2, 0x5B,
    0x46, 0xD3, 0x9F, 0xFD, 0xD4, 0x0F, 0x9C, 0x2F,
    0x9B, 0x43, 0xEF, 0xD9, 0x79, 0xB6, 0x53, 0x7F,
    0xC1, 0xF0, 0x23, 0xE7, 0x25, 0x5E, 0xB5, 0x1E,
    0xA2, 0xDF, 0xA6, 0xFE, 0xAC, 0x22, 0xF9, 0xE2,
    0x4A, 0xBC, 0x35, 0xCA, 0xEE, 0x78, 0x05, 0x6B,
    0x51, 0xE1, 0x59, 0xA3, 0xF2, 0x71, 0x56, 0x11,
    0x6A, 0x89, 0x94, 0x65, 0x8C, 0xBB, 0x77, 0x3C,
    0x7B, 0x28, 0xAB, 0xD2, 0x31, 0xDE, 0xC4, 0x5F,
    0xCC, 0xCF, 0x76, 0x2C, 0xB8, 0xD8, 0x2E, 0x36,
    0xDB, 0x69, 0xB3, 0x14, 0x95, 0xBE, 0x62, 0xA1,
    0x3B, 0x16, 0x66, 0xE9, 0x5C, 0x6C, 0x6D, 0xAD,
    0x37, 0x61, 0x4B, 0xB9, 0xE3, 0xBA, 0xF1, 0xA0,
    0x85, 0x83, 0xDA, 0x47, 0xC5, 0xB0, 0x33, 0xFA,
    0x96, 0x6F, 0x6E, 0xC2, 0xF6, 0x50, 0xFF, 0x5D,
    0xA9, 0x8E, 0x17, 0x1B, 0x97, 0x7D, 0xEC, 0x58,
    0xF7, 0x1F, 0xFB, 0x7C, 0x09, 0x0D, 0x7A, 0x67,
    0x45, 0x87, 0xDC, 0xE8, 0x4F, 0x1D, 0x4E, 0x04,
    0xEB, 0xF8, 0xF3, 0x3E, 0x3D, 0xBD, 0x8A, 0x88,
    0xDD, 0xCD, 0x0B, 0x13, 0x98, 0x02, 0x93, 0x80,
    0x90, 0xD0, 0x24, 0x34, 0xCB, 0xED, 0xF4, 0xCE,
    0x99, 0x10, 0x44, 0x40, 0x92, 0x3A, 0x01, 0x26,
    0x12, 0x1A, 0x48, 0x68, 0xF5, 0x81, 0x8B, 0xC7,
    0xD6, 0x20, 0x0A, 0x08, 0x00, 0x4C, 0xD7, 0x74
};
 

Линейное преобразование (преобразование L)

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

static uint8_t GOST_Kuz_GF_mul(uint8_t a, uint8_t b)
{
    uint8_t c = 0;
    uint8_t hi_bit;
    int i;
    for (i = 0; i < 8; i++)
    {
        if (b & 1)
            c ^= a;
        hi_bit = a & 0x80;
        a <<= 1;
        if (hi_bit)
            a ^= 0xc3; // Полином x^8 + x^7 + x^6 + x + 1
        b >>= 1;
    }
    return c;
}

В целом, если внимательно посмотреть на код, можно увидеть, что это по большому счету умножение в столбик с добавлением числа 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-преобразования сначала определим массив нужных нам коэффициентов:

static const unsigned char l_vec[16] = {
    1, 148, 32, 133, 16, 194, 192, 1,
    251, 1, 192, 194, 16, 133, 32, 148
};

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

static void GOST_Kuz_R(uint8_t *state)
{
    int i;
    uint8_t a_15 = 0;
    vect internal;
    for (i = 15; i >= 0; i--)
    {
        internal[i - 1] = state[i];// Двигаем байты в сторону младшего разряда
        a_15 ^= GOST_Kuz_GF_mul(state[i], l_vec[i]);
    }
    // Пишем в последний байт результат сложения
    internal[15] = a_15;
    memcpy(state, internal, BLOCK_SIZE);
}

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

static void GOST_Kuz_L(const uint8_t *in_data, uint8_t *out_data)
{
    int i;
    vect internal;
    memcpy(internal, in_data, BLOCK_SIZE);
    for (i = 0; i < 16; i++)
        GOST_Kuz_R(internal);
    memcpy(out_data, internal, BLOCK_SIZE);
}
 

Обратное линейное преобразование (обратное преобразование L)

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

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

static void GOST_Kuz_reverse_L(const uint8_t *in_data, uint8_t *out_data)
{
    int i;
    vect internal;
    memcpy(internal, in_data, BLOCK_SIZE);
    for (i = 0; i < 16; i++)
        GOST_Kuz_reverse_R(internal);
    memcpy(out_data, internal, BLOCK_SIZE);
}

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

static void GOST_Kuz_reverse_R(uint8_t *state)
{
    int i;
    uint8_t a_0;
    a_0 = state[15];
    vect internal;
    for (i = 0; i < 16; i++)
    {
        internal[i] = state[i - 1];// Двигаем все на старые места
        a_0 ^= GOST_Kuz_GF_mul(internal[i], l_vec[i]);
    }
    internal[0] = a_0;
    memcpy(state, internal, BLOCK_SIZE);
}

Продолжение статьи доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все статьи на сайте

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

Вариант 2. Купи одну статью

Заинтересовала статья, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для статей, опубликованных более двух месяцев назад.


6 комментариев

Подпишитесь на ][, чтобы участвовать в обсуждении

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

Check Also

Как работает Linux: от нажатия кнопки включения до рабочего стола

Лучший способ понять, как работает операционная система, — это проследить поэтапно ее загр…