Привет, сейчас речь пойдет про разбор и реализацию алгоритма хеширования md5 на языке C++. Сам алгоритм раньше широко применялся для проверки целостности информации и для хранения паролей, пока его не признали небезопасным.
Историю алгоритма вы можете прочитать на Википедии:
Эта статья написана для начинающих, которым интересно как этот алгоритм работает изнутри и как его реализовать. Моя реализация алгоритма является обучающей, то есть код работает не так быстро, но позволяет понять как устроен md5. От читателей требуется базовое знание C++ и минимальный опыт работы с памятью и указателями. Начнем.
Алгоритм состоит из нескольких шагов, которые мы сейчас рассмотрим и сразу же реализуем.
Step 0
Сам алгоритм принимает на вход двоичную последовательность любой длины. Мы же будем решать немного иную задачу. А именно, на вход нашей программы будет поступать строго набор байтов, нежели двоичная последовательность в чистом виде. Хранить мы будем это как указатель на начало последовательности и её длину в байтах. Это наши входные данные.
Я назвал переменную saved_length, потому что в процессе длина последовательности будет увеличиваться, и алгоритм требует что бы мы помнили первоначальный размер.
Step 1. Append Padding Bits
«Добавить к последовательности единичный бит, затем добавлять нулевые биты, пока длина последовательности не станет сравнима с 448 по модулю 512 в битах.».
Поскольку мы работаем с байтами, то нам нужно добавить единичный байт 0x80 (1000 0000), и добавлять нулевые байты (0x00), пока длина последовательности не станет сравнима с 56 по модулю 64 в байтах. Создадим указатель end, который всегда будет ссылаться на байт, находящийся сразу за последним байтом нашей последовательности. И с помощью него реализуем эту несложную функцию.
Step 2. Append Length
«Добавьте к последовательности её первоначальную длину в битах в 64-битном формате в порядке байт little-endian».
Перед тем как проделать этот шаг, напишем функцию, которая определяет порядок байт на исполняемом компьютере. Сделаем это следующим образом: создадим int, которому присвоим ему значение 1, и посмотрим на левый байт этого числа. Если он равен 1, то определим порядок байт как little-endian, если 0, то big-endian. Конечно, это не сработает при middle-endian, но к счастью он очень редко встречается, так что можно им пренебречь.
Поскольку saved_length содержит длину входных данных в байтах, а нам нужно записать в длину в битах, то создадим новую переменную, которой присвоим значение saved_length * 8, и с помощью функции Memory Copy скопируем её в конец последовательности.
Далее если на исполняемом компьютере little-endian, то шаг выполнен, если big-endian, то вручную сделаем реверс-байт.
Первые два шага реализованы, теперь расскажу для чего они нужны. Они называются подготовительным этапом, и собственно нужны для подготовки перед основными вычислениями.
И подготовительный этап в md5 как раз реализован так, чтобы такого избежать. При разных входных данных в md5 всегда будут разные результаты подготовительного этапа.
Step 3. Initialize MD Buffer
Теперь нам нужно создать буфер, в котором будут храниться результаты промежуточных вычислений.
Буфер представляет из себя четыре 32-битных переменных, начальные значения вы видите на изображении.
Каждая переменная буфера должна содержать 4 байта, которые принимают значения, как показано на изображении. На картинке слева изображен левый байт, а справа — правый. Я не использую понятия младший и старший, потому что эти понятия разные для разных порядков байтов, и это может запутать. Левый и правый более проще и универсальнее.
Абсолютно все результаты вычислений над нашей последовательностью будут записываться туда. И спойлер, в конце это и будет 128-битный хеш.
Теперь как это реализовать.
Первый способ - проверяем какой порядок байт на исполняемом компьютере и в зависимости от этого инициализируем переменные.
Второй способ — принудительно задать байты без ветвлений.
Мне второй вариант нравится больше, я буду использовать его.
Step 4. Process Message in 16-Word Blocks
Это основной шаг нашего алгоритма. Текущая последовательность разбивается на блоки по 64 байта (512 бит), и в каждом блоке происходит много раундов, которые грубо говоря перемешивают и сжимают информацию.
Сперва реализуем функцию, которая бежит по всей последовательности, и для каждого блока вызывает метод, обрабатывающий сам 64-байтный блок.
В качестве аргумента передаем адрес начала блока.
Теперь определим несколько функций и констант, которые нам пригодятся при вычислениях.
Каждая из этих функций принимает на вход три 32-битных переменные, и возвращает тоже 32-битную переменную. Они нужны для «перемешивания» информации, повышения криптостойкости.
Реализуем их:
Теперь определим массив констант T:
Эти константы аналогично нужны для повышения криптостойкости. Их можно рассчитать заранее и вставить в программу готовый вариант:
Теперь перейдем к самому блоку
Перед вычислениями в каждом блоке нужно сохранить текущее состояние буфера.
Длина блока составляет 64 байта, и его разделяют на 16 32-битных переменных. Создадим массив int block[16], и скопируем туда текущий блок.
Теперь происходит 64 раунда. Каждый раунд имеет следующий вид:
На картинке A, B, C, D локальные, не наш буфер.
"<<<" - побитовый циклический сдвиг влево.
Если упростить запись, то получим:
Function – это одна из функций F, G, H, I, какая именно где используется сейчас поймете.
Теперь происходит 64 раунда. Вот они:
64 раунда разделяются на 4 этапа по 16 раундов. В первом этапе при вычислениях используется функция F, во втором — G, в третьем — H, в четвертом — I.
Наших текущий знаний достаточно что бы написать функцию round, которая будет выступать в роли оператора, принимающая на вход все аргументы оператора, и адрес функции, которая будет использоваться при вычислениях.
И при реализации функции process_block пропишем все раунды вручную.
В конце прибавляем к нашему буферу, его состояние, которое было до вычисления этих 64 раундов.
Подробнее про раунды
На самом деле все 64 раунда можно реализовать с помощью цикла, нежели прописывать вручную. Это вовсе необязательно, и для понимая алгоритма не требуется. Но кому интересно, то я сейчас расскажу закономерности в этих раундах:
1) первые 4 аргумента оператора, это наш буфер, который с каждым раундом циклически сдвигается вправо на единицу.
2) пятый аргумент k зависит от номера текущего раунда. Пусть i - номер текущего раунда (нумерация с 1), тогда k можно рассчитать по следующему правилу:
3) Шестой аргумент - s. Используется для циклического побитого сдвига на s байтов. Для каждого из 4-этапов есть повторяются 4 значения s. Для первого этапа повторяются значения {7, 12, 17, 22}, для второго - {5, 9, 14, 20}, для третьего - {4, 11, 16, 23}, для четвертого - {6, 10, 15, 21}.
4) Ну и седьмой аргумент i. Этот аргумент всегда равен номеру текущего раунда, и используется для добавления в хеш констант T.
Эта информация необязательна для понимания алгоритма, она нужна лишь для тех кто хочет рассчитать раунды в цикле, нежели прописывать их вручную.
Step 5. Output
Md5-хеш начинается с левого байта A, и заканчивая правым байтом D. В обучающих целях упакуем это в std::vector.
Ну и собственно сама MD5 функция:
Заметьте что я выделяю новую память на 100 байт больше, копирую туда входные данные, и вычисляю хеш на ней. Это сделано потому что на этапах append_padding_bits и append_length мы изменяем значения на неизвестном участке памяти, что может вызвать проблемы, если мы случайно изменим что-то важное.
Теперь научимся переводить хеш из std::vector в std::string.
Ну и собственно весь код целиком, включая int main:
Запустим, и проведем немного тестов.
На этом моя обучающая реализация закончилась. Целью было объяснить как работает алгоритм, и написать его самую наивную реализацию. Если устроить test_speed, то на i3 7100 (3.9 GHZ) я получил 980 000 хешей в секунду. Много это или мало - философский вопрос. Но hashlib.md5() в python на аналогичном тесте показала 1 500 000 хешей в секунду.
Реализацию можно улучшить следующем образом:
Историю алгоритма вы можете прочитать на Википедии:
Ссылка скрыта от гостей
.Эта статья написана для начинающих, которым интересно как этот алгоритм работает изнутри и как его реализовать. Моя реализация алгоритма является обучающей, то есть код работает не так быстро, но позволяет понять как устроен md5. От читателей требуется базовое знание C++ и минимальный опыт работы с памятью и указателями. Начнем.
Алгоритм состоит из нескольких шагов, которые мы сейчас рассмотрим и сразу же реализуем.
Step 0
Сам алгоритм принимает на вход двоичную последовательность любой длины. Мы же будем решать немного иную задачу. А именно, на вход нашей программы будет поступать строго набор байтов, нежели двоичная последовательность в чистом виде. Хранить мы будем это как указатель на начало последовательности и её длину в байтах. Это наши входные данные.
C++:
void* input;
uint64_t saved_length;Step 1. Append Padding Bits
«Добавить к последовательности единичный бит, затем добавлять нулевые биты, пока длина последовательности не станет сравнима с 448 по модулю 512 в битах.».
Поскольку мы работаем с байтами, то нам нужно добавить единичный байт 0x80 (1000 0000), и добавлять нулевые байты (0x00), пока длина последовательности не станет сравнима с 56 по модулю 64 в байтах. Создадим указатель end, который всегда будет ссылаться на байт, находящийся сразу за последним байтом нашей последовательности. И с помощью него реализуем эту несложную функцию.
C++:
uint8_t* end;
void append_padding_bits() {
end = static_cast<uint8_t*>(input) + saved_length;
*end = 0x80;
++end;
while ((end - static_cast<uint8_t*>(input)) % 64 != 56)
*end = 0x00, ++end;
}«Добавьте к последовательности её первоначальную длину в битах в 64-битном формате в порядке байт little-endian».
Перед тем как проделать этот шаг, напишем функцию, которая определяет порядок байт на исполняемом компьютере. Сделаем это следующим образом: создадим int, которому присвоим ему значение 1, и посмотрим на левый байт этого числа. Если он равен 1, то определим порядок байт как little-endian, если 0, то big-endian. Конечно, это не сработает при middle-endian, но к счастью он очень редко встречается, так что можно им пренебречь.
C++:
#define LITTLE_ENDIAN 0
#define BIG_ENDIAN 1
bool endian() {
uint32_t i = 1;
uint8_t *p = reinterpret_cast<uint8_t*>(&i);
if (*p == 1)
return LITTLE_ENDIAN;
else
return BIG_ENDIAN;
}Далее если на исполняемом компьютере little-endian, то шаг выполнен, если big-endian, то вручную сделаем реверс-байт.
C++:
void append_length() {
uint64_t length = saved_length * 8;
memcpy(static_cast<void*>(end), &length, 8);
if (endian() == BIG_ENDIAN) {
std::swap(*end, *(end + 7));
std::swap(*(end + 1), *(end + 6));
std::swap(*(end + 2), *(end + 5));
std::swap(*(end + 3), *(end + 4));
}
end += 8;
}- Во-первых, последовательность стала кратна 512 битам (64 байта). Это нужно, потому что в дальнейшем последовательность разделяется на блоки по 512 бит, и там уже обрабатывается каждый блок.
- Во-вторых, добавляя единичный бит и исходную длину, можно гарантировать что при разных входных данных, последовательности будут оставаться разными после подготовительного этапа.
И подготовительный этап в md5 как раз реализован так, чтобы такого избежать. При разных входных данных в md5 всегда будут разные результаты подготовительного этапа.
Step 3. Initialize MD Buffer
Теперь нам нужно создать буфер, в котором будут храниться результаты промежуточных вычислений.
Буфер представляет из себя четыре 32-битных переменных, начальные значения вы видите на изображении.
Каждая переменная буфера должна содержать 4 байта, которые принимают значения, как показано на изображении. На картинке слева изображен левый байт, а справа — правый. Я не использую понятия младший и старший, потому что эти понятия разные для разных порядков байтов, и это может запутать. Левый и правый более проще и универсальнее.
Абсолютно все результаты вычислений над нашей последовательностью будут записываться туда. И спойлер, в конце это и будет 128-битный хеш.
Теперь как это реализовать.
Первый способ - проверяем какой порядок байт на исполняемом компьютере и в зависимости от этого инициализируем переменные.
C++:
uint32_t a;
uint32_t b;
uint32_t c;
uint32_t d;
void init_buffer() {
if(endian() == LITTLE_ENDIAN) {
a = 0x67452301;
b = 0xefcdab89;
c = 0x98badcfe;
d = 0x10325476;
}
else {
a = 0x01234567;
b = 0x89abcdef;
c = 0xfedcba98;
d = 0x76543210;
}
}
C++:
uint32_t a;
uint32_t b;
uint32_t c;
uint32_t d;
void init_buffer() {
uint8_t _a[4] = { 0x01, 0x23, 0x45, 0x67 };
uint8_t _b[4] = { 0x89, 0xab, 0xcd, 0xef };
uint8_t _c[4] = { 0xfe, 0xdc, 0xba, 0x98 };
uint8_t _d[4] = { 0x76, 0x54, 0x32, 0x10 };
a = *reinterpret_cast<uint32_t*>(&_a);
b = *reinterpret_cast<uint32_t*>(&_b);
c = *reinterpret_cast<uint32_t*>(&_c);
d = *reinterpret_cast<uint32_t*>(&_d);
}Step 4. Process Message in 16-Word Blocks
Это основной шаг нашего алгоритма. Текущая последовательность разбивается на блоки по 64 байта (512 бит), и в каждом блоке происходит много раундов, которые грубо говоря перемешивают и сжимают информацию.
Сперва реализуем функцию, которая бежит по всей последовательности, и для каждого блока вызывает метод, обрабатывающий сам 64-байтный блок.
C++:
void process() {
uint8_t* temp = static_cast<uint8_t*>(input);
while (temp != end)
process_block(temp), temp += 64;
}Теперь определим несколько функций и констант, которые нам пригодятся при вычислениях.
Каждая из этих функций принимает на вход три 32-битных переменные, и возвращает тоже 32-битную переменную. Они нужны для «перемешивания» информации, повышения криптостойкости.
Реализуем их:
C++:
uint32_t F(uint32_t x, uint32_t y, uint32_t z) { return (x & y) | (~x & z); }
uint32_t G(uint32_t x, uint32_t y, uint32_t z) { return (x & z) | (~z & y); }
uint32_t H(uint32_t x, uint32_t y, uint32_t z) { return x ^ y ^ z; }
uint32_t I(uint32_t x, uint32_t y, uint32_t z) { return y ^ (~z | x); }Эти константы аналогично нужны для повышения криптостойкости. Их можно рассчитать заранее и вставить в программу готовый вариант:
C++:
const uint32_t t[65] = { 0,
0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
};Перед вычислениями в каждом блоке нужно сохранить текущее состояние буфера.
C++:
uint32_t aa = a, bb = b, cc = c, dd = d;Теперь происходит 64 раунда. Каждый раунд имеет следующий вид:
На картинке A, B, C, D локальные, не наш буфер.
"<<<" - побитовый циклический сдвиг влево.
Если упростить запись, то получим:
Function – это одна из функций F, G, H, I, какая именно где используется сейчас поймете.
Теперь происходит 64 раунда. Вот они:
Код:
[abcd 0 7 1][dabc 1 12 2][cdab 2 17 3][bcda 3 22 4]
[abcd 4 7 5][dabc 5 12 6][cdab 6 17 7][bcda 7 22 8]
[abcd 8 7 9][dabc 9 12 10][cdab 10 17 11][bcda 11 22 12]
[abcd 12 7 13][dabc 13 12 14][cdab 14 17 15][bcda 15 22 16]
[abcd 1 5 17][dabc 6 9 18][cdab 11 14 19][bcda 0 20 20]
[abcd 5 5 21][dabc 10 9 22][cdab 15 14 23][bcda 4 20 24]
[abcd 9 5 25][dabc 14 9 26][cdab 3 14 27][bcda 8 20 28]
[abcd 13 5 29][dabc 2 9 30][cdab 7 14 31][bcda 12 20 32]
[abcd 5 4 33][dabc 8 11 34][cdab 11 16 35][bcda 14 23 36]
[abcd 1 4 37][dabc 4 11 38][cdab 7 16 39][bcda 10 23 40]
[abcd 13 4 41][dabc 0 11 42][cdab 3 16 43][bcda 6 23 44]
[abcd 9 4 45][dabc 12 11 46][cdab 15 16 47][bcda 2 23 48]
[abcd 0 6 49][dabc 7 10 50][cdab 14 15 51][bcda 5 21 52]
[abcd 12 6 53][dabc 3 10 54][cdab 10 15 55][bcda 1 21 56]
[abcd 8 6 57][dabc 15 10 58][cdab 6 15 59][bcda 13 21 60]
[abcd 4 6 61][dabc 11 10 62][cdab 2 15 63][bcda 9 21 64]Наших текущий знаний достаточно что бы написать функцию round, которая будет выступать в роли оператора, принимающая на вход все аргументы оператора, и адрес функции, которая будет использоваться при вычислениях.
C++:
uint32_t rotate_left(uint32_t x, uint32_t s) { return (x << s) | (x >> (32 - s)); }
void round(uint32_t& a, uint32_t b, uint32_t c, uint32_t d, uint32_t k, uint32_t s, uint32_t i, uint32_t(*function)(uint32_t, uint32_t, uint32_t)) {
a += function(b, c, d) + block[k] + t[i];
a = rotate_left(a, s);
a += b;
}
C++:
uint32_t block[16];
void process_block(uint8_t* adress) {
memcpy(&block, static_cast<void*>(adress), 64);
uint32_t aa = a, bb = b, cc = c, dd = d;
round(a, b, c, d, 0, 7, 1, F);
round(d, a, b, c, 1, 12, 2, F);
round(c, d, a, b, 2, 17, 3, F);
round(b, c, d, a, 3, 22, 4, F);
round(a, b, c, d, 4, 7, 5, F);
round(d, a, b, c, 5, 12, 6, F);
round(c, d, a, b, 6, 17, 7, F);
round(b, c, d, a, 7, 22, 8, F);
round(a, b, c, d, 8, 7, 9, F);
round(d, a, b, c, 9, 12, 10, F);
round(c, d, a, b, 10, 17, 11, F);
round(b, c, d, a, 11, 22, 12, F);
round(a, b, c, d, 12, 7, 13, F);
round(d, a, b, c, 13, 12, 14, F);
round(c, d, a, b, 14, 17, 15, F);
round(b, c, d, a, 15, 22, 16, F);
round(a, b, c, d, 1, 5, 17, G);
round(d, a, b, c, 6, 9, 18, G);
round(c, d, a, b, 11, 14, 19, G);
round(b, c, d, a, 0, 20, 20, G);
round(a, b, c, d, 5, 5, 21, G);
round(d, a, b, c, 10, 9, 22, G);
round(c, d, a, b, 15, 14, 23, G);
round(b, c, d, a, 4, 20, 24, G);
round(a, b, c, d, 9, 5, 25, G);
round(d, a, b, c, 14, 9, 26, G);
round(c, d, a, b, 3, 14, 27, G);
round(b, c, d, a, 8, 20, 28, G);
round(a, b, c, d, 13, 5, 29, G);
round(d, a, b, c, 2, 9, 30, G);
round(c, d, a, b, 7, 14, 31, G);
round(b, c, d, a, 12, 20, 32, G);
round(a, b, c, d, 5, 4, 33, H);
round(d, a, b, c, 8, 11, 34, H);
round(c, d, a, b, 11, 16, 35, H);
round(b, c, d, a, 14, 23, 36, H);
round(a, b, c, d, 1, 4, 37, H);
round(d, a, b, c, 4, 11, 38, H);
round(c, d, a, b, 7, 16, 39, H);
round(b, c, d, a, 10, 23, 40, H);
round(a, b, c, d, 13, 4, 41, H);
round(d, a, b, c, 0, 11, 42, H);
round(c, d, a, b, 3, 16, 43, H);
round(b, c, d, a, 6, 23, 44, H);
round(a, b, c, d, 9, 4, 45, H);
round(d, a, b, c, 12, 11, 46, H);
round(c, d, a, b, 15, 16, 47, H);
round(b, c, d, a, 2, 23, 48, H);
round(a, b, c, d, 0, 6, 49, I);
round(d, a, b, c, 7, 10, 50, I);
round(c, d, a, b, 14, 15, 51, I);
round(b, c, d, a, 5, 21, 52, I);
round(a, b, c, d, 12, 6, 53, I);
round(d, a, b, c, 3, 10, 54, I);
round(c, d, a, b, 10, 15, 55, I);
round(b, c, d, a, 1, 21, 56, I);
round(a, b, c, d, 8, 6, 57, I);
round(d, a, b, c, 15, 10, 58, I);
round(c, d, a, b, 6, 15, 59, I);
round(b, c, d, a, 13, 21, 60, I);
round(a, b, c, d, 4, 6, 61, I);
round(d, a, b, c, 11, 10, 62, I);
round(c, d, a, b, 2, 15, 63, I);
round(b, c, d, a, 9, 21, 64, I);
a += aa, b += bb, c += cc, d += dd;
}Подробнее про раунды
На самом деле все 64 раунда можно реализовать с помощью цикла, нежели прописывать вручную. Это вовсе необязательно, и для понимая алгоритма не требуется. Но кому интересно, то я сейчас расскажу закономерности в этих раундах:
1) первые 4 аргумента оператора, это наш буфер, который с каждым раундом циклически сдвигается вправо на единицу.
2) пятый аргумент k зависит от номера текущего раунда. Пусть i - номер текущего раунда (нумерация с 1), тогда k можно рассчитать по следующему правилу:
Код:
k = i-1 if 1 <= i <= 16
k = ((i-1)*5+1) mod 16 if 17 <= i <= 32
k = ((i-1)*3+5) mod 16 if 33 <= i <= 48
k = ((i-1)*7) mod 16 if 49 <= i <= 644) Ну и седьмой аргумент i. Этот аргумент всегда равен номеру текущего раунда, и используется для добавления в хеш констант T.
Эта информация необязательна для понимания алгоритма, она нужна лишь для тех кто хочет рассчитать раунды в цикле, нежели прописывать их вручную.
Step 5. Output
Md5-хеш начинается с левого байта A, и заканчивая правым байтом D. В обучающих целях упакуем это в std::vector.
C++:
std::vector<uint8_t> finish() {
std::vector<uint8_t> hash(16);
memcpy(&hash[0], &a, 4);
memcpy(&hash[4], &b, 4);
memcpy(&hash[8], &c, 4);
memcpy(&hash[12], &d, 4);
return hash;
}
C++:
std::vector<uint8_t> MD5(void* original_input, uint64_t size) {
uint8_t* place = new uint8_t[size + 100];
memcpy(static_cast<void*>(place), original_input, size);
input = static_cast<void*>(place);
saved_length = size;
append_padding_bits();
append_length();
init_buffer();
process();
delete[] place;
return finish();
}Теперь научимся переводить хеш из std::vector в std::string.
C++:
std::string md5hash_to_string(std::vector<uint8_t> hash) {
std::string hex_char = "0123456789abcdef";
std::string ret = "";
for (int i = 0; i < 16; ++i) {
ret += hex_char[hash[i] >> 4];
ret += hex_char[hash[i] & 0x0F];
}
return ret;
}
C++:
#include <cstdint>
#include <memory.h>
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#define LITTLE_ENDIAN 0
#define BIG_ENDIAN 1
bool endian() {
uint32_t i = 1;
uint8_t *p = reinterpret_cast<uint8_t*>(&i);
if (*p == 1)
return LITTLE_ENDIAN;
else
return BIG_ENDIAN;
}
void* input;
uint64_t saved_length;
uint8_t* end;
uint32_t a;
uint32_t b;
uint32_t c;
uint32_t d;
uint32_t block[16];
const uint32_t t[65] = { 0,
0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
};
void append_padding_bits() {
end = static_cast<uint8_t*>(input) + saved_length;
*end = 0x80;
++end;
while ((end - static_cast<uint8_t*>(input)) % 64 != 56)
*end = 0x00, ++end;
}
void append_length() {
uint64_t length = saved_length * 8;
memcpy(static_cast<void*>(end), &length, 8);
if (endian() == BIG_ENDIAN) {
std::swap(*end, *(end + 7));
std::swap(*(end + 1), *(end + 6));
std::swap(*(end + 2), *(end + 5));
std::swap(*(end + 3), *(end + 4));
}
end += 8;
}
void init_buffer() {
uint8_t _a[4] = { 0x01, 0x23, 0x45, 0x67 };
uint8_t _b[4] = { 0x89, 0xab, 0xcd, 0xef };
uint8_t _c[4] = { 0xfe, 0xdc, 0xba, 0x98 };
uint8_t _d[4] = { 0x76, 0x54, 0x32, 0x10 };
a = *reinterpret_cast<uint32_t*>(&_a);
b = *reinterpret_cast<uint32_t*>(&_b);
c = *reinterpret_cast<uint32_t*>(&_c);
d = *reinterpret_cast<uint32_t*>(&_d);
}
uint32_t rotate_left(uint32_t x, uint32_t s) { return (x << s) | (x >> (32 - s)); }
uint32_t F(uint32_t x, uint32_t y, uint32_t z) { return (x & y) | (~x & z); }
uint32_t G(uint32_t x, uint32_t y, uint32_t z) { return (x & z) | (~z & y); }
uint32_t H(uint32_t x, uint32_t y, uint32_t z) { return x ^ y ^ z; }
uint32_t I(uint32_t x, uint32_t y, uint32_t z) { return y ^ (~z | x); }
void round(uint32_t& a, uint32_t b, uint32_t c, uint32_t d, uint32_t k, uint32_t s, uint32_t i, uint32_t(*function)(uint32_t, uint32_t, uint32_t)) {
a += function(b, c, d) + block[k] + t[i];
a = rotate_left(a, s);
a += b;
}
void process_block(uint8_t* adress) {
memcpy(&block, static_cast<void*>(adress), 64);
uint32_t aa = a, bb = b, cc = c, dd = d;
round(a, b, c, d, 0, 7, 1, F);
round(d, a, b, c, 1, 12, 2, F);
round(c, d, a, b, 2, 17, 3, F);
round(b, c, d, a, 3, 22, 4, F);
round(a, b, c, d, 4, 7, 5, F);
round(d, a, b, c, 5, 12, 6, F);
round(c, d, a, b, 6, 17, 7, F);
round(b, c, d, a, 7, 22, 8, F);
round(a, b, c, d, 8, 7, 9, F);
round(d, a, b, c, 9, 12, 10, F);
round(c, d, a, b, 10, 17, 11, F);
round(b, c, d, a, 11, 22, 12, F);
round(a, b, c, d, 12, 7, 13, F);
round(d, a, b, c, 13, 12, 14, F);
round(c, d, a, b, 14, 17, 15, F);
round(b, c, d, a, 15, 22, 16, F);
round(a, b, c, d, 1, 5, 17, G);
round(d, a, b, c, 6, 9, 18, G);
round(c, d, a, b, 11, 14, 19, G);
round(b, c, d, a, 0, 20, 20, G);
round(a, b, c, d, 5, 5, 21, G);
round(d, a, b, c, 10, 9, 22, G);
round(c, d, a, b, 15, 14, 23, G);
round(b, c, d, a, 4, 20, 24, G);
round(a, b, c, d, 9, 5, 25, G);
round(d, a, b, c, 14, 9, 26, G);
round(c, d, a, b, 3, 14, 27, G);
round(b, c, d, a, 8, 20, 28, G);
round(a, b, c, d, 13, 5, 29, G);
round(d, a, b, c, 2, 9, 30, G);
round(c, d, a, b, 7, 14, 31, G);
round(b, c, d, a, 12, 20, 32, G);
round(a, b, c, d, 5, 4, 33, H);
round(d, a, b, c, 8, 11, 34, H);
round(c, d, a, b, 11, 16, 35, H);
round(b, c, d, a, 14, 23, 36, H);
round(a, b, c, d, 1, 4, 37, H);
round(d, a, b, c, 4, 11, 38, H);
round(c, d, a, b, 7, 16, 39, H);
round(b, c, d, a, 10, 23, 40, H);
round(a, b, c, d, 13, 4, 41, H);
round(d, a, b, c, 0, 11, 42, H);
round(c, d, a, b, 3, 16, 43, H);
round(b, c, d, a, 6, 23, 44, H);
round(a, b, c, d, 9, 4, 45, H);
round(d, a, b, c, 12, 11, 46, H);
round(c, d, a, b, 15, 16, 47, H);
round(b, c, d, a, 2, 23, 48, H);
round(a, b, c, d, 0, 6, 49, I);
round(d, a, b, c, 7, 10, 50, I);
round(c, d, a, b, 14, 15, 51, I);
round(b, c, d, a, 5, 21, 52, I);
round(a, b, c, d, 12, 6, 53, I);
round(d, a, b, c, 3, 10, 54, I);
round(c, d, a, b, 10, 15, 55, I);
round(b, c, d, a, 1, 21, 56, I);
round(a, b, c, d, 8, 6, 57, I);
round(d, a, b, c, 15, 10, 58, I);
round(c, d, a, b, 6, 15, 59, I);
round(b, c, d, a, 13, 21, 60, I);
round(a, b, c, d, 4, 6, 61, I);
round(d, a, b, c, 11, 10, 62, I);
round(c, d, a, b, 2, 15, 63, I);
round(b, c, d, a, 9, 21, 64, I);
a += aa, b += bb, c += cc, d += dd;
}
void process() {
uint8_t* temp = static_cast<uint8_t*>(input);
while (temp != end)
process_block(temp), temp += 64;
}
std::vector<uint8_t> finish() {
std::vector<uint8_t> hash(16);
memcpy(&hash[0], &a, 4);
memcpy(&hash[4], &b, 4);
memcpy(&hash[8], &c, 4);
memcpy(&hash[12], &d, 4);
return hash;
}
std::vector<uint8_t> MD5(void* original_input, uint64_t size) {
uint8_t* place = new uint8_t[size + 100];
memcpy(static_cast<void*>(place), original_input, size);
input = static_cast<void*>(place);
saved_length = size;
append_padding_bits();
append_length();
init_buffer();
process();
delete[] place;
return finish();
}
std::string md5hash_to_string(std::vector<uint8_t> hash) {
std::string hex_char = "0123456789abcdef";
std::string ret = "";
for (int i = 0; i < 16; ++i) {
ret += hex_char[hash[i] >> 4];
ret += hex_char[hash[i] & 0x0F];
}
return ret;
}
int main() {
//#define test_speed
#ifndef test_speed
std::string s;
while (true) {
std::cout << "Input: ";
std::getline(std::cin, s);
std::cout << "Hash: " << md5hash_to_string(MD5(&s[0], s.size())) << std::endl;
}
#else
int arr[500];
int counter = 0;
int start = clock();
while(clock() - start < 1000)
MD5(&arr[counter%500], 7), counter++;
std::cout << counter;
#endif
return 0;
}
Код:
Input: md5
Hash: 1bc29b36f623ba82aaf6724fd3b16718
Input: md4
Hash: c93d3bf7a7c4afe94b64e30c2ce39f4f
Input: hello
Hash: 5d41402abc4b2a76b9719d911017c592
Input: Hello
Hash: 8b1a9953c4611296a827abf8c47804d7Реализацию можно улучшить следующем образом:
- Убрать std::vector. У меня это дало +300 000 хешей в секунду.
- Убрать вызовы функций. Заменив функцию round на аналоги через #define я получил +1 200 000 хешей в секунду.
- Убрать выделение новой памяти. Я еще это не реализовывал, и не знаю насколько это улучшит производительность.
- Научить алгоритм хешировать файлы. Уже сейчас можно скопировать файл в строку и прохешировать её, но это не эффективно для больших файлов. Нужно подгружать и хешировать файл по частям, но это изменит порядок алгоритма и с этим нужно повозится.
Последнее редактирование:
