Реализация SHA256 и SHA512 на языке RUST01.05.2024 23:00

Написать эту статью меня побудили 2 вещи:

Задание в университете
Слабый пересказ алгоритма SHA256.

Я хотел бы попытаться закрыть пробелы в этой статье своими объяснениями и примерами кода на языке Rust. Будут представлены примеры для алгоритмов SHA256 и SHA512. Надеюсь эта статья будет полезна другим студентам. Более опытные разработчики в комментариях приветствуются.

Весь код сохранен в репозитории GitVerse.

Шаг 1 — заполнение и разделение на блоки

На вход хэш-функции подаются байты исходного сообщения. Характер сообщения нам неизвестен и неважен, это может быть что-угодно — текст, изображение, аудио файл. Входные данные необходимо оформить для дальнейшей работы с ними.

Из данных мы формируем блоки, для SHA256 размер блока равен 64 байтам (512 бит), а для SHA512 128 байт (1024 бита). Данные зачастую имеют не кратный блокам размер, поэтому их приходится дополнять. Алгоритм дополнения един:

Добавить к сообщению байт 0x80. В бинарном виде 0x80 выглядит как 10000000.
Добавить к сообщению нулевые байты 0x00.
Добавить к сообщению восемь байт значения длины входных данных.

Теперь внесем конкретику. Сразу после добавленного байта 0x80 нам необходимо заполнить какое-то количество пространства нулевыми байтами 0x00. Это количество пространства определяет следующей формулой:

$x = b - m - 1 - 8 \pmod b$

Где x — количество нулей для заполнения, b — размер блока данных, m — размер входных данных.

Мы должны точно знать количество нулей в последнем блоке, поэтому вычитаем из размера блока остаток от деления размера входных данных на размер блока. Не стоит забывать и про байт 0x80, который мы добавляем сразу после данных. Кроме того мы должны оставить 8 байт (64 бита) для значения длины входных данных.

Пример блока для алгоритма SHA256

Может получиться такая ситуация, что для поля значения длины входных данных места не остается.

Блок, где почти все место занято данными

В статье, на которую я ссылался выше, этот момент упущен. Однако на Википедии все ясно расписано. Мы добавляем байт 0x80 и оставшееся место заполняем нулями. После этого создается новый блок, который содержит в себе только нули заполнителя и 8 байт (64 бита) значения длины входных данных.

Два блока входных данных для алгоритма SHA256

SHA256:

pub fn sha256(message: &[u8]) -> String {
    let mut m = message.to_vec();
    m.push(0x80);
    if 64 - m.len() % 64 < 8 {
        m.append(&mut vec![0u8; 64 - m.len() % 64])
    }
    m.append(&mut vec![0u8; 64 - m.len() % 64 - 8]);
    m.append(&mut (message.len() as u64 * 8).to_be_bytes().to_vec());
    let blocks = m.chunks_exact(64);

SHA512:

pub fn sha512(message: &[u8]) -> String {
    let mut m = message.to_vec();
    m.push(0x80);
    if 128 - m.len() % 128 < 8 {
        m.append(&mut vec![0u8; 128 - m.len() % 128])
    }
    m.append(&mut vec![0u8; 128 - m.len() % 128 - 8]);
    m.append(&mut (message.len() as u64 * 8).to_be_bytes().to_vec());
    let blocks = m.chunks_exact(128);

Отличие заключается только в том, что в SHA512 размер блок вдвое больше, чем у SHA256, то есть 128 байт (1024 бита).

Шаг 2 — инициализация начальных значений

Мы должны инициализировать две разные переменные. Одна называется h и хранит значения, которые будут изменяться в следующих шагах, что приведет как раз к значению хэша, а другая называется K и хранит раундовые константы, которые понадобятся на этапе сжатия.

SHA256:

let mut h: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];
const K: [u32; 64] = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
    0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
    0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
    0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
    0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
    0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
    0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
    0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
    0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
];

SHA512:

