Написать эту статью меня побудили 2 вещи:
Задание в университете
Слабый пересказ алгоритма SHA256.
Я хотел бы попытаться закрыть пробелы в этой статье своими объяснениями и примерами кода на языке Rust. Будут представлены примеры для алгоритмов SHA256 и SHA512. Надеюсь эта статья будет полезна другим студентам. Более опытные разработчики в комментариях приветствуются.
Весь код сохранен в репозитории GitVerse.
Шаг 1 - заполнение и разделение на блоки
На вход хэш-функции подаются байты исходного сообщения. Характер сообщения нам неизвестен и неважен, это может быть что-угодно - текст, изображение, аудио файл. Входные данные необходимо оформить для дальнейшей работы с ними.
Из данных мы формируем блоки, для SHA256 размер блока равен 64 байтам (512 бит), а для SHA512 128 байт (1024 бита). Данные зачастую имеют не кратный блокам размер, поэтому их приходится дополнять. Алгоритм дополнения един:
Добавить к сообщению байт
0x80. В бинарном виде0x80выглядит как10000000.Добавить к сообщению нулевые байты
0x00.Добавить к сообщению восемь байт значения длины входных данных.
Теперь внесем конкретику. Сразу после добавленного байта 0x80 нам необходимо заполнить какое-то количество пространства нулевыми байтами 0x00. Это количество пространства определяет следующей формулой:
Где x - количество нулей для заполнения, b - размер блока данных, m - размер входных данных.
Мы должны точно знать количество нулей в последнем блоке, поэтому вычитаем из размера блока остаток от деления размера входных данных на размер блока. Не стоит забывать и про байт 0x80, который мы добавляем сразу после данных. Кроме того мы должны оставить 8 байт (64 бита) для значения длины входных данных.
Может получиться такая ситуация, что для поля значения длины входных данных места не остается.
В статье, на которую я ссылался выше, этот момент упущен. Однако на Википедии все ясно расписано. Мы добавляем байт 0x80 и оставшееся место заполняем нулями. После этого создается новый блок, который содержит в себе только нули заполнителя и 8 байт (64 бита) значения длины входных данных.
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<u32> = 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<u64> = 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::<Vec<String>>()
.join("")SHA512:
h.iter()
.map(|byte| format!("{:016x}", byte))
.collect::<Vec<String>>()
.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). Напишите комментарии (или поставьте реакции) если бы хотели такой материал.
