Алгоритм хэш-функции MD5
В этой статье содержится описание алгоритма *md5*.
Сам алгоритм md5 был создан Риверстом в 1991 году на основе алгоритма md4. MD переводится как Message Digest (цифровой дайджест) и означает, что из произвольной символьной строки может быть получен только один цифровой отпечаток длиной 128 бит.
MD5 можно представить как виртуальный процессор, который (как и все остальные процессоры) состоит из регистров. Вот эти регистры:
- A, B, C и D регистры - предназначены для промежуточного хранения временных данных
- Блочный буфер - состоит из 16 штук 32-разрядных слов
- Байт в буфере - хранит длину или количество байт в блочном буфере
- Размер сообщения - длина исходной строки в битах
- Указатель данных
- Размер данных - последние два регистра определяют текущий обрабатываемый блок
Вид не инициализированного процессора представлен на следующем рисунке:
После первоначальной инициализации (заполнения данными по умолчанию) в регистрах будут содержаться следующие значения:
В этом виртуальном процессоре определены 4 операции (логические функции):
- F(x,y,z) = (x AND y) OR (NOT x AND z)
- G(x,y,z) = (x AND z) OR (y AND NOT z)
- H(x,y,z) = x XOR y XOR z
- I(x,y,z) = y XOR (x OR NOT z)
Так же, определены 4 базовых команды, которые будет выполнять наш процессор. Общий вид команд таков:
A = B + ((A + F(B,C,D) + X[k] + T[i]) <<< s)
Где:
- A, B, C, D – регистры
- F - одна из операций
- X[k] - k-ый элемент блочного буфера (т.е. одно из 16 слов)
- T[i] - i-ый элемент массива констант
- <<< так мы обозначим операцию логического сдвига на S позиций влево
T - специальное усиление алгоритма, представляющее собой белый шум и содержащий псевдослучайные числа зависимые от синуса числа i (4,294,967,296 * abs(sin(i))).
Алгоритм начинается с преобразования регистра A:
Затем модифицируется регистр D:
Каждая такая операция будет считаться элементарной, которую можно обозначить как [ABCD k s I]. Первый раунд можно представть как последовательность таких операций:
- [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]
Всего таких раундов 4. Показывать их все бессмысленно, их при желании можно найти в предлагаемом RFC 1321. После проведения всех раундов и финальной обработки в четырех регистрах A B C D будет содержаться результирующее (или текущее) слово, в результате дающее 128 бит хэша.
Необходимо заметить, что первоначальная инициализация состоит еще и в дописывании в конец потока 1 и некоторого числа нулей до тех пор, пока общая длина не станет равной 512*N+448, где N - любое натуральное число, такое, что это выражение будет наиболее близко к длине блока.