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

Грамотно,почему бы и нет? Есть новшества в обзоре,продолжение не помешает в виде следующей части.
Тем более,что MD5 применим до сих пор и популярен.

 

Жду второй части, спасибо за статью

 

С чего это его признали "признали небезопасным"?
А как же соль?

Простой пример на PHP:

$password = 'password'; // Сам пароль
$hash = md5($password); // Хэшируем первоначальный пароль
$salt = 'sflprt49fhiddFSfsdf$SDfg45fdf3sdfd2'; // Соль

// Солим пароль: конкатенируем старый хэш с солью и ещё раз хэшируем
$saltedHash = md5($hash . $salt);

В данном примере соль является статической строкой, в реальных проектах следует применять только динамическую (то есть каждый раз новую) соль.
И все - радужные понибои идут нервно курить в сторонку.
Если не прав - аргументируйте.

ps.
Статья классная, прочитал взахлеб!

 

С чего это его признали "признали небезопасным"?

Терабайты радужных таблиц для нахождения обратного хеша, методы нахождения/создания коллизий.

Соль конечно решает часть проблем, так что вы правы.

Еще одно возможное решение - использовать нестандартный вектор инициализации (начальное состояние буфера).

PS: спасибо за положительный комментарий

 

С чего это его признали "признали небезопасным"?
А как же соль?

Соль - это изменение и увеличение размера входной строки. Это усложняет прямой брут, но на сам алгоритм и его уязвимости она никак не влияет: те же самые коллизии, как пишет автор в сообщении выше.
Почитать можно тут: MD5 — Википедия
и тут: RFC 6151 - Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms

 

Привет, сейчас речь пойдет про разбор и реализацию алгоритма хеширования md5 на языке C++. Сам алгоритм раньше широко применялся для проверки целостности информации и для хранения паролей, пока его не признали небезопасным.
Историю алгоритма вы можете прочитать на Википедии: https://ru.wikipedia.org/wiki/MD5.

Эта статья написана для начинающих, которым интересно как этот алгоритм работает изнутри и как его реализовать. Моя реализация алгоритма является обучающей, то есть код работает не так быстро, но позволяет понять как устроен md5. От читателей требуется базовое знание C++ и минимальный опыт работы с памятью и указателями. Начнем.

Алгоритм состоит из нескольких шагов, которые мы сейчас рассмотрим и сразу же реализуем.

Step 0

Сам алгоритм принимает на вход двоичную последовательность любой длины. Мы же будем решать немного иную задачу. А именно, на вход нашей программы будет поступать строго набор байтов, нежели двоичная последовательность в чистом виде. Хранить мы будем это как указатель на начало последовательности и её длину в байтах. Это наши входные данные.

void* input;
uint64_t saved_length;

Я назвал переменную saved_length, потому что в процессе длина последовательности будет увеличиваться, и алгоритм требует что бы мы помнили первоначальный размер.

Step 1. Append Padding Bits

«Добавить к последовательности единичный бит, затем добавлять нулевые биты, пока длина последовательности не станет сравнима с 448 по модулю 512 в битах.».

Поскольку мы работаем с байтами, то нам нужно добавить единичный байт 0x80 (1000 0000), и добавлять нулевые байты (0x00), пока длина последовательности не станет сравнима с 56 по модулю 64 в байтах. Создадим указатель end, который всегда будет ссылаться на байт, находящийся сразу за последним байтом нашей последовательности. И с помощью него реализуем эту несложную функцию.

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;
}

Step 2. Append Length

«Добавьте к последовательности её первоначальную длину в битах в 64-битном формате в порядке байт little-endian».

Перед тем как проделать этот шаг, напишем функцию, которая определяет порядок байт на исполняемом компьютере. Сделаем это следующим образом: создадим int, которому присвоим ему значение 1, и посмотрим на левый байт этого числа. Если он равен 1, то определим порядок байт как little-endian, если 0, то big-endian. Конечно, это не сработает при middle-endian, но к счастью он очень редко встречается, так что можно им пренебречь.

#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;
}

Поскольку saved_length содержит длину входных данных в байтах, а нам нужно записать в длину в битах, то создадим новую переменную, которой присвоим значение saved_length * 8, и с помощью функции Memory Copy скопируем её в конец последовательности.

Далее если на исполняемом компьютере little-endian, то шаг выполнен, если big-endian, то вручную сделаем реверс-байт.

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 бит, и там уже обрабатывается каждый блок.
• Во-вторых, добавляя единичный бит и исходную длину, можно гарантировать что при разных входных данных, последовательности будут оставаться разными после подготовительного этапа.

Про второе объясню подробнее. Допустим, мы бы вместо этих двух шагов просто добавляли нули, пока последовательность не станет кратна 512 битам. Тогда для последовательностей (M) и (M + ‘0’) мы бы получали абсолютно одинаковые результаты после подготовительного этапа, а значит и вычисления хеша для них будет одинаковым. Таким образом сразу получили легкую коллизию для разных входных данных.

И подготовительный этап в md5 как раз реализован так, чтобы такого избежать. При разных входных данных в md5 всегда будут разные результаты подготовительного этапа.

Step 3. Initialize MD Buffer

Теперь нам нужно создать буфер, в котором будут храниться результаты промежуточных вычислений.

Буфер представляет из себя четыре 32-битных переменных, начальные значения вы видите на изображении.

Посмотреть вложение 41479

Каждая переменная буфера должна содержать 4 байта, которые принимают значения, как показано на изображении. На картинке слева изображен левый байт, а справа — правый. Я не использую понятия младший и старший, потому что эти понятия разные для разных порядков байтов, и это может запутать. Левый и правый более проще и универсальнее.

Абсолютно все результаты вычислений над нашей последовательностью будут записываться туда. И спойлер, в конце это и будет 128-битный хеш.

Теперь как это реализовать.

Первый способ - проверяем какой порядок байт на исполняемом компьютере и в зависимости от этого инициализируем переменные.

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;
    }
}

Второй способ — принудительно задать байты без ветвлений.

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-байтный блок.

void process() {
    uint8_t* temp = static_cast<uint8_t*>(input);

    while (temp != end)
        process_block(temp), temp += 64;
}

В качестве аргумента передаем адрес начала блока.

Теперь определим несколько функций и констант, которые нам пригодятся при вычислениях.

Посмотреть вложение 41481

Каждая из этих функций принимает на вход три 32-битных переменные, и возвращает тоже 32-битную переменную. Они нужны для «перемешивания» информации, повышения криптостойкости.

Реализуем их:

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); }

Теперь определим массив констант T:

Посмотреть вложение 41482

Эти константы аналогично нужны для повышения криптостойкости. Их можно рассчитать заранее и вставить в программу готовый вариант:

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
};

Теперь перейдем к самому блоку

Перед вычислениями в каждом блоке нужно сохранить текущее состояние буфера.

uint32_t aa = a, bb = b, cc = c, dd = d;

Длина блока составляет 64 байта, и его разделяют на 16 32-битных переменных. Создадим массив int block[16], и скопируем туда текущий блок.

Теперь происходит 64 раунда. Каждый раунд имеет следующий вид:

Посмотреть вложение 41488

На картинке A, B, C, D локальные, не наш буфер.
"<<<" - побитовый циклический сдвиг влево.
Если упростить запись, то получим:

Посмотреть вложение 41484

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]

64 раунда разделяются на 4 этапа по 16 раундов. В первом этапе при вычислениях используется функция F, во втором — G, в третьем — H, в четвертом — I.

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

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;
}

И при реализации функции process_block пропишем все раунды вручную.

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 раундов.

Подробнее про раунды

На самом деле все 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 <= 64

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.

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;
}

Ну и собственно сама MD5 функция:

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();
}

Заметьте что я выделяю новую память на 100 байт больше, копирую туда входные данные, и вычисляю хеш на ней. Это сделано потому что на этапах append_padding_bits и append_length мы изменяем значения на неизвестном участке памяти, что может вызвать проблемы, если мы случайно изменим что-то важное.

Теперь научимся переводить хеш из std::vector в std::string.

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:

#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

На этом моя обучающая реализация закончилась. Целью было объяснить как работает алгоритм, и написать его самую наивную реализацию. Если устроить test_speed, то на i3 7100 (3.9 GHZ) я получил 980 000 хешей в секунду. Много это или мало - философский вопрос. Но hashlib.md5() в python на аналогичном тесте показала 1 500 000 хешей в секунду.

Реализацию можно улучшить следующем образом:

1. Убрать std::vector. У меня это дало +300 000 хешей в секунду.
2. Убрать вызовы функций. Заменив функцию round на аналоги через #define я получил +1 200 000 хешей в секунду.
3. Убрать выделение новой памяти. Я еще это не реализовывал, и не знаю насколько это улучшит производительность.
4. Научить алгоритм хешировать файлы. Уже сейчас можно скопировать файл в строку и прохешировать её, но это не эффективно для больших файлов. Нужно подгружать и хешировать файл по частям, но это изменит порядок алгоритма и с этим нужно повозится.

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

Круто. Хотелось бы статью про sha512, т. к. он очень часто требуется