MD5
Оглавление
Описание
Алгоритм
Пример
MD5 (англ. Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из
Массачусетского Технологического Института (MIT, Massachusetts Institute of Technlogy) в 1991 году.
Предназначендля создания «отпечатков» или «дайджестов» сообщений произвольной длины.
Пришёл на смену MD4, который был несовершенен. Работает на 32-битных машинах.
Зная MD5, невозможно восстановить входное сообщение, так как одному MD5 могут соответствовать разные сообщения.
Используется для проверки подлинности опубликованных сообщений путем сравнения дайджеста сообщения с опубликованным.
Эту операцию называют «проверка хеша» (hashcheck). Описан в RFC 1321.
Алгоритм MD5
На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения может быть
любой (в том числе нулевой). Запишем длину сообщения в L. Это число целое и не отрицательное. Кратность каким-либо
числам не обязательна. После поступления даных идет процесс подготовки потока к вычислениям.
Ниже приведены 5 шагов алгоритма:
Шаг 1. Выравнивание потока
Входные данные выравниваются так, чтобы их размер был сравним с 448 по модулю 512 (L’ = 512 ? N + 448).
Сначала дописывают единичный бит в конец потока, затем необходимое число нулевых бит (выравнивание происходит,
даже если длина уже конгруэнтна — сравнима с 448).
Шаг 2. Добавление длины сообщения.
В оставшиеся 64 бита дописывают 64-битное представление длины данных до выравнивания. Если длина превосходит 2 64 ? 1,
то дописывают только младшие биты. После этого длина потока станет кратной степеням двойки — 16, 32. Вычисления
будут основываться на представлении этого потока данных в виде массива слов по 512 бит.
Шаг 3. Инициализация MD-буфера.
Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами:
А = 01 23 45 67;
В = 89 AB CD EF;
С = FE DC BA 98;
D = 76 54 32 10.
В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется
инициализирующим вектором.
Определим еще функции и константы, которые нам понадобятся для вычислений.
Потребуются 4 функции для четырех раундов. Введем функции от трех параметров — слов, результатом также будет слово.
Определим таблицу констант T[1..64] — 64-элементная таблица данных, построенная следующим образом:
T[i] = int(4294967296 * | sin(i) | ) и s — циклический сдвиг влево на s бит полученого 32-битного аргумента.
Выравненные данные разбиваются на блоки (слова) по 32 бита, и каждый блок проходит 4 раунда из 16 операторов.
Все операторы однотипны и имеют вид: [abcd k s i], определяемый как a = b + ((a + Fun(b,c,d) + X[k] + T[i]) < < < s),
где X — блок данных. X[k] = M [n * 16 + k], где k — номер 32-битного слова из n-го 512-битного блока сообщения.
Шаг 4. Вычисление в цикле
Заносим в блок данных элемент n из массива. Сохраняются значения A, B, C и D, оставшиеся после операций над предыдущими
блоками (или их начальные значения, если блок первый).
AA = A
BB = B
CC = C
DD = D
Раунд 1
/*[abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
[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]
Раунд 2
/*[abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
[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]
Раунд 3
/*[abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
[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]
Раунд 4
/*[abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
[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]
Суммируем с результатом предыдущего цикла:
A = AA + A
B = BB + B
C = CC + C
D = DD + D
После окончания цикла необходимо проверить, есть ли еще блоки для вычислений. Если да, то изменяем номер элемента массива
(n++) и переходим в начало цикла.
Шаг 5. Результат вычислений
Результат вычислений находится в буфере ABCD, это и есть хеш. Если вывести слова в обратном порядке DCBA, то мы получим наш MD5 хеш.
Пример
MD5("md5") = 1bc29b36f623ba82aaf6724fd3b16718
Хеш содержит 128 бит (16 байт) и обычно представляется как последовательность из 32 шестнадцатеричных чисел.
Виды
MD6
MD4
MD5
SECURE HASH ALGORITHM (SHA)
RIPE-MD
HAVAL
MDC
|
|
|
 |
|