let mut h: [u64; 8] = [
    0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,
    0x510e527fade682d1, 0x9b05688c2b3e6c1f, 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179,
];
const K: [u64; 80] = [
    0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc,
    0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
    0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2,
    0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694,
    0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65,
    0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5,
    0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4,
    0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70,
    0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df,
    0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b,
    0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30,
    0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8,
    0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8,
    0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
    0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec,
    0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b,
    0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178,
    0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b,
    0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c,
    0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817,
];

h хранит значения дробных частей квадратных корней от первых восьми простых чисел. В SHA256 h хранит 32 бита для каждого значения, а в SHA512 64 бита.

Похожий смысл заключен в K. В этой переменной тоже хранятся значения дробных частей, но уже кубических корней от простых чисел. В SHA256 K хранит 64 значения по 32 бита, а в SHA512 80 значений по 64 бита.

Шаг 3 — получение слов

Сейчас начинается этап, где мы будем обрабатывать каждый блок в отдельности. В данный момент мы имеем блок данных и несколько переменных в начальном состоянии. В блоке данные представлены байтами (8 бит), а в переменных h и K 32-х битные и 64-х битные значения. Необходимо произвести приведение типов данных — объединить байты данных в слова w.

SHA256:

for block in blocks {
    let mut w: Vec = block.chunks_exact(4).map(|chunk| {
        u32::from_be_bytes([chunk[0], chunk[1], chunk[2], chunk[3]])
    }).collect();
    w.append(&mut vec![0u32; 48]);

SHA512:

for block in blocks {
    let mut w: Vec = block.chunks_exact(8).map(|chunk| {
        u64::from_be_bytes([chunk[0], chunk[1], chunk[2], chunk[3], chunk[4], chunk[5], chunk[6], chunk[7]])
    }).collect();
    w.append(&mut vec![0u64; 64]);

Из данных блока мы можем получить только 16 слов, но нам необходимо столько, сколько имеется раундовых констант. Мы сразу добавляем в вектор нулевые значения, чтобы заменить их на слова, которые вычислим дальше.

SHA256:

for i in 16..64 {
    let s0 = (w[i - 15].rotate_right(7)) ^ (w[i - 15].rotate_right(18)) ^ (w[i - 15] >> 3);
    let s1 = (w[i - 2].rotate_right(17)) ^ (w[i - 2].rotate_right(19)) ^ (w[i - 2] >> 10);
    w[i] = w[i - 16].wrapping_add(s0).wrapping_add(w[i - 7]).wrapping_add(s1);
}

SHA512:

for i in 16..80 {
    let s0 = (w[i - 15].rotate_right(1)) ^ (w[i - 15].rotate_right(8)) ^ (w[i - 15] >> 7);
    let s1 = (w[i - 2].rotate_right(19)) ^ (w[i - 2].rotate_right(61)) ^ (w[i - 2] >> 6);
    w[i] = w[i - 16].wrapping_add(s0).wrapping_add(w[i - 7]).wrapping_add(s1);
}

Здесь мы используем циклические сдвиги, логические сдвиги и операцию исключающего ИЛИ. Когда мы получаем слово, может возникнуть переполнение при сложении, поэтому в Rust мы используем метод wrapping_add().

Шаг 4 — сжатие

На каждой итерации по блокам, мы создаем временную переменную tmp_h, которая инициализируется со значениями h. Мы будем вносить изменения в tmp_h, которые в итоге повлияют на конечный хэш.

SHA256:

let mut tmp_h: [u32; 8] = h.clone();

SHA512:

let mut tmp_h: [u64; 8] = h.clone();

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

SHA256:

for i in 0..64 {
    let s1 = (tmp_h[4].rotate_right(6)) ^ (tmp_h[4].rotate_right(11)) ^ (tmp_h[4].rotate_right(25));
    let ch = (tmp_h[4] & tmp_h[5]) ^ (!tmp_h[4] & tmp_h[6]);
    let temp1 = tmp_h[7].wrapping_add(s1).wrapping_add(ch).wrapping_add(K[i]).wrapping_add(w[i]);
    let s0 = (tmp_h[0].rotate_right(2)) ^ (tmp_h[0].rotate_right(13)) ^ (tmp_h[0].rotate_right(22));
    let maj = (tmp_h[0] & tmp_h[1]) ^ (tmp_h[0] & tmp_h[2]) ^ (tmp_h[1] & tmp_h[2]);
    let temp2 = s0.wrapping_add(maj);

SHA512:

for i in 0..80 {
    let s1 = (tmp_h[4].rotate_right(14)) ^ (tmp_h[4].rotate_right(18)) ^ (tmp_h[4].rotate_right(41));
    let ch = (tmp_h[4] & tmp_h[5]) ^ (!tmp_h[4] & tmp_h[6]);
    let temp1 = tmp_h[7].wrapping_add(s1).wrapping_add(ch).wrapping_add(K[i]).wrapping_add(w[i]);
    let s0 = (tmp_h[0].rotate_right(28)) ^ (tmp_h[0].rotate_right(34)) ^ (tmp_h[0].rotate_right(39));
    let maj = (tmp_h[0] & tmp_h[1]) ^ (tmp_h[0] & tmp_h[2]) ^ (tmp_h[1] & tmp_h[2]);
    let temp2 = s0.wrapping_add(maj);

Добавляются новые операции: логическое отрицание и логическое И. Заметьте, что сами операции у обоих версий SHA256 и SHA512 одинаковы, меняются только значения сдвигов.

На каждом раунде мы переопределяем значения tmp_h.

SHA256 и SHA512:

tmp_h[7] = tmp_h[6];
tmp_h[6] = tmp_h[5];
tmp_h[5] = tmp_h[4];
tmp_h[4] = tmp_h[3].wrapping_add(temp1);
tmp_h[3] = tmp_h[2];
tmp_h[2] = tmp_h[1];
tmp_h[1] = tmp_h[0];
tmp_h[0] = temp1.wrapping_add(temp2);

В статье, на которую я ссылался выше допущена ошибка. По сути просто забыли указать, что f = e, но в пояснении этот момент есть.

Шаг 5 — внесение изменений в значения хэша

После всех раундов хэширования мы просто складываем соответствующие значения h и tmp_h.

SHA256 и SHA512:

for i in 0..8 {
    h[i] = h[i].wrapping_add(tmp_h[i]);
}

Шаги 3, 4 и 5 будут повторяться для всех блоков, ни один байт входных данных не останется без внимания.

Шаг 6 — получение хэша

В конце h хранит байты, которые и являются составляющими хэша. Части необходимо соединить и конвертировать в строковый вид.

SHA256:

h.iter()
.map(|byte| format!("{:08x}", byte))
.collect::>()
.join("")

SHA512:

h.iter()
.map(|byte| format!("{:016x}", byte))
.collect::>()
.join("")

Ремарка

Есть несколько мест, где могут возникнуть вопросы. Некоторые могут подумать, что алгоритм где-то реализован неправильно. Эта часть предназначена для новичков, люди по-опытнее могут спокойно пропустить.

Этот код был проверен на нескольких примерах с ориентированием на вывод инструментов sha256sum и sha512sum из пакета coreutils версии 9.5.

Не забывайте, что знак переноса строки тоже знак. Он имеет свое байтовое значение, а значит влияет на конечный хэш. "hello world" и "hello world\n" — разные строки и дадут разные значения хэша.
Используя команду echo "hello world" | sha256sum вы отправляете в утилиту строку "hello world\n", то есть с переносом строки.
Не забывайте добавлять избыточные ведущие нули. Значения 0x03 и 0x3 идентичны с точки зрения значения, однако когда вы рассчитаете хэш через свою утилиту и забудете добавить избыточные нули, проверка хэша закончится неудачей.

Заключение

Пишу статью первый раз, возможно где-то написал неточно или даже неверно. Подача тоже может быть довольно куцей, однако я не хотел написать исключительный материал по SHA256/SHA512. Чтобы ознакомиться с этим алгоритмом вам необходимо прочесть больше профессионального материала, а здесь все-таки заметка студента, который затупил в паре мест и решил немного помочь другим.

Любые правки, советы, исправления готов рассмотреть и внести при необходимости. Это можно сделать как в комментариях, так и в репозитории.

Еще бы я хотел написать здесь про хэш-функцию Стрибог (ГОСТ Р 34.11–2012). Напишите комментарии (или поставьте реакции) если бы хотели такой материал.