Доброго времени суток.
В качестве первой статьи решил выбрать разбор реализации отечественного шифра «кузнечик». Постараюсь объяснить сложные вещи простым языком.
В качестве рабочего примера моя реализация на C.
Используемые определения:
Блок — последовательность из 16ти байтов.
Мастерключ — основной ключ для расшифрования(длина 32байта). Из него мы получаем раундовые ключ. Сам ключ в преобразованиях не используется.
Раундовый ключ — ключ, получаемый из мастер ключа, используемый непосредственно внутри преобразований
Преобразование(прямое) — манипуляция с данными(блоком). Условно: изменение данных и/или их формы представления из состояния А в состояние Б.
Обратное преобразование — манипуляция с данными(блоком). Условно: изменение данных и/или их формы представления из состояния Б в состояние А. Обратное прямому преобразованию.
Симметричное шифрование — грубо говоря, это метод шифрования, при котором для шифрования и расшифрования используется один и тот же секретный ключ.
Блочный шифр — это криптографический алгоритм симметричного шифрования, преобразующий блок открытого текста фиксированной длины в блок зашифрованного текста той же длины.
Режим шифрования — способ применения блочного шифра.
Обзор используемых преобразований
Нелинейное преобразование (S преобразование)
Самое просто с точки зрения математики.
По сути это просто замена байтов в блоке в соответствии с заданной таблицей. Берём байт, смотрим в таблице на какой его заменить, заменяем.
void S(uint8_t *blck) {
for (int i = 0; i < BLOCK_SIZE; i++) {
blck[i] = Pi[blck[i]];
}
}
Обратное S преобразование реализовано идентично, единственная разница - инвертированная таблица Pi:
void reverse_S(uint8_t *blck) {
for (int i = 0; i < BLOCK_SIZE; i++) {
blck[i] = reverse_Pi[blck[i]];
}
}
Вот и всё. Идём дальше.
Умножение многочленов в поле Галуа по модулю неприводимого многочлена.
Это операция является основой линейного преобразования в данном алгоритме.
GF(2) - поле Галуа порядка 2.
Что же это значит?
Вводить понятие поля мы не будем, скажу просто. У нас есть всего два элемента: 0 и 1. И у нас определены две операции: сложение, умножение.
Пример прилагаю:
a | b | a + b | a × b |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
В нашем же случае у нас GF(2^8). Это поле из 256 элементов. Это полиномы степени до 7 включительно, у которых коэффициенты — 0 или 1.
Выглядит это следующим образом:
a₇x⁷ + a₆x⁶ + a₅x⁵ + a₄x⁴ + a₃x³ + a₂x² + a₁x¹ + a₀
Где каждый aᵢ ∈ {0, 1}
Как вы уже поняли в памяти это будет выглядеть как один байт.
Например:
Элемент: 0xD4 = 11010100
Полином: x⁷ + x⁶ + x⁴ + x²
Умножение полиномов над полем Галуа
Давайте для начала посмотрим как умножаются два полинома друг на друга над этим полем:
Пусть первый полином будет таким:
А второй таким:
Умножение работает как в школе: каждый элемент первого на каждый элемент второго, только вместо обычного сложения получается xor:
Складываем результаты:
У нас сократилось два и единички. Выглядит достаточно доступно и понятно.
Теперь разберём концепцию модуля по неприводимому многочлену, которая полностью завершит используемую операцию.
Неприводимый многочлен можно объяснить двумя способами.
Первый способ:
Неприводимый многочлен - это это аналог простого числа, только в мире многочленов, т.е его нельзя разложить на произведение двух многочленов меньшей степени.
Второй способ(он мне нравится больше 😊):
Если приравнять неприводимый многочлен к нулю, то мы не сможем найти решение такого уравнения в данном поле(нет корней).
В рассматриваемом госте используется следующий неприводимый многочлен:
x^8 + x^7 + x^6 + x^1 + 1
Если вы его приравняете к нулю, то ни ни
не будут являться корнем уравнения.
Давайте возьмём наш вышеполученный результат умножения двух полиномов по модулю этого многочлена:
Во первых стоит сказать, что взять по модулю это найти остаток от деления одного на другое.
Мы делим на
, то есть
, где:
Цель — найти остаток от деления на
На самом деле, это намного нагляднее если делить один многочлен на другой на бумаге столбиком, поэтому прикреплю скриншот деления:

Мы получили остаток равный - это и есть наш ответ.
Фууууух.
Сейчас посмотрим как это сделано в коде, а дальше будет уже намного проооооще - всё свернётся в матрёшку🪆.
static uint8_t GF_mul(uint8_t a, uint8_t b) {
uint8_t c = 0, hi_bit;
for (int i = 0; i < 8; i++) {
if (b & 1) c ^= a;
hi_bit = a & 0x80;
a <<= 1;
if (hi_bit) a ^= 0xC3;
b >>= 1;
}
return c;
}
аргументы функции - байты, те же самые многочлены
c - результат умножения
hi_bit — переменная, чтобы отследить, вылез ли старший бит (x^7), при сдвиге a.
Цикл проходит по каждому биту. Это обеспечивается тем что осуществляется сдвиг битов вправо(b >>= 1
) и при новой итерации мы уже смотрим не нулевой бит, а как бы первый, второй и т.д.
Проверяем младший бит у байта b, если он равен 1, то делаем xor(c, a)
.
Если бы он был равен нулю, то нет смысла делать ксор так xor с нулём не изменяет значение. Иными словами, если в числе b бит равен 0, то его вклад в итоговое умножение равен нулю, и нет смысла прибавлять (XORить) a к результату. Это не повлияет на итоговое значение.
Далее проверяем установлен ли старший бит в a.
hi_bit = a & 0x80;
0x80 — это маска для старшего бита байта, то есть, бит на позиции x^7.
Далее сдвигаем a на 1 бит влево: — умножаем на x, что эквивалентно увеличению степени полинома на 1. Это делается на каждом шаге цикла, чтобы обработать каждую степень x из множителя b.
Если старший бит равен 1, это значит, что после сдвига на один разряд влево мы выйдем за пределы x^7 и получим x^8, то есть надо будет взять модуль:
if (hi_bit) a ^= 0xC3;
Если старший бит был равен 1 (то есть, старший бит перед сдвигом был установлен), мы делаем XOR с неприводимым многочленом 0xC3, чтобы вернуть результат обратно в поле Галуа GF(2^8).
(Многочлен 0xC3 в двоичной форме — это 11000011, что соответствует
)
Это на самом деле не самый простой алгоритм, но какой есть. Он достаточно эффективен, и тем кому интересно как выполнять умножение многочленов кодом по модулю - советую вдуматься.
Я вас поздравляю. Самое сложное позади - дальше сплошное наслаивание и удовольствие ))
Преобразование R
Данный метод выполняет циклический сдвиг вправо, далее выполняется поэлементное перемножение с вектором l_vec, результат каждого умножения накапливается в переменной tmp с помощью xor. Далее нулевой блок заменяется на переменную tmp.
void R(uint8_t *block) {
cyclic_shift_right(block);
uint8_t tmp = 0; // zero or the 16th element???
for (int i = 0; i < 16; i++) {
tmp ^= GF_mul(block[i], l_vec[15 - i]); // mul + xor
}
block[0] = tmp;
}
void cyclic_shift_right(uint8_t *block) {
const uint8_t last = block[BLOCK_SIZE - 1];
for (int i = BLOCK_SIZE - 1; i > 0; i--) {
block[i] = block[i - 1];
}
block[0] = last;
}
void cyclic_shift_left(uint8_t *block) {
const uint8_t first = block[0];
for (int i = 0; i < BLOCK_SIZE - 1; i++) {
block[i] = block[i + 1];
}
block[BLOCK_SIZE - 1] = first;
}
const uint8_t l_vec[16] = {
0x94, 0x20, 0x85, 0x10, 0xC2, 0xC0, 0x01, 0xFB,
0x01, 0xC0, 0xC2, 0x10, 0x85, 0x20, 0x94, 0x01
};

Тут же отметим обратное преобразование R. Изменяется только порядок манипуляций с точностью до наоборот (именно коммутативность операции GF позволяет нам так сделать):
void reverse_R(uint8_t *block) {
uint8_t tmp = 0;
for (int i = 0; i < 16; i++) {
tmp ^= GF_mul(block[i], l_vec[15 - i]); // mul + xor
}
block[0] = tmp;
cyclic_shift_left(block);
}
Тут же стоит рассказать про метод L, который 16 раз вызывает преобразование R, чтобы каждый байт прошёл через линейное пребразование.
void L(uint8_t *block) {
for (int i = 0; i < 16; i++) {
R(block);
}
}
Далее разберём последнее преобразование F.
Она принимает на вход два блока. Ксорит их и выполняет два преобразования: S и L, которые мы с вами уже рассматривали.
uint8_t* F(uint8_t *k1, uint8_t *c) {
uint8_t *tmp = xor_blocks(k1, c);
S(tmp);
L(tmp);
return tmp;
}
Эта функция используется при генерации раундовых ключей.
ГЕНЕРАЦИЯ РАУНДОВЫХ КЛЮЧЕЙ
Для генерации раундовых ключей нам понадобятся константы. Они всегда одинаковые и не зависят от входных данных, но согласно ГОСТ они формируются в процессе выполнения алгоритма, так что приступим:
void gen_constants(uint8_t *constants[32]) {
for (int i = 0; i < 32; i++) {
constants[i] = malloc(BLOCK_SIZE); // allocate memory
memset(constants[i], 0, BLOCK_SIZE); // zero
constants[i][15] = i + 1;
L(constants[i]);
}
}
У нас всего 32 константы
Для каждой мы создаём заготовку вида:
0x00, 0x00, 0x00 ... 0x00
0x00, 0x00, 0x00 ... 0x01
0x00, 0x00, 0x00 ... 0x02
....
0x00, 0x00, 0x00 ... 0x20
Каждую из этих заготовок мы отправляем в метод L
Приступаем к генерации ключей, скоро картинка сложится.
// key generation
void gen_keys(uint8_t *keys[10], uint8_t *masterkey) {
uint8_t *constants[32]; // array for keys_constants
gen_constants(constants);
uint8_t *k1 = malloc(16);
uint8_t *k2 = malloc(16);
// memory copy for masterKey immutability
memcpy(k1, masterkey, 16);
memcpy(k2, masterkey + 16, 16);
keys[0] = malloc(BLOCK_SIZE);
keys[1] = malloc(BLOCK_SIZE);
memcpy(keys[0], k1, BLOCK_SIZE);
memcpy(keys[1], k2, BLOCK_SIZE);
for (int i = 0; i < 32; i++) {
uint8_t *tmp = F(k1, constants[i]);
tmp = xor_blocks(tmp, k2);
k2 = k1;
k1 = tmp;
if ((i + 1) % 8 == 0) {
int a = (i + 1) / 4;
//write a value with memcpy, cos k1 k2 still needed
keys[a] = malloc(BLOCK_SIZE);
memcpy(keys[a], k1, BLOCK_SIZE);
keys[a + 1] = malloc(BLOCK_SIZE);
memcpy(keys[a + 1], k2, BLOCK_SIZE);
}
}
for (int i = 0; i < 32; i++) {
free(constants[i]);
}
}
В процессе генерации раундовых ключей мы
Генерируем константы
Первые два ключа мы получаем, поделив мастерключ на 2 части
Далее начинается сеть фейстеля, она изображена на схеме ниже.
Каждые 8 преобразований мы снимаем по 2 ключа.

Шифрование блока
Для шифрования мы используем 10 раундов через три преобразования:
Ксор с ключом
Нелинейное преобразование
Линейное преобразование НО! в последнем раунде мы используем только XOR - Это важно
void encrypt_block(uint8_t *text_bytes, uint8_t *keys[10]) {
for (int i = 0; i < 9; i++) {
xor_blocks_void(text_bytes, keys[i]);
S(text_bytes);
L(text_bytes);
}
xor_blocks_void(text_bytes, keys[9]);
}
В случае дешифрования мы используем обратные преобразования и изменённый порядок вызовов этих преобразований.
void decrypt_block(uint8_t *text_bytes, uint8_t *keys[10]) {
xor_blocks_void(text_bytes, keys[9]);
for (int i = 8; i >= 0; i--) {
reverse_L(text_bytes);
reverse_S(text_bytes);
xor_blocks_void(text_bytes, keys[i]);
}
}
На самом деле на это моменте можно уже заканчивать мою статейку, так как мы уже покрыли всё что касается ГОСТа. Мы уже можем шифровать и расшифровывать блоки, но в таком варианте реализация абсолютно не прикладная.
Поэтому я прикрутил несколько дополнительных функций:
Шифрование файла
Автодополнение блока, если нам не хватает байтов до целого блока в файле
Режим шифрования CBC
Начнём со второго пункта:
Как правило, у вас размер файла не будет кратен 16ти байтам, поэтому нам необходимо прикрутить механизм который позволит нам без проблем добивать до целого блока, расшифровывать даже если дополнения не произошло, ну и конечно же чтобы криптостойкость алгоритма никак не изменилась).
Эту проблему я решил следующим способом:
Я считываю размер файла, проверяю кратность и устанавливаю флаг надо ли как именно нужно будет модифицировать последний шифруемый блок. Дак вот, если у нам не хватает до целого блока мы добиваем его с помощью 0xFF:
if (bytes_read < BLOCK_SIZE) {
padding_bytes = BLOCK_SIZE - bytes_read;
memset(buffer + bytes_read, 0xFF, BLOCK_SIZE - bytes_read);
}
И запоминаем сколько мы добавили.
После того как мы всё зашифровали мы дописываем модификационные(вспомогательные байты). Если мы не добавляли никаких новых байтов, то записываем два пустых блока, содержащих 0xFF, иначе дописываем один блок и в его нулевом байте указывает сколько байтов мы добавили.
const int is_whole_blocks = (file_size % BLOCK_SIZE == 0);
if (is_whole_blocks) {
// if an input file has integer number of block add two empty blocks
memset(buffer, 0xFF, BLOCK_SIZE);
fwrite(buffer, 1, BLOCK_SIZE, output_file);
memset(buffer, 0xFF, BLOCK_SIZE);
fwrite(buffer, 1, BLOCK_SIZE, output_file);
} else {
// if an input file has not integer number of block, add block with number of added 0xFF
memset(buffer, 0xFF, BLOCK_SIZE);
buffer[0] = (uint8_t)padding_bytes;
fwrite(buffer, 1, BLOCK_SIZE, output_file);
}
Как это влияет на функцию расшифрования файла: перед расшифровкой мы проверяем последний байт. Если он полный 0xFF, то мы просто расшифровываем, не читая последние два байта, иначе считываем сколько мы добавили байтов:
int zeros;
for (int i = 0; i < BLOCK_SIZE; i++) {
if (buffer[i] != 0xFF) {
is_buffer_zero = false;
zeros = buffer[0];
break;
}
}
Далее, что касается режима шифрования. Шифровать в режим ECB (электронно кодовой книги), то есть без взаимодействия блоков между собой — не очень секьюрно, так как одна входная последовательность после шифрования всегда будет одной и той же. Приведу самый популярный пример с картинкой, её вы можете найти в википедии:

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

Мы производим ксор с так называемой gamma, затем gamma обновляется в соответствии со схемой.
В качестве Вектора инициализации(исходная gamma) я взял первый раундовый ключ.
uint8_t* gamma = malloc(BLOCK_SIZE);
memcpy(gamma, keys[1], BLOCK_SIZE);
Вот как это происходит xor в процессе шифрования:
while ((bytes_read = fread(buffer, 1, BLOCK_SIZE, input_file)) > 0) {
if (bytes_read < BLOCK_SIZE) {
padding_bytes = BLOCK_SIZE - bytes_read;
memset(buffer + bytes_read, 0xFF, BLOCK_SIZE - bytes_read);
}
xor_blocks_void(buffer, gamma); // CBC: xor with gamma
encrypt_block(buffer, keys);
memcpy(gamma, buffer, BLOCK_SIZE); // CBC: refresh gamma
fwrite(buffer, 1, BLOCK_SIZE, output_file);
}
Благодаря этому мы получили более безопасный режим использования данного шифра, так как входной блок будет изменяться на основе предыдущего зашифрованного блока.
Можно было бы дальше продолжить исследование данного алгоритма, но пора закругляться, в любом случае полный код реализации вы можете посмотреть на моё github.
Эта моя первая статья, буду признателен комментариям, критике, указанием ошибок и фаворитам на github.
Всем прогресса[project](
https://github.com/awsCartman/kuznec)
---
Используемые таблицы замен:
const uint8_t Pi[256] = {
0xFC, 0xEE, 0xDD, 0x11, 0xCF, 0x6E, 0x31, 0x16, 0xFB, 0xC4, 0xFA, 0xDA, 0x23, 0xC5, 0x04, 0x4D,
0xE9, 0x77, 0xF0, 0xDB, 0x93, 0x2E, 0x99, 0xBA, 0x17, 0x36, 0xF1, 0xBB, 0x14, 0xCD, 0x5F, 0xC1,
0xF9, 0x18, 0x65, 0x5A, 0xE2, 0x5C, 0xEF, 0x21, 0x81, 0x1C, 0x3C, 0x42, 0x8B, 0x01, 0x8E, 0x4F,
0x05, 0x84, 0x02, 0xAE, 0xE3, 0x6A, 0x8F, 0xA0, 0x06, 0x0B, 0xED, 0x98, 0x7F, 0xD4, 0xD3, 0x1F,
0xEB, 0x34, 0x2C, 0x51, 0xEA, 0xC8, 0x48, 0xAB, 0xF2, 0x2A, 0x68, 0xA2, 0xFD, 0x3A, 0xCE, 0xCC,
0xB5, 0x70, 0x0E, 0x56, 0x08, 0x0C, 0x76, 0x12, 0xBF, 0x72, 0x13, 0x47, 0x9C, 0xB7, 0x5D, 0x87,
0x15, 0xA1, 0x96, 0x29, 0x10, 0x7B, 0x9A, 0xC7, 0xF3, 0x91, 0x78, 0x6F, 0x9D, 0x9E, 0xB2, 0xB1,
0x32, 0x75, 0x19, 0x3D, 0xFF, 0x35, 0x8A, 0x7E, 0x6D, 0x54, 0xC6, 0x80, 0xC3, 0xBD, 0x0D, 0x57,
0xDF, 0xF5, 0x24, 0xA9, 0x3E, 0xA8, 0x43, 0xC9, 0xD7, 0x79, 0xD6, 0xF6, 0x7C, 0x22, 0xB9, 0x03,
0xE0, 0x0F, 0xEC, 0xDE, 0x7A, 0x94, 0xB0, 0xBC, 0xDC, 0xE8, 0x28, 0x50, 0x4E, 0x33, 0x0A, 0x4A,
0xA7, 0x97, 0x60, 0x73, 0x1E, 0x00, 0x62, 0x44, 0x1A, 0xB8, 0x38, 0x82, 0x64, 0x9F, 0x26, 0x41,
0xAD, 0x45, 0x46, 0x92, 0x27, 0x5E, 0x55, 0x2F, 0x8C, 0xA3, 0xA5, 0x7D, 0x69, 0xD5, 0x95, 0x3B,
0x07, 0x58, 0xB3, 0x40, 0x86, 0xAC, 0x1D, 0xF7, 0x30, 0x37, 0x6B, 0xE4, 0x88, 0xD9, 0xE7, 0x89,
0xE1, 0x1B, 0x83, 0x49, 0x4C, 0x3F, 0xF8, 0xFE, 0x8D, 0x53, 0xAA, 0x90, 0xCA, 0xD8, 0x85, 0x61,
0x20, 0x71, 0x67, 0xA4, 0x2D, 0x2B, 0x09, 0x5B, 0xCB, 0x9B, 0x25, 0xD0, 0xBE, 0xE5, 0x6C, 0x52,
0x59, 0xA6, 0x74, 0xD2, 0xE6, 0xF4, 0xB4, 0xC0, 0xD1, 0x66, 0xAF, 0xC2, 0x39, 0x4B, 0x63, 0xB6
};
const uint8_t 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,
};