Шифр ГОСТ 34.12-2018 «Кузнечик»
Привет! Сегодня мы рассмотрим, заключительный в цикле материалов, Российский шифр «Кузнечик».
«Кузнечик» — это современный стандарт шифрования в России и за рубежом. Опубликован был в 19 июня 2015 года. В наступающем 2025 году будем отмечать его юбилей.
Изначально был опубликован как ГОСТ Р 34.12-2015
и являлся стандартом только в России, а позже, в 2018 году стал межгосударственным стандартом с идентификатором ГОСТ 34.12-2018
.
В прошлый раз мы рассматривали предшественника «Кузнечика» — «Магму». Обе реализации шифров используют небольшую самописную библиотеку, с ней вы можете ознакомиться в статье по режимам блочного шифрования.
Характеристики и подробности
SP-сеть — разновидность блочного шифра, предложенная в 1971 году Хорстом Фейстелем. В простейшем варианте представляет собой «сэндвич» из слоёв двух типов, используемых многократно по очереди.
Первый тип слоя — P-слой, состоящий из P-блока большой разрядности, за ним идёт второй тип слоя — S-слой, представляющий собой большое количество S-блоков малой разрядности, потом опять P-слой и т.д.
В настоящее время из алгоритмов на основе SP-сетей широко используется AES. Альтернативой SP-сетям являются сети Фейстеля, на основе которых реализованы, например, DES и «Магма».
В современных алгоритмах вместо S- и P-блоков используются различные математические или логические функции. Любая двоичная функция может быть сведена к S-блоку, некоторые функции — к P-блоку. Например, к P-блоку сводится циклический сдвиг, сам P-блок является частным случаем S-блока. Такие функции, как правило, легко реализуются в аппаратуре, обеспечивая при этом хорошую криптостойкость.
В «Кузнечике» используется:
-
Длина блока — 128 бит (16 байт), что вдвое больше, чем у «Магмы».
-
Длина ключа — 256 бит (32 байта).
-
Количество итераций — 10 итераций.
Алгоритм
Для того, чтобы реализовать шифр «Кузнечик» понадобится гораздо больше функций, чем для реализации «Магмы». Часть из них будет дублироваться с минимальными изменениями, поскольку понадобятся обратные преобразования. Перечислим их:
-
Преобразование X.
-
Преобразование S.
-
Обратное преобразование S.
-
Функция умножения в поле Галуа.
-
Преобразование R.
-
Обратное преобразование R.
-
Преобразование L.
-
Обратное преобразование L.
-
Преобразование F.
-
Функция формирования итерационных ключей.
-
Функция шифрования.
-
Функция расшифровывания.
Функций и преобразований много, а смысл некоторых из них довольно сложен. Будем реализовывать каждую по порядку.
Для начала зададим необходимые константы:
/// Длина блока: 128 бит const BLOCK_SIZE: usize = 16; /// Длина ключа: 256 бит const KEY_SIZE: usize = 32; /// Количество раундов шифрования: 10 const ROUNDS: usize = 10;
И структуру шифра:
/// # Шифр "Кузнечик" /// /// - Длина блока: 128 бит /// - Длина ключа: 256 бит /// - Количество раундов шифрования: 10 #[derive(Debug, Clone)] pub struct Kuznyechik { round_keys: [[u8; 16]; ROUNDS], }
В этот раз мы не будем создавать отдельного поля для различных матриц — будем использовать лишь одну.
Преобразование X
Преобразование, знакомое каждому, кто хоть немного увлекается программированием — функция XOR
.
Мы оперируем по сути 128-битными числами, но для удобства передаем и модифицируем их как массив из 16 байт.
/// # Преобразование X fn transform_x(a: &[u8; 16], b: &[u8; 16], result: &mut [u8; 16]) { for (i, e) in result.iter_mut().enumerate() { *e = a[i] ^ b[i]; } }
Здесь все довольно просто, принимаем два 128-битных числа: a
и b
, а результат их XOR
кладем в результирующее число result
.
Преобразование S
Преобразование, знакомое некоторым по Российскому алгоритму хэширования «Стрибог». Даже используемая матрица подстановок та же.
/// # Преобразование S fn transform_s(result: &mut [u8; 16]) { result.iter_mut().for_each(|byte| *byte = PI[*byte as usize]); }
Здесь все довольно просто — мы оперируем массивом байт, а самое большое число, которое мы можем закодировать одним байтом — 255
(0b11111111
).
Теперь, когда это ясно, мы можем использовать эти байты как индексы в матрице подстановок Pi
и заменять исходные байты новыми. Это нелинейное биективное преобразование.
Сама матрица подстановок выглядит так:
pub const PI: [u8; 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, ];
Обратное преобразование S
А вот что отличает «Кузнечик» от «Стрибог», так это наличие обратного преобразования S. Если хэширование — это процесс необратимый (в идеале), то вот шифрование, напротив, должно быть обратимым.
/// # Преобразование обратное преобразованию S fn transform_s_rev(result: &mut [u8; 16]) { result.iter_mut().for_each(|byte| *byte = PI_REV[*byte as usize]); }
Здесь смысл абсолютно такой же, как и в обычном преобразовании S — подстановки, но теперь мы должны использовать обратную матрицу Pi
.
Если раньше мы должны были, например, заменить 0x00
на 0xfc
, то в этом преобразовании должны, напротив, вернуть все на свои места — заменить 0xfc
на 0x00
.
Это можно сделать двумя путями — рассчитывать матрицу каждый раз самостоятельно, либо захардкодить. Я использую захардкоженный вариант.
Обратная матрица подстановок выглядит так:
pub const PI_REV: [u8; 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, ];
Функция умножения в поле Галуа
Это очень сложная для понимания функция, особенно для тех, кто не знаком с кольцами, полями и остальной теорией алгебры.
P.s. заранее прошу прощения за вид формул — Хабр не поддерживает inline-математику.
Начнем с того, что мы работает в поле Галуа (GF 2^8), образованном неприводимым многочленом указанном выше.
Обратите внимание на следующие вещи:
-
Характеристика поля — это 2, то есть 1 бит информации.
-
Степень поля — это 8, то есть количество разрядов.
Уже можно видеть связь между полем Галуа и байтом информации. Наша функция умножения в поле Галуа предназначена для умножения двух байт a
и b
.
Для упрощения понимания я обозначу еще несколько моментов:
-
Мы будем одновременно работать и с байтами, и с многочленами. Для примера:
-
Байт
0b00110011
будет отображать многочлен вида x^5 + x^4 + x + 1. -
Байт
0b11000011
будет отображать многочлен вида x^7 + x^6 + x + 1. Как можно заметить — это часть неприводимого многочлена по которому строится поле Галуа.
-
-
Операция
XOR
будет использоваться для:-
Инициализации переменной. Если мы произведем операцию
XOR
между следующими байтами:0b00000000
(0) и0b00110011
(51), то получим0b00110011
(51). То есть то же самое. -
Сложения. Удобно, что характеристика нашего поля 2. При использовании
XOR
между следующими байтами:0b00000010
(2) и0b00000010
(2) мы получим0b00000000
(0). Так как это не привычная система счисления — мы не получим ожидаемой четверки0b00000100
(4).
Не забывайте, что мы фактически работаем с многочленами. Возможно кому-то было бы проще воспринимать этот пример в таком виде: x + x. При сложении этих двух многочленов в поле Галуа с характеристикой 2 мы получим ноль.
Кстати, на забывайте, что в поле с характеристикой 2 операции сложения и вычитания — это одна и та же операция. -
Взятия остатка по модулю. Если мы достигнем значения больше, чем наш модуль, то необходимо этот самый модуль вычесть.
-
-
Сдвиги эквиваленты умножению или делению на 2. К тому же значение 2 в нашем поле имеет вид многочлена x.
Теперь можно приступить к самому алгоритму.
/// # Умножение в поле Галуа /// /// Умножение в поле Галуа, построенном над /// неприводимым полиномом /// `x^8 + x^7 + x^6 + x + 1` fn gf_multiply(mut a: u8, mut b: u8) -> u8 { let mut result: u8 = 0; let mut high_bit: u8; for _ in 0..8 { if b & 0b00000001 == 0b00000001 { result ^= a; } high_bit = a & 0b10000000; a <<= 1; if high_bit == 0b10000000 { a ^= 0b11000011; } b >>= 1; } result }
Выглядит сложно и непонятно, однако если вам в общих чертах ясны мои предыдущие объяснения, то и это вы сможете осилить.
Мы заведем две отдельные переменные:
-
Для хранения результата умножения.
-
Для хранения бита, который может возникнуть при переполнении. Мы могли бы взять тип не
u8
, аu16
, которого хватит для хранения переполнения, но это бы переусложнило код.
Итак, мы должны пройтись по всем восьми разрядам многочлена, то есть по всем восьми битам.
Если число b
имеет ненулевой младший бит, то мы произведем операцию XOR
между результирующим числом r
и числом a
. Производя это впервые, мы просто присваеваем значение числа a
результирующему числу r
. В последствии это будет просто сложение двух многочленов.
Далее мы сохраняем старший, а само число a
мы сдвигаем влево на 1 позицию. Напомню, что это умножение на x.
Далее, поскольку мы сдвинули 8-битное число, то переполнение, если бы оно было, находилось бы в девятом разряде числа. Поэтому мы сохраняем возможное переполнение до того, как сдвинем число. Если переполнение возникло, то наше число имеет вид многочлена x^8 + …, а следовательно необходимо взять остаток по модулю. Это мы делаем с помощью операции XOR
.
Остаток мы берем по части неприводимого многочлена. Для того, чтобы изобразить неприводимый многочлен целиком, необходимо 9 бит, однако в нашем случае достаточно только младшей 8-битной части, поскольку старший бит при сдвиге исчезает самостоятельно.
В конце итерации мы сдвигаем число b
вправо. Опять же, это умножение на x.
Пример на поле Галуа меньшего размера
Для примера возьмем такие параметры:
-
Поле Галуа (GF 2^2).
-
Неприводимый многочлен x^2 + x + 1. В бинарном виде мы не будем учитывать старший член, тогда получится:
0b11
. -
Число
a
x + 1 (0b11
). -
Число
b
x + 1 (0b11
).
Мы должны произвести простое умножение a
на b
.
Действуем по алгоритму и начинаем цикл из двух итераций:
-
Первая итерация.
-
Проверка младшего бита числа
b
(0b11
). Он ненулевой.r
(0b11
) =b
(0b11
)XOR
r
(0b00
). -
Старший бит числа
a
(0b11
) ненулевой. Запоминаем. -
Сдвигаем число
a
влево.a
(0b10
) =a
(0b11
) << 1. -
Так как число
a
у нас переполнилось, а мы это помним, то производим взятие остатка по модулю.a
(0b01
) =a
(0b10
)XOR
неприводимый многочлен (0b11
). -
Сдвигаем число
b
вправо.b
(0b01
) =b
(0b11
) >> 1.
-
Первая итерация закончилась. Давайте взглянем на ее результат:
-
Число
a
1 (0b01
). -
Число
b
1 (0b01
). -
Число
r
x + 1 (0b11
).
-
Вторая итерация.
-
Проверка младшего бита числа
b
(0b01
). Он ненулевой.r
(0b10
) =b
(0b01
)XOR
r
(0b11
). -
Старший бит числа
a
(0b01
) нулевой. Запоминаем. -
Сдвигаем число
a
влево.a
(0b10
) =a
(0b01
) << 1. -
Число
a
у нас не переполнялось, а значит дополнительных действий не требуется. -
Сдвигаем число
b
вправо.b
(0b00
) =b
(0b01
) >> 1.
-
Вторая итерация закончилась. Можно принимать результат умножения:
-
Число
a
x (0b10
). -
Число
b
0 (0b00
). -
Число
r
x (0b10
).
Внимательные читатели заметили, что после первого действия второй итерации можно было прекращать вычисления, так как результирующее число больше не изменится.
Для разнообразия мы можем прорешать этот же пример естественным методом:
-
(x + 1) * (x + 1).
-
(x + 1) * x + (x + 1).
Мы просто раскрыли скобки. -
x^2 + x + (x + 1).
Еще раз раскрыли скобки. Теперь нам необходимо взять остаток по модулю. Правую часть пока не трогаем. -
1 + (x + 1).
Дело за малым — складывая две единицы мы получаем ноль. -
x.
Вот и результат.
Теперь мы можем провести аналогию. В конце первой итерации мы получили в результате x + 1. В конце второй итерации мы получили сложение x + 1 с единицей. Это если по-простому.
Если же мы начнем анализировать глубже, то обнаружим, что умножение в поле сводится к простым операциям:
-
Умножению на x (2).
-
Взятию остатка по модулю.
-
Сложению.
Как в начале этого объяснения упоминал:
-
Умножение — это сдвиги.
-
Взятие остатка — это операция
XOR
с неприводимым многочленом. -
Сложение — это тоже операция
XOR
.
Надеюсь, объяснение этой действительно сложной функции было достаточно простым и подробным. Больше сложных функций не будет, можно расслабиться.
Преобразование R
Это преобразование гораздо более простое для понимания. Мы работает с одним 128-битным числом result
. Нам необходимо преобразовать байты этого числа по следующему алгоритму:
/// # Преобразование R fn transform_r(result: &mut [u8; 16]) { result.rotate_right(1); let mut temp = 0; for (i, e) in result.iter().enumerate() { temp ^= Self::gf_multiply(*e, L[i]); } result[0] = temp; }
Алгоритм:
-
Циклически сдвинем число
result
на 1 байт вправо. -
Перемножим каждый байт на соответствующее значение из последовательности
L
. -
Результаты перемножений последовательно будем отправлять в операцию
XOR
. -
Результат
XOR
положим в первый байт числаresult
.
Поскольку из 16-байтной последовательности неизменными остались только 15 байт, то мы всегда сможем восстановить 16-й, информация о нем осталась в первом байте, который мы заменили. Операция XOR
обратима.
Накладывая маску дважды с помощью
XOR
, мы отменяем ее действие. Соответственно в этом преобразовании мы наложили ее единожды, а в обратном преобразовании сделаем это еще раз. Таким образом мы восстановим оригинальное значение замененного байта.
Последовательность значений L
:
pub const L: [u8; 16] = [ 0x01, 0x94, 0x20, 0x85, 0x10, 0xc2, 0xc0, 0x01, 0xfb, 0x01, 0xc0, 0xc2, 0x10, 0x85, 0x20, 0x94, ];
Это тоже константа, поэтому можем определить ее там же, где и матрицы Pi
.
Обратное преобразование R
Здесь мы совершаем, очевидно, обратные действия преобразования R. Как уже было написано, обращаем действие XOR
вспять, получая исходный 16-й байт оригинального числа.
/// # Преобразование обратное преобразованию R fn transform_r_rev(result: &mut [u8; 16]) { let mut temp = 0; for (i, e) in result.iter().enumerate() { temp ^= Self::gf_multiply(*e, L[i]); } result[0] = temp; result.rotate_left(1); }
Преобразование L
Максимально простое преобразование.
/// # Преобразование L fn transform_l(result: &mut [u8; 16]) { for _ in 0..16 { Self::transform_r(result); } }
Мы применим операцию преобразования R 16 раз к 16 байтам. Как вы помните — мы каждый раз циклически сдвигаем последовательность, а в первый байт кладем результат XOR
всех байтов.
Получается мы циклически сдвигаем входящую последовательность 16 раз.
Обратное преобразование L
В предыдущем пункте я назвал преобразование L простым. Так вот я ошибся — это еще проще.
/// # Преобразование обратное преобразованию L fn transform_l_rev(result: &mut [u8; 16]) { for _ in 0..16 { Self::transform_r_rev(result); } }
Абсолютно то же самое, но с применением обратного преобразования R.
Преобразование F
Это преобразование немного сложнее, но оно использует только наши предыдущие преобразования.
Для шифрования нам необходимы итерационные ключи (10 штук). Так вот с помощью этой функции мы их формировать и будем.
/// # Итерация развертывания ключа fn transform_f( in_key_1: &mut [u8; 16], in_key_2: &mut [u8; 16], out_key_1: &mut [u8; 16], out_key_2: &mut [u8; 16], iter_constant: &mut [u8; 16], ) { let mut temp = [0u8; 16]; out_key_2.copy_from_slice(in_key_1); Self::transform_x(in_key_1, iter_constant, &mut temp); Self::transform_s(&mut temp); Self::transform_l(&mut temp); Self::transform_x(&temp, in_key_2, out_key_1); }
Итак, преобразование F принимает на вход пять ссылок:
-
Две из них — это входные ключи, материал для формирования выходных ключей.
-
Еще две из них — это выходные ключи, результат манипуляций.
-
Последняя — итерационная константа.
Создадим временную переменную для хранения промежуточного состояния первого выходного ключа. Кстати, второй выходной ключ известен сразу — это первый входной ключ.
Ну а дальше весьма простые операции:
-
XOR
между первым входным ключом и итерационной константой с сохранением во временную переменную. -
Преобразование S над временной переменной.
-
Преобразование L над временной переменной.
-
XOR
между временной переменной и вторым входным ключом с сохранением уже в первый выходной ключ.
Функция формирования итерационных ключей
Последняя крупная функция необходимая для формирования итерационных ключей шифрования и расшифровывания.
pub fn new(key: &[u8]) -> Result<Self, CipherError>
Сигнатура функции выглядит так — мы просто принимаем срез байт в качестве ключа, а возвращаем результат, который содержит либо ошибку, либо объект шифра.
// Формирование итерационных констант let mut iter_constants = [[0u8; 16]; 32]; for (i, e) in iter_constants.iter_mut().enumerate() { e[15] = i as u8 + 1; Self::transform_l(e); }
Создаем итерационные константы:
-
Нам понадобятся 32 итерационные константы. Сами константы — это 16 байтные числа изначально равные нулю.
-
Далее мы должны эти константы инициализировать уже нужными значениями. Эти значения формируются очень просто — это просто номера этих констант. То есть из 16 байт итерационной константы мы поменяем только последний, куда запишем значение порядкового номера.
-
Далее такую итерационную константу необходимо изменить с помощью преобразования L.
let mut round_keys = [[0u8; 16]; ROUNDS]; let mut temp_1 = [0u8; 16]; let mut temp_2 = [0u8; 16]; let mut temp_3 = [0u8; 16]; let mut temp_4 = [0u8; 16]; round_keys[0].copy_from_slice(&key[..16]); round_keys[1].copy_from_slice(&key[16..]); temp_1.copy_from_slice(&round_keys[0]); temp_2.copy_from_slice(&round_keys[1]);
Следующим шагом подготовимся к формированию итерационных ключей.
Нам понадобятся:
-
Переменная для хранения итерационных ключей.
-
Переменные для хранения промежуточных итерационных ключей.
Начальная инициализация происходит так:
-
Первых два раундовых ключа мы получаем из самого ключа шифрования. Просто делим эту последовательность на 2 части по 16 байт.
-
Этими же значениями инициализируем первые промежуточные ключи.
for i in 0..4 { Self::transform_f(&mut temp_1, &mut temp_2, &mut temp_3, &mut temp_4, &mut iter_constants[8 * i]); Self::transform_f(&mut temp_3, &mut temp_4, &mut temp_1, &mut temp_2, &mut iter_constants[1 + 8 * i]); Self::transform_f(&mut temp_1, &mut temp_2, &mut temp_3, &mut temp_4, &mut iter_constants[2 + 8 * i]); Self::transform_f(&mut temp_3, &mut temp_4, &mut temp_1, &mut temp_2, &mut iter_constants[3 + 8 * i]); Self::transform_f(&mut temp_1, &mut temp_2, &mut temp_3, &mut temp_4, &mut iter_constants[4 + 8 * i]); Self::transform_f(&mut temp_3, &mut temp_4, &mut temp_1, &mut temp_2, &mut iter_constants[5 + 8 * i]); Self::transform_f(&mut temp_1, &mut temp_2, &mut temp_3, &mut temp_4, &mut iter_constants[6 + 8 * i]); Self::transform_f(&mut temp_3, &mut temp_4, &mut temp_1, &mut temp_2, &mut iter_constants[7 + 8 * i]); round_keys[2 + 2 * i].copy_from_slice(&temp_1); round_keys[3 + 2 * i].copy_from_slice(&temp_2); }
И наконец мы переходим к циклу формирования оставшихся 8 раундовых ключей:
-
Цикл состоит из четырех итераций в результате которых будут формироваться очередные два раундовых ключа.
-
Сами ключи формируются одним лишь преобразованием F, в которое подают промежуточные ключи.
-
Каждый раз в преобразование F дополнительно подается итерационная константа. Самих преобразований F в итоге будет 32 штуки, поскольку в каждой итерации цикла выработки раундовых ключей 8 вызовов преобразования F, поэтому ранее мы как раз выработали эти итерационные константы именно в таком количестве.
Сначала мы подаем на вход первые два ключа, а результат принимаем в последние два. Далее преобразование повторяется, но на этот раз мы на вход подаем последние два ключа, а результат принимаем в первые два. И так 4 раза.
По итогу в первых двух промежуточных ключах будут находиться раундовые ключи. Сохраняем их и продолжаем цикл выработки ключей.
Функция шифрования
Пройдя все эти сложные преобразования и функции мы, наконец, добрались до заветного шифрования.
fn encrypt_block(&self, block: &[u8]) -> Result<Vec<u8>, CipherError>
Сигнатура функции шифрования выглядит так. Мы определяли так называемые трейты в статье о режимах шифрования. Эти трейты нужны для обобщения каких-либо функций, например, функций шифра: шифровать и расшифровывать.
Поэтому мы принимаем блок данных на вход, а возвращаем либо ошибку, либо зашифрованный блок данных.
let mut block_exact: [u8; 16] = [0u8; 16]; block_exact.copy_from_slice(block);
Поскольку в «Магме» нам не приходилось использовать функции с аргументами конкретного размера, то и такого шага не было.
Здесь мы просто объявляем блок данных строго определенного размера и копируем данные из блока с неопределенным размером.
for key in self.round_keys[..9].iter() { Self::transform_x(key, &block_exact.clone(), &mut block_exact); Self::transform_s(&mut block_exact); Self::transform_l(&mut block_exact); } Self::transform_x(&self.round_keys[9], &block_exact.clone(), &mut block_exact);
Вот и ядро — заветные вызовы функций, которые позволят нам перевести данные в такой вид, который условно невозможно будет прочитать, не зная секрет.
Мы должны произвести девять с половиной итераций, чтобы произвести шифрование.
Первые девять итераций производятся так:
-
XOR
между итерационным ключом и блоком данных с сохранением результата. -
Преобразование S.
-
Преобразование L.
А последняя, десятая, итерация состоит лишь из одного XOR
между последним итерационным ключом и блоком данных с сохранением результата.
Функция расшифровывания
Функция расшифровывания производит абсолютно те же операции, что и функция шифрования, но в обратном порядке.
fn decrypt_block(&self, block: &[u8]) -> Result<Vec<u8>, CipherError>
Подходящая для трейта сигнатура функции.
let mut block_exact: [u8; 16] = [0u8; 16]; block_exact.copy_from_slice(block);
Копирование данных в блок определенного размера.
Self::transform_x(&self.round_keys[9], &block_exact.clone(), &mut block_exact); for key in self.round_keys[..9].iter().rev() { Self::transform_l_rev(&mut block_exact); Self::transform_s_rev(&mut block_exact); Self::transform_x(key, &block_exact.clone(), &mut block_exact); }
Применение операций в обратном порядке. Не забываем и итерационные ключи применять в обратном порядке.
Проверка и эталонные значения
При проверке шифра «Кузнечик» я не пользовался какими-то новыми средствами в отличие от «Магмы».
Использование значений из RFC 7801 сильно помогает определять ошибки еще на состоянии написания фундаментальных функций.
CyberChef содержит функции шифрования как по алгоритму «Магма», так и по алгоритму «Кузнечик», предлагая различные режимы шифрования. Проблема, описанная мною в статье про алгоритм «Магма», сохраняется — CyberChef не производит корректное дополнение, однако сделав это вручную — работоспособность алгоритма подтверждается.
Заключение проверки
running 12 tests test tests::cipher::kuznyechik::gf_multiply_test::test_gf_multiply ... ok test tests::cipher::kuznyechik::keys_test::test_invalid_key_lenght - should panic ... ok test tests::cipher::kuznyechik::keys_test::test_invalid_zeroed_key - should panic ... ok test tests::cipher::kuznyechik::transform_r_test::test_transform_r ... ok test tests::cipher::kuznyechik::transform_l_test::test_transform_l ... ok test tests::cipher::kuznyechik::transform_l_test::test_transform_l_rev ... ok test tests::cipher::kuznyechik::transform_r_test::test_transform_r_rev ... ok test tests::cipher::kuznyechik::transform_s_test::test_transform_s ... ok test tests::cipher::kuznyechik::transform_s_test::test_transform_s_rev ... ok test tests::cipher::kuznyechik::encrypt_test::test_encryption ... ok test tests::cipher::kuznyechik::decrypt_test::test_decryption ... ok test tests::cipher::kuznyechik::keys_test::test_key_generation ... ok test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured; 11 filtered out; finished in 0.00s
Тесты, работоспособность которых вы можете проверить самостоятельно (результат полностью воспроизводимый), выполняются ожидаемым образом — все верно. Как минимум один блок данных мы точно можем зашифровать и расшифровать верно.
Заключение
digit4lsh4d0w
Автор
А что в итоге ?
Эта статья была написана в 23:30 31 декабря 2024 года во Владивостоке. Сейчас можно подвести итог — у меня получилось рассмотреть в этом году две темы: алгоритмы хэширования и алгоритмы шифрования. Получилось применить Rust в этих задачах имея нулевой опыт как в разработке, так и алгоритмах.
С помощью этих материалов у меня получилось немного облегчить жизнь тем, кому подготовлены задания по реализации этих алгоритмов в университетах.
Надеюсь, что я и сам получил бесценный опыт:
-
Попрактиковался в разъяснении сложных и не очень тем.
-
Научился понимать как код на Rust, так и некоторые, важные для программиста, вещи.
Кроме того, к статьям оставляли бесценные комментарии, которые помогали разобраться в неочевидных тонкостях.
Поздравляю вас с новым 2025 годом! Желаю, чтобы ваш код всегда был чистым и эффективным, а баги обходили вас стороной. Пусть алгоритмы, которые вы создаёте, будут оптимальными и элегантными.
В новом году я желаю вам новых возможностей для роста и развития. Пусть каждый проект, над которым вы работаете, будет успешным и принесёт вам удовлетворение. Желаю, чтобы вы могли реализовать свои самые смелые идеи и создать что-то действительно значимое.
Помните, что программирование — это не только работа, но и творчество. Не бойтесь экспериментировать и искать новые подходы к решению задач. Именно так рождаются самые интересные и инновационные проекты.
Желаю вам вдохновения, терпения и настойчивости. Пусть новый год принесёт вам много радости, счастья и, конечно же, успехов в программировании!
С Новым годом!
Услышимся в Telegram.
Весь код сохранен в репозитории GitVerse.
Источники
ссылка на оригинал статьи https://habr.com/ru/articles/871092/
Добавить комментарий