Алгоритм MD5
Схема работы алгоритма MD5
На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения может быть любой (в том числе нулевой). Запишем длину сообщения в L. Это число целое и неотрицательное. Кратность каким-либо числам необязательна. После поступления данных идёт процесс подготовки потока к вычислениям.
Ниже приведены 5 шагов алгоритма:
[править]Шаг 1. Выравнивание потока
Сначала дописывают единичный бит в конец потока(байт 0x80), затем необходимое число нулевых бит. Входные данные выравниваются так, чтобы их новый размер L' был сравним с 448 по модулю 512 (L’ = 512 × N + 448). Выравнивание происходит, даже если длина уже сравнима с 448.
[править]Шаг 2. Добавление длины сообщения
В оставшиеся 64 бита дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записывают младшие 4 байта. Если длина превосходит 264 − 1, то дописывают только младшие биты. После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.
[править]Шаг 3. Инициализация буфера
Для вычислений инициализируются 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) | ), где 4294967296 = 232.[3]
- Выровненные данные разбиваются на блоки (слова) по 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-битного блока сообщения, и s — циклический сдвиг влево на s бит полученого 32-битного аргумента.
[править]Шаг 4. Вычисление в цикле
Заносим в блок данных элемент n из массива. Сохраняются значения A, B, C и 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, это и есть хеш. Если выводить побайтово начиная с младшего байта A и закончив старшим байтом D, то мы получим MD5 хеш.
[править]
