MD5 — 128 битный алгоритм хеширования, предназначенный для создания отпечатка сообщения произвольной длины N и последующей проверки их подлинности. Широко применялся для проверки целостности информации и хранения хешей паролей.
Результат работы алгоритма записывается в массив 4 беззнаковых целых (uint32_t = 4 байт), что эквивалентно непрерывному участку памяти 4*4 байт = 16 байт = 128 бит.
Примечание: обычно рассматривают реализации алгоритма с использованием динамического выделения памяти, автор предлагает реализацию без динамического выделения памяти.
Реализация алгоритма доступна в репозитории C_MD5.
Определим входные данные для функции преобразующей произвольный набор байт в 16 байт числовой информации:
- указатель на массив однобайтовых беззнаковых целых (uint8_t);
- размер массива в байтах (size_t — на 64 битной архитектуре равен 8 байт);
- указатель на массив четырехбайтовых беззнаковых целых (uint32_t).
Проинициализируем массив, содержащий результат, начальными значениями:
result[0] = 0x67452301;
result[1] = 0xefcdab89;
result[2] = 0x98badcfe;
result[3] = 0x10325476;Определим массив k (uint32_t), содержащий 64 константы, участвующие в преобразованиях в соответствии с формулой k[i] = int(232 * sin(i)). Для упрощения работы массив рассчитан заранее:
uint32_t k[] = {
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 r[] = {
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
}; Исходное сообщение разбивается на M отрезков (чанков) размером 512 бит (64 байта), которые обрабатываются в цикле. Пример разделения сообщения на M чанков представлен на рисунке 1.
Размер сообщения должен быть дополнен нулями до размера N mod 64 + 56 байт. Это означает что изначальное сообщение должно иметь возможность разместить единичный бит в конце сообщения и дописать еще 8 байт в конце сообщения, содержащие информацию о количестве бит изначального сообщения. В данной реализации единичный бит в конце сообщения добавляется в формате одного байта = 128 и следовательно формула размера сообщения требует, чтобы в последний чанк помещались 56 байт включая дополнительный (с единицей в старшем бите) и два байта с количеством бит сообщения, в противном случае необходимо создать ещё один чанк.
В цикле по чанкам производится копирование массива с результатами в переменные a,b,c,d (uint32_t).
Для удобства расчетов чанк будет рассматриваться в цикле по i в виде массива uint32_t под названием chunk_4b. Этот цикл (64 итерации = 16 элементов по 4 раунда) в котором производятся основные преобразования чанка:
- вычисления функции раунда (f(b,c,d)) и определение индекса (g) добавляемого значения;
- перестановки и сдвиг:
- temp = d,
- d = c,
- b = b + (a + f(b,c,d) + k[i] + chunk_4b[g]) <<< r[i],
- a = temp.
Примечание: оператор <<< обозначает циклический битовый сдвиг влево и определяется следующим выражением:
(((x) << (c)) | ((x) >> (32 - (c))))Определим функции раундов и соответствующие индексы:
- f(b,c,d) = ((b & c) | ((~b) & d));
g = i; - f(b,c,d) = ((b & d) | ((~d) & c));
g = (5 * i + 1) % 16; - f(b,c,d) = (b ^ c ^ d);
g = (3 * i + 5) % 16; - f(b,c,d) = (c ^ ((~d) | b));
g = (7 * i) % 16;
После окончания цикла с раундами необходимо добавить к значениям результата результаты расчета:
result[0] += a;
result[1] += b;
result[2] += c;
result[3] += d;В результате работы алгоритма должны получиться значения, соответствующие значениям из таблицы 1.
Программа написана в представлении байт big-endian (от старшего к младшему), но результат необходимо рассматривать в представлении little-endian (от младшего к старшему). Для правильного вывода используем указатель uint8_t:
uint8_t *p;
p = (uint8_t *)&result[0];
printf("%2.2x%2.2x%2.2x%2.2x ", p[0], p[1], p[2], p[3]);
p = (uint8_t *)&result[1];
printf("%2.2x%2.2x%2.2x%2.2x ", p[0], p[1], p[2], p[3]);
p = (uint8_t *)&result[2];
printf("%2.2x%2.2x%2.2x%2.2x ", p[0], p[1], p[2], p[3]);
p = (uint8_t *)&result[3];
printf("%2.2x%2.2x%2.2x%2.2x\n", p[0], p[1], p[2], p[3]);Таблица 1 — Результаты работы алгоритма
| Исходная си-строка | Результат |
|---|---|
| md5 | 1bc29b36 f623ba82 aaf6724f d3b16718 |
| 1111111111111111111111111111111111111111111111111111111111111111 | 46f04863 257ac804 0905ea00 02183d35 |
| 1 | 1bc29b36 f623ba82 aaf6724f d3b16718 |
| rekovalev.site | 1649ab49 35ed8df8 4129df2d 846953f9 |
| Test note for hashing | e142ddfb fbb0197d 66943c59 3d45c4c9 |
| Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. | db89bb5c eab87f9c 0fcc2ab3 6c189c2c |