Как и планировалось, следом за реализацией семейства хэш-функций SHA, появляется Стрибог и тоже в двух версиях, для 256 и 512 бит на выходе. Надеюсь эта статья будет полезна другим студентам. Более опытные разработчики в комментариях приветствуются.
Весь код сохранен в репозитории GitVerse.
Прошлая статья "Реализация SHA256 и SHA512 на языке RUST" очень сильно помогла мне в понимании работы SHA, кроме того в комментариях нашлись поистине полезные советы, спасибо за это!
В основе Стрибог лежат 5 простейших функций:
Сложение двух 512 битных чисел.
X-преобразование.
S-преобразование.
P-преобразование.
L-преобразование.
Из этих функций строятся:
Функция вычисления раундовых ключей.
E-преобразование.
Функция сжатия g.
Общая функция вычисления хэш-суммы.
Сложение двух 512 битных чисел
Как следует из заголовка - необходимо иметь функцию, которая складывает длинные числа, при этом возможное переполнение будет отбрасываться. Так как планируется, что эти два числа a и b мы имеем в виде массивов байт, то и алгоритм будет соответствующий.
Делается это довольно просто, мы берем соответствующие байты из a и b, представляем их в качестве двухбайтовых чисел и складываем.
Возможное переполнение будет учитываться, поскольку мы представили оба числа как двухбайтовые. Переполнение как раз будет храниться во втором байте результирующего числа.
Мы снова делаем приведение типов и кладем младший байт результирующего числа в массив результата result.
На следующей итерации мы делаем все то же самое, но не забываем учесть переполнение, просто сдвигаем результат предыдущего сложения на один байт и добавляем к результату сложения a и b.
Не забываем, что необходимо складывать начиная с младших байт, то есть с конца массивов.
Код
fn add_512(a: &[u8; 64], b: &[u8; 64], result: &mut [u8; 64]) {
let mut temp: u16 = 0;
for i in (0..64).rev() {
temp = a[i] as u16 + b[i] as u16 + (temp >> 8);
result[i] = temp as u8;
}
}Четыре преобразования
Стрибог использует четыре простые функции: X, S, P, L.
X-преобразование
Это простая операция XOR над 512 битными числами. Так же, как и при сложении 512 битных чисел, мы будем перебирать байты входящих массивов a и b, а результат XOR будет укладываться в result.
Код
fn transform_x(a: &[u8; 64], b: &[u8; 64], result: &mut [u8; 64]) {
for (index, byte) in result.iter_mut().enumerate() {
*byte = a[index] ^ b[index];
}
}S-преобразование
Это тоже довольно простое преобразование. Мы перебираем каждый байт входящего массива result и заменяем на тот, что находится в массиве 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,
];Код
fn transform_s(result: &mut [u8; 64]) {
result.iter_mut().for_each(|byte| *byte = PI[*byte as usize]);
}P-преобразование
Это тоже довольно простое преобразование. Мы должны переставить байты из массива result в порядке, который задает массив TAU.
Так как мы в Rust не можем изменять и перебирать один и тот же объект одновременно, то предварительно нужно сделать копию массива result.
Константы
pub const TAU: [u8; 64] = [
0x00, 0x08, 0x10, 0x18, 0x20, 0x28, 0x30, 0x38,
0x01, 0x09, 0x11, 0x19, 0x21, 0x29, 0x31, 0x39,
0x02, 0x0a, 0x12, 0x1a, 0x22, 0x2a, 0x32, 0x3a,
0x03, 0x0b, 0x13, 0x1b, 0x23, 0x2b, 0x33, 0x3b,
0x04, 0x0c, 0x14, 0x1c, 0x24, 0x2c, 0x34, 0x3c,
0x05, 0x0d, 0x15, 0x1d, 0x25, 0x2d, 0x35, 0x3d,
0x06, 0x0e, 0x16, 0x1e, 0x26, 0x2e, 0x36, 0x3e,
0x07, 0x0f, 0x17, 0x1f, 0x27, 0x2f, 0x37, 0x3f,
];Код
fn transform_p(result: &mut [u8; 64]) {
let temp = result.clone();
for (index, position) in TAU.iter().enumerate() {
result[index] = temp[*position as usize];
}
}L-преобразование
А вот это уже чуть более сложное преобразование. На входе мы как всегда имеем 512 битное число result, которое состоит из 64 байт. Мы снова должны сделать приведение типов - склеить каждые 8 байт в одно число. Таким образом из входящих 64 чисел мы получим 8.
Код
let input_u64: [u64; 8] = result.chunks_exact(8)
.map(|bytes| u64::from_be_bytes(bytes.try_into().unwrap()))
.collect::<Vec<u64>>()
.try_into()
.unwrap();Начнем с первого. Всего в этом числе 64 бита, в то же время в массиве A 64 элемента. Мы будем перебирать биты первого числа и если встретим 1, то производим операцию XOR первого элемента массива buffers и элемента из A, который соотвествует индексу бита. Важная особенность заключается в том, что первый элемент массива A находится "в конце", а последний "в начале".
Код
for i in 0..8 {
for j in 0..64 {
if (input_u64[i] >> j) & 1 == 1 {
buffers[i] ^= A[63 - j];
}
}
}В конце не забываем обратно разделить 64 битные числа на байты.
Код
let buffer: [u8; 64] = buffers.iter()
.flat_map(|bytes| bytes.to_be_bytes())
.collect::<Vec<u8>>()
.try_into()
.unwrap();Изначально массив
buffersинициализирован нулями.Для удобства можно инвертировать порядок байт в
A.
Константы
pub const A: [u64; 64] = [
0x8e20faa72ba0b470, 0x47107ddd9b505a38, 0xad08b0e0c3282d1c, 0xd8045870ef14980e,
0x6c022c38f90a4c07, 0x3601161cf205268d, 0x1b8e0b0e798c13c8, 0x83478b07b2468764,
0xa011d380818e8f40, 0x5086e740ce47c920, 0x2843fd2067adea10, 0x14aff010bdd87508,
0x0ad97808d06cb404, 0x05e23c0468365a02, 0x8c711e02341b2d01, 0x46b60f011a83988e,
0x90dab52a387ae76f, 0x486dd4151c3dfdb9, 0x24b86a840e90f0d2, 0x125c354207487869,
0x092e94218d243cba, 0x8a174a9ec8121e5d, 0x4585254f64090fa0, 0xaccc9ca9328a8950,
0x9d4df05d5f661451, 0xc0a878a0a1330aa6, 0x60543c50de970553, 0x302a1e286fc58ca7,
0x18150f14b9ec46dd, 0x0c84890ad27623e0, 0x0642ca05693b9f70, 0x0321658cba93c138,
0x86275df09ce8aaa8, 0x439da0784e745554, 0xafc0503c273aa42a, 0xd960281e9d1d5215,
0xe230140fc0802984, 0x71180a8960409a42, 0xb60c05ca30204d21, 0x5b068c651810a89e,
0x456c34887a3805b9, 0xac361a443d1c8cd2, 0x561b0d22900e4669, 0x2b838811480723ba,
0x9bcf4486248d9f5d, 0xc3e9224312c8c1a0, 0xeffa11af0964ee50, 0xf97d86d98a327728,
0xe4fa2054a80b329c, 0x727d102a548b194e, 0x39b008152acb8227, 0x9258048415eb419d,
0x492c024284fbaec0, 0xaa16012142f35760, 0x550b8e9e21f7a530, 0xa48b474f9ef5dc18,
0x70a6a56e2440598e, 0x3853dc371220a247, 0x1ca76e95091051ad, 0x0edd37c48a08a6d8,
0x07e095624504536c, 0x8d70c431ac02a736, 0xc83862965601dd1b, 0x641c314b2b8ee083,
];Код
fn transform_l(result: &mut [u8; 64]) {
// Объединение 8 байт в одну последовательность
let input_u64: [u64; 8] = result.chunks_exact(8)
.map(|bytes| u64::from_be_bytes(bytes.try_into().unwrap()))
.collect::<Vec<u64>>()
.try_into()
.unwrap();
let mut buffers = [0u64; 8];
for i in 0..8 {
for j in 0..64 {
if (input_u64[i] >> j) & 1 == 1 {
buffers[i] ^= A[63 - j];
}
}
}
// Разделение модифицированной последовательности на части по 8 байт
let buffer: [u8; 64] = buffers.iter()
.flat_map(|bytes| bytes.to_be_bytes())
.collect::<Vec<u8>>()
.try_into()
.unwrap();
for (index, byte) in buffer.iter().enumerate() {
result[index] = *byte;
}
}Функция вычисления раундовых ключей
Теперь, когда у нас есть 4 простых преобразования, мы можем собрать из них функцию вычисления раундовых ключей. Для этого нам понадобятся новые итерационные константы C. Функция принимает массив ключей и индекс итерации. По очереди вызываются преобразования X, S, P, L.
Константы
pub const C: [[u8; 64]; 12] = [
[
0xb1, 0x08, 0x5b, 0xda, 0x1e, 0xca, 0xda, 0xe9, 0xeb, 0xcb, 0x2f, 0x81, 0xc0, 0x65, 0x7c, 0x1f,
0x2f, 0x6a, 0x76, 0x43, 0x2e, 0x45, 0xd0, 0x16, 0x71, 0x4e, 0xb8, 0x8d, 0x75, 0x85, 0xc4, 0xfc,
0x4b, 0x7c, 0xe0, 0x91, 0x92, 0x67, 0x69, 0x01, 0xa2, 0x42, 0x2a, 0x08, 0xa4, 0x60, 0xd3, 0x15,
0x05, 0x76, 0x74, 0x36, 0xcc, 0x74, 0x4d, 0x23, 0xdd, 0x80, 0x65, 0x59, 0xf2, 0xa6, 0x45, 0x07,
],
[
0x6f, 0xa3, 0xb5, 0x8a, 0xa9, 0x9d, 0x2f, 0x1a, 0x4f, 0xe3, 0x9d, 0x46, 0x0f, 0x70, 0xb5, 0xd7,
0xf3, 0xfe, 0xea, 0x72, 0x0a, 0x23, 0x2b, 0x98, 0x61, 0xd5, 0x5e, 0x0f, 0x16, 0xb5, 0x01, 0x31,
0x9a, 0xb5, 0x17, 0x6b, 0x12, 0xd6, 0x99, 0x58, 0x5c, 0xb5, 0x61, 0xc2, 0xdb, 0x0a, 0xa7, 0xca,
0x55, 0xdd, 0xa2, 0x1b, 0xd7, 0xcb, 0xcd, 0x56, 0xe6, 0x79, 0x04, 0x70, 0x21, 0xb1, 0x9b, 0xb7,
],
[
0xf5, 0x74, 0xdc, 0xac, 0x2b, 0xce, 0x2f, 0xc7, 0x0a, 0x39, 0xfc, 0x28, 0x6a, 0x3d, 0x84, 0x35,
0x06, 0xf1, 0x5e, 0x5f, 0x52, 0x9c, 0x1f, 0x8b, 0xf2, 0xea, 0x75, 0x14, 0xb1, 0x29, 0x7b, 0x7b,
0xd3, 0xe2, 0x0f, 0xe4, 0x90, 0x35, 0x9e, 0xb1, 0xc1, 0xc9, 0x3a, 0x37, 0x60, 0x62, 0xdb, 0x09,
0xc2, 0xb6, 0xf4, 0x43, 0x86, 0x7a, 0xdb, 0x31, 0x99, 0x1e, 0x96, 0xf5, 0x0a, 0xba, 0x0a, 0xb2,
],
[
0xef, 0x1f, 0xdf, 0xb3, 0xe8, 0x15, 0x66, 0xd2, 0xf9, 0x48, 0xe1, 0xa0, 0x5d, 0x71, 0xe4, 0xdd,
0x48, 0x8e, 0x85, 0x7e, 0x33, 0x5c, 0x3c, 0x7d, 0x9d, 0x72, 0x1c, 0xad, 0x68, 0x5e, 0x35, 0x3f,
0xa9, 0xd7, 0x2c, 0x82, 0xed, 0x03, 0xd6, 0x75, 0xd8, 0xb7, 0x13, 0x33, 0x93, 0x52, 0x03, 0xbe,
0x34, 0x53, 0xea, 0xa1, 0x93, 0xe8, 0x37, 0xf1, 0x22, 0x0c, 0xbe, 0xbc, 0x84, 0xe3, 0xd1, 0x2e,
],
[
0x4b, 0xea, 0x6b, 0xac, 0xad, 0x47, 0x47, 0x99, 0x9a, 0x3f, 0x41, 0x0c, 0x6c, 0xa9, 0x23, 0x63,
0x7f, 0x15, 0x1c, 0x1f, 0x16, 0x86, 0x10, 0x4a, 0x35, 0x9e, 0x35, 0xd7, 0x80, 0x0f, 0xff, 0xbd,
0xbf, 0xcd, 0x17, 0x47, 0x25, 0x3a, 0xf5, 0xa3, 0xdf, 0xff, 0x00, 0xb7, 0x23, 0x27, 0x1a, 0x16,
0x7a, 0x56, 0xa2, 0x7e, 0xa9, 0xea, 0x63, 0xf5, 0x60, 0x17, 0x58, 0xfd, 0x7c, 0x6c, 0xfe, 0x57,
],
[
0xae, 0x4f, 0xae, 0xae, 0x1d, 0x3a, 0xd3, 0xd9, 0x6f, 0xa4, 0xc3, 0x3b, 0x7a, 0x30, 0x39, 0xc0,
0x2d, 0x66, 0xc4, 0xf9, 0x51, 0x42, 0xa4, 0x6c, 0x18, 0x7f, 0x9a, 0xb4, 0x9a, 0xf0, 0x8e, 0xc6,
0xcf, 0xfa, 0xa6, 0xb7, 0x1c, 0x9a, 0xb7, 0xb4, 0x0a, 0xf2, 0x1f, 0x66, 0xc2, 0xbe, 0xc6, 0xb6,
0xbf, 0x71, 0xc5, 0x72, 0x36, 0x90, 0x4f, 0x35, 0xfa, 0x68, 0x40, 0x7a, 0x46, 0x64, 0x7d, 0x6e,
],
[
0xf4, 0xc7, 0x0e, 0x16, 0xee, 0xaa, 0xc5, 0xec, 0x51, 0xac, 0x86, 0xfe, 0xbf, 0x24, 0x09, 0x54,
0x39, 0x9e, 0xc6, 0xc7, 0xe6, 0xbf, 0x87, 0xc9, 0xd3, 0x47, 0x3e, 0x33, 0x19, 0x7a, 0x93, 0xc9,
0x09, 0x92, 0xab, 0xc5, 0x2d, 0x82, 0x2c, 0x37, 0x06, 0x47, 0x69, 0x83, 0x28, 0x4a, 0x05, 0x04,
0x35, 0x17, 0x45, 0x4c, 0xa2, 0x3c, 0x4a, 0xf3, 0x88, 0x86, 0x56, 0x4d, 0x3a, 0x14, 0xd4, 0x93,
],
[
0x9b, 0x1f, 0x5b, 0x42, 0x4d, 0x93, 0xc9, 0xa7, 0x03, 0xe7, 0xaa, 0x02, 0x0c, 0x6e, 0x41, 0x41,
0x4e, 0xb7, 0xf8, 0x71, 0x9c, 0x36, 0xde, 0x1e, 0x89, 0xb4, 0x44, 0x3b, 0x4d, 0xdb, 0xc4, 0x9a,
0xf4, 0x89, 0x2b, 0xcb, 0x92, 0x9b, 0x06, 0x90, 0x69, 0xd1, 0x8d, 0x2b, 0xd1, 0xa5, 0xc4, 0x2f,
0x36, 0xac, 0xc2, 0x35, 0x59, 0x51, 0xa8, 0xd9, 0xa4, 0x7f, 0x0d, 0xd4, 0xbf, 0x02, 0xe7, 0x1e,
],
[
0x37, 0x8f, 0x5a, 0x54, 0x16, 0x31, 0x22, 0x9b, 0x94, 0x4c, 0x9a, 0xd8, 0xec, 0x16, 0x5f, 0xde,
0x3a, 0x7d, 0x3a, 0x1b, 0x25, 0x89, 0x42, 0x24, 0x3c, 0xd9, 0x55, 0xb7, 0xe0, 0x0d, 0x09, 0x84,
0x80, 0x0a, 0x44, 0x0b, 0xdb, 0xb2, 0xce, 0xb1, 0x7b, 0x2b, 0x8a, 0x9a, 0xa6, 0x07, 0x9c, 0x54,
0x0e, 0x38, 0xdc, 0x92, 0xcb, 0x1f, 0x2a, 0x60, 0x72, 0x61, 0x44, 0x51, 0x83, 0x23, 0x5a, 0xdb,
],
[
0xab, 0xbe, 0xde, 0xa6, 0x80, 0x05, 0x6f, 0x52, 0x38, 0x2a, 0xe5, 0x48, 0xb2, 0xe4, 0xf3, 0xf3,
0x89, 0x41, 0xe7, 0x1c, 0xff, 0x8a, 0x78, 0xdb, 0x1f, 0xff, 0xe1, 0x8a, 0x1b, 0x33, 0x61, 0x03,
0x9f, 0xe7, 0x67, 0x02, 0xaf, 0x69, 0x33, 0x4b, 0x7a, 0x1e, 0x6c, 0x30, 0x3b, 0x76, 0x52, 0xf4,
0x36, 0x98, 0xfa, 0xd1, 0x15, 0x3b, 0xb6, 0xc3, 0x74, 0xb4, 0xc7, 0xfb, 0x98, 0x45, 0x9c, 0xed,
],
[
0x7b, 0xcd, 0x9e, 0xd0, 0xef, 0xc8, 0x89, 0xfb, 0x30, 0x02, 0xc6, 0xcd, 0x63, 0x5a, 0xfe, 0x94,
0xd8, 0xfa, 0x6b, 0xbb, 0xeb, 0xab, 0x07, 0x61, 0x20, 0x01, 0x80, 0x21, 0x14, 0x84, 0x66, 0x79,
0x8a, 0x1d, 0x71, 0xef, 0xea, 0x48, 0xb9, 0xca, 0xef, 0xba, 0xcd, 0x1d, 0x7d, 0x47, 0x6e, 0x98,
0xde, 0xa2, 0x59, 0x4a, 0xc0, 0x6f, 0xd8, 0x5d, 0x6b, 0xca, 0xa4, 0xcd, 0x81, 0xf3, 0x2d, 0x1b,
],
[
0x37, 0x8e, 0xe7, 0x67, 0xf1, 0x16, 0x31, 0xba, 0xd2, 0x13, 0x80, 0xb0, 0x04, 0x49, 0xb1, 0x7a,
0xcd, 0xa4, 0x3c, 0x32, 0xbc, 0xdf, 0x1d, 0x77, 0xf8, 0x20, 0x12, 0xd4, 0x30, 0x21, 0x9f, 0x9b,
0x5d, 0x80, 0xef, 0x9d, 0x18, 0x91, 0xcc, 0x86, 0xe7, 0x1d, 0xa4, 0xaa, 0x88, 0xe1, 0x28, 0x52,
0xfa, 0xf4, 0x17, 0xd5, 0xd9, 0xb2, 0x1b, 0x99, 0x48, 0xbc, 0x92, 0x4a, 0xf1, 0x1b, 0xd7, 0x20,
],
];Код
fn key_schedule(keys: &mut [u8; 64], iter_index: usize) {
transform_x(&keys.clone(), &C[iter_index], keys);
transform_s(keys);
transform_p(keys);
transform_l(keys);
}E-преобразование
E-преобразование является частью функции сжатия, которую использует Стрибог. Здесь тоже уже нет чего-то особенного - мы просто используем, написанные ранее, преобразования. Как можно видеть, в этом преобразовании мы и перебираем все итерационные константы C.
Код
fn transform_e(
keys: &mut [u8; 64],
block: &[u8; 64],
state: &mut [u8; 64]
) {
transform_x(&block, &keys, state);
for i in 0..12 {
transform_s(state);
transform_p(state);
transform_l(state);
key_schedule(keys, i);
transform_x(&state.clone(), &keys, state);
}
}Функция сжатия g
Наконец-то! Это последняя необходимая функция, прежде чем мы приступим уже к вычислению хэш-суммы. Как можно видеть, здесь мы объявляем и инициализируем нулями наши раундовые ключи keys.
Код
fn transform_g(
n: &[u8; 64],
hash: &mut [u8; 64],
message: &[u8; 64],
) {
let mut keys = [0u8; 64];
let mut temp = [0u8; 64];
transform_x(n, hash, &mut keys);
transform_s(&mut keys);
transform_p(&mut keys);
transform_l(&mut keys);
transform_e(&mut keys, message, &mut temp);
transform_x(&temp.clone(), hash, &mut temp);
transform_x(&temp, &message, hash);
}Общая функция вычисления хэш-функции Стрибог
У обоих версий Стрибог одинаковый алгоритм вычисления хэша, разница заключается только в инициализации хэш-суммы и взятии нужной ее части на выходе.
Мы должны инициализировать два вспомогательных массива N и Sigma:
Код
let mut n = [0u8; 64];
let mut sigma = [0u8; 64];Для того, чтобы не расписывать портянку кода для полных и не полных блоков заранее выделим место под сам блок и размер полезных данных блока:
Код
let mut block_size = [0u8; 64];
let mut block: [u8; 64];В block мы будем копировать содержимое каждого очередного блока данных, размер которого равен 512 бит. А в block_size мы будем записывать размер полезных данных блока в битах.
Представим, что у вас есть данные ровно на два блока, то есть 1024 бита. Тогда в обоих случаях block_size будет хранить число 512. Думаю тут все ясно.
Теперь представим, что данных у нас меньше, чем на два блока, например 816 бит. Тогда в первой итерации block_size будет хранить 512, а в следующий раз уже 304.
Интересная особенность заключается в том, что для хранения block_size отводится 64 байта. То есть каждый раз нам нужно будет изменять содержимое только для 2 из 64 байт.
Соответственно, с помощью метода chunks мы разобьем наши данные на куски по 64 байта. Важно отметить, что если длина данных не кратна 64, то последняя часть будет меньше, чем 64 байта.
Код
for chunk in message.chunks(64) {
...
}Для каждого куска данных мы вычисляем размер полезных данных блока по уже приведенному выше алгоритму:
Код
let chunk_size = chunk.len() as u16 * 8;
block_size[62..].copy_from_slice(&chunk_size.to_be_bytes());Очевидно, что зачастую вы вряд ли будете получать данные, длина которых кратна 64 байтам. Поэтому мы будем дополнять необходимые блоки. Это очень простой алгоритм:
Создаем блок, заполненный нулями.
Копируем в него данные, которые у нас есть.
После данных добавляем единицу.
Код
if chunk.len() != 64 {
block = [0u8; 64];
block[..chunk.len()].copy_from_slice(chunk);
block[chunk.len()] = 1;
} else {
...
}После всех манипуляций с данными блока, его необходимо развернуть:
Код
block.reverse();Вообще, здесь такая же ситуация как и с массивом констант A. Первый блок находится "в конце", а последний "в начале". По-хорошему мы должны дополнять сообщение как описано, однако на тестах все работает правильно и следовательно это равноправные операции дополнения.
Теперь, когда у нас есть данные, поделенные на блоки с дополнением, мы можем начать вычисление хэш-суммы. Когда хэш-сумма будет посчитана, ее тоже необходимо развернуть.
Код
fn streebog_core(message: &[u8], hash: &mut [u8; 64]) {
let mut n = [0u8; 64];
let mut sigma = [0u8; 64];
// Массив, хранящий размер полезных данных блока
let mut block_size = [0u8; 64];
let mut block: [u8; 64];
for chunk in message.chunks(64) {
// Вычисление размера полезных данных блока
let chunk_size = chunk.len() as u16 * 8;
block_size[62..].copy_from_slice(&chunk_size.to_be_bytes());
// Дополнение блока
if chunk.len() != 64 {
block = [0u8; 64];
block[..chunk.len()].copy_from_slice(chunk);
block[chunk.len()] = 1;
} else {
block = chunk.try_into().unwrap();
}
block.reverse();
transform_g(&n, hash, &block);
add_512(&n.clone(), &block_size, &mut n);
add_512(&sigma.clone(), &block, &mut sigma);
}
transform_g(&[0u8; 64], hash, &mut n);
transform_g(&[0u8; 64], hash,&mut sigma);
hash.reverse();
}Стрибог 512 и 256
Отличие, как и было сказано, заключается в двух моментах:
Инициализация хэш-суммы.
Выбор необходимой части.
Для 512 битной версии хэш-сумма инициализируется нулями:
Код
let mut hash = [0u8; 64];А для 256 битной версии единицами:
Код
let mut hash = [1u8; 64];При этом 512 битная версия возвращает хэш-сумму полностью, а 256 битная версия только последние 32 байта.
Код 512 битной версии
pub fn streebog_512(message: &[u8]) -> [u8; 64] {
let mut hash = [0u8; 64];
streebog_core(message, &mut hash);
hash
}Код 256 битной версии
pub fn streebog_256(message: &[u8]) -> [u8; 32] {
let mut hash = [1u8; 64];
streebog_core(message, &mut hash);
hash[32..].try_into().unwrap()
}Проверочные значения
Для того, чтобы вы могли проверить свою реализацию алгоритма, я проставил в функции streebog_core отладочные выводы и записал результат дальше.
Streebog512
Подготовленный блок
Block
block = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Преобразование g
Block
block = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Hash
hash = [
0xfa, 0x6a, 0x05, 0xa4, 0x62, 0xb3, 0x0d, 0xfa,
0xf9, 0x23, 0xe1, 0x2d, 0x1d, 0x9a, 0xaf, 0x59,
0x1a, 0x28, 0x70, 0xad, 0xfb, 0x8b, 0x36, 0xb6,
0x56, 0xfd, 0xd1, 0x6c, 0x47, 0x6f, 0x69, 0x3b,
0x3d, 0x99, 0x26, 0xd6, 0xfa, 0x76, 0x81, 0x70,
0x04, 0xb6, 0x4c, 0xe8, 0x3e, 0x91, 0xe0, 0xc0,
0xf7, 0xee, 0xff, 0x26, 0x62, 0xe0, 0xbb, 0x2b,
0x58, 0x06, 0x79, 0xc7, 0x73, 0xde, 0xf1, 0x93,
]Сложение 512 битных чисел
N
n = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58,
]Sigma
sigma = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Преобразование g
Hash
hash = [
0x55, 0x32, 0xef, 0x29, 0x68, 0xcd, 0xaa, 0xf2,
0x8f, 0x9a, 0x9c, 0x1a, 0xd2, 0x0f, 0x9f, 0xb3,
0x1b, 0xa4, 0x49, 0x4e, 0xbd, 0x74, 0x68, 0x3c,
0x5d, 0x3a, 0xb3, 0xf1, 0xc1, 0xe2, 0x28, 0x2d,
0x7c, 0x5a, 0x1e, 0x68, 0x4c, 0xef, 0xea, 0xd3,
0xd7, 0x44, 0xe5, 0x38, 0x11, 0x37, 0x81, 0x12,
0xa6, 0x6f, 0xf1, 0x3a, 0xd6, 0x60, 0x4e, 0x6d,
0xd4, 0xb4, 0x72, 0x57, 0xde, 0x20, 0xfe, 0x7d,
]N
n = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58,
]Преобразование g
Hash
hash = [
0x63, 0xf5, 0xd6, 0x3e, 0xba, 0xa9, 0x68, 0x92,
0xff, 0x38, 0xb7, 0x41, 0xe1, 0x83, 0x9a, 0xcc,
0xa4, 0x7d, 0x15, 0xc0, 0x62, 0xf8, 0x1f, 0xdf,
0x4a, 0x66, 0xf5, 0xb8, 0x76, 0xa0, 0x3f, 0x2f,
0xb0, 0x3c, 0xea, 0x06, 0xb5, 0xb9, 0x38, 0x0c,
0xae, 0x31, 0x28, 0x60, 0xf0, 0x8b, 0xc8, 0x5f,
0x9f, 0xcd, 0x8e, 0x27, 0x8c, 0x2d, 0xd8, 0x55,
0xe8, 0x6c, 0xfa, 0xe9, 0xed, 0x83, 0xd8, 0x84,
]Sigma
sigma = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Разворот
Hash
hash = [
0x84, 0xd8, 0x83, 0xed, 0xe9, 0xfa, 0x6c, 0xe8,
0x55, 0xd8, 0x2d, 0x8c, 0x27, 0x8e, 0xcd, 0x9f,
0x5f, 0xc8, 0x8b, 0xf0, 0x60, 0x28, 0x31, 0xae,
0x0c, 0x38, 0xb9, 0xb5, 0x06, 0xea, 0x3c, 0xb0,
0x2f, 0x3f, 0xa0, 0x76, 0xb8, 0xf5, 0x66, 0x4a,
0xdf, 0x1f, 0xf8, 0x62, 0xc0, 0x15, 0x7d, 0xa4,
0xcc, 0x9a, 0x83, 0xe1, 0x41, 0xb7, 0x38, 0xff,
0x92, 0x68, 0xa9, 0xba, 0x3e, 0xd6, 0xf5, 0x63,
]Streebog256
Подготовленный блок
Block
block = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Преобразование g
Block
block = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Hash
hash = [
0x6e, 0xce, 0x01, 0xd9, 0x11, 0x61, 0x61, 0x69,
0xff, 0xec, 0x67, 0x45, 0xa6, 0xdc, 0x33, 0x67,
0xce, 0x21, 0x48, 0x5f, 0xca, 0xeb, 0x9b, 0x4b,
0x7d, 0x4d, 0x52, 0xd6, 0xb3, 0x73, 0xef, 0xe2,
0x5f, 0x87, 0x70, 0xb0, 0xd2, 0xfd, 0x3c, 0xfa,
0x3d, 0x93, 0xf3, 0x84, 0x24, 0x23, 0xcd, 0x46,
0xca, 0x57, 0xe3, 0x70, 0x01, 0xdc, 0x7d, 0x36,
0x22, 0x4d, 0x04, 0x2a, 0x0c, 0xfb, 0x24, 0x52,
]Сложение 512 битных чисел
N
n = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58,
]Sigma
sigma = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Преобразование g
Hash
hash = [
0xd6, 0xde, 0xec, 0xf8, 0x84, 0x63, 0xd1, 0x1e,
0x02, 0xed, 0x61, 0x5a, 0x7a, 0x2c, 0xfd, 0xf2,
0xd1, 0x3d, 0xd0, 0x13, 0x4d, 0x0c, 0x4a, 0x4d,
0x41, 0x0d, 0x36, 0x20, 0x63, 0x4f, 0xe4, 0x32,
0xdf, 0x19, 0x3e, 0x39, 0x87, 0xf3, 0xac, 0x6f,
0x49, 0x01, 0xe3, 0x97, 0x84, 0x15, 0x76, 0xc5,
0xe3, 0x07, 0xca, 0x16, 0x1a, 0x33, 0x6f, 0xe5,
0xb6, 0x3f, 0xb0, 0xf9, 0x60, 0x69, 0x70, 0xbb,
]N
n = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x58,
]Преобразование g
Hash
hash = [
0x55, 0xa8, 0x58, 0xfe, 0x84, 0xdc, 0x88, 0xcd,
0x5d, 0x15, 0x1c, 0xde, 0x44, 0xea, 0x41, 0x0e,
0xcb, 0xd2, 0x40, 0xe8, 0x32, 0x5b, 0x2f, 0xbd,
0x8a, 0xcf, 0x49, 0xd0, 0x9d, 0xfd, 0x00, 0xc6,
0xe4, 0x7d, 0xf0, 0xc1, 0x1d, 0x65, 0xc9, 0xbf,
0x00, 0x17, 0x36, 0x82, 0xd1, 0x21, 0x16, 0xc7,
0x76, 0x35, 0xa2, 0x76, 0xa5, 0x0b, 0xa0, 0x96,
0xb3, 0x8b, 0xa8, 0x48, 0x17, 0xfe, 0x1e, 0xc3,
]Sigma
sigma = [
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x01, 0x64, 0x6c, 0x72,
0x6f, 0x77, 0x20, 0x6f, 0x6c, 0x6c, 0x65, 0x68,
]Разворот
Hash
hash = [
0xc3, 0x1e, 0xfe, 0x17, 0x48, 0xa8, 0x8b, 0xb3,
0x96, 0xa0, 0x0b, 0xa5, 0x76, 0xa2, 0x35, 0x76,
0xc7, 0x16, 0x21, 0xd1, 0x82, 0x36, 0x17, 0x00,
0xbf, 0xc9, 0x65, 0x1d, 0xc1, 0xf0, 0x7d, 0xe4,
0xc6, 0x00, 0xfd, 0x9d, 0xd0, 0x49, 0xcf, 0x8a,
0xbd, 0x2f, 0x5b, 0x32, 0xe8, 0x40, 0xd2, 0xcb,
0x0e, 0x41, 0xea, 0x44, 0xde, 0x1c, 0x15, 0x5d,
0xcd, 0x88, 0xdc, 0x84, 0xfe, 0x58, 0xa8, 0x55,
]Взятие 32 байт
Hash
hash = [
0xc6, 0x00, 0xfd, 0x9d, 0xd0, 0x49, 0xcf, 0x8a,
0xbd, 0x2f, 0x5b, 0x32, 0xe8, 0x40, 0xd2, 0xcb,
0x0e, 0x41, 0xea, 0x44, 0xde, 0x1c, 0x15, 0x5d,
0xcd, 0x88, 0xdc, 0x84, 0xfe, 0x58, 0xa8, 0x55,
]Хэши
В итоге для фразы hello world мы получили:
Хэш Streebog512:
84d883ede9fa6ce855d82d8c278ecd9f5fc88bf0602831ae0c38b9b506ea3cb02f3fa076b8f5664adf1ff862c0157da4cc9a83e141b738ff9268a9ba3ed6f563Хэш Streebog256:
c600fd9dd049cf8abd2f5b32e840d2cb0e41ea44de1c155dcd88dc84fe58a855
Ответы проходят проверку на Hashing Tools:
Там же вы можете загрузить собственный файл, чтобы сделать более серьезную проверку своего решения. Таким образом я добавил тесты и с файлом тоже. Их вы можете найти в конце файла src/lib.rs в репозитории GitVerse.
Опыт использования Perf
Как и SHA, Стрибог должен был пройти тесты, чтобы я мог убедиться в том, что он отрабатывает верно. В ходе тестов было выявлено, что этот код очень долго, порядка 10 секунд в Debug сборке и 1 секунды в Release сборке, вычисляет хэш-сумму для ~4MiB видео файла.
С помощью поиска получилось понять, что необходимо использовать профилировщик, чтобы попытаться найти бутылочные горлышки этого кода. Спойлер: ускорить не вышло.
Perf показал, что 25% времени выполнения программы на себя забирает L преобразование, однако я не нашел способов ускорить его. Во многих источниках было написано, что можно произвести некоторые приготовления к расчету хэш-суммы, заранее вычислив все возможные варианты, однако это не наш метод.
Используя свой предыдущий опыт и чрезвычайно полезные советы из прошлого поста у меня получилось оптимизировать код до этого состояния.
Как натравить профилировщик на программу:
cargo buildperf record -g ./target/debug/hand-made-streebogperf report
Заключение
digit4lsh4d0w
Автор
Пишу статью второй раз, конечно же где-то могут быть неточности и ошибки. Как и пост про SHA, это записка для студентов и тех, кто просто интересуется. Как и в прошлый раз я надеюсь на конструктивную критику со стороны более опытных программистов.
Любые правки, советы, исправления готов рассмотреть и внести при необходимости. Это можно сделать как в комментариях, так и в репозитории GitVerse.
Еще бы я хотел написать здесь про ключевую хэш-функцию HMAC, использующую результаты предыдущих статей. Напишите комментарии (или поставьте реакции) если бы хотели такой материал.
Источники
WikiPedia. Спецификации и описание.
Habr. Псевдокод, C# код, начальные и промежуточные значения.
Хакер. C код, начальные значения для SHA512.
Cypherpunks Web. Сравнительная таблица Российских и Западных крипто-протоколов. Есть ссылки для каждого примера.
Cypherpunks Git. Веб-обертка для git репозиториев, где можно найти несколько, посвященных Российским крипто-протоколам, проектов.
GitHub. C код.
GitHub. C код.
Hashing Tools. Проверка хэш-сумм.
