MD5

tiger@ibd.lv

🕛 02.11.2006, 16:38

Данный алгоритм является алгоритмом вычисления "хэш" функции (message digest). В качестве входных данных он принимает сообщение (поток данных) произвольной длины, и вычисляет 128-битный хэш. Нахождение двух различных входных строк, которые производили бы одинаковый MD5 хэш, или нахождение исходной строки по существующему хэш, представляется почти невозмжным (точнее, этим можно заняться имея огромные вычислительные ресурсы, плюс достаточный запас времени). MD5 алгоритм используется в приложениях криптографии и электронно-цифровых подписей для генерации ключа шифрования.
Алгоритм разработан, что бы быть достаточно быстрым на 32-битных системах и не требовать больших объемов памяти. MD5 является чуть более медленным, чем MD4, но является более устойчивым к криптографическим атакам.
Далее под "словом" будет подразумеваться количество информации в 32 бита, а под "байтом" - 8 бит. Последовательность бит интерпретируется в естественной форме - как последовательность байт, где каждая группа из 8 бит является отдельным байтом, причём старший бит байта идет первым. Аналогично представляется последовательность байт, как последовательность слов, только младший байт идет первым.
Предпологается, что в качестве входного потока имеется поток данных N бит. N - неотрицательное целое (возможно 0), не обязательно кратное 8. Для вычисления MD5 хэш функции неоходимо выполнить следующие 5 шагов.

Шаг 1: выравнивание потока.
Входной поток выравнивается так, что бы его длина стала конгруэнтной (сравнимой) с 448 по модулю 512. Выравнивание происходит следующим образом: к потоку добавляется один бит '1', а затем биты '0' до тех пор, пока длина потока не будет сравнима с 448 по модулю 512.
Выравнивание происходит всегда, даже если длина потока была уже сравнима с 448 по модулю 512. Таким образом к потоку добавляется минимум 1 бит, максимум - 512.

Шаг 2: добавление длины.
64 битное представление длины входного потока (длины потока до выравниваия) добавляется к результату предидущего шага. Если длина потока превосходит 2^64, то добавляются младшие 64 бит. Эти биты добавляются как 2 32-битных слова, младшее слово добавляется первым.
Таким образом на этом шаге длина потока становится кратной 512 битам или 16 32-битным словам. Далее будем рассматривать входной поток как массив M[0 ... N-1] слов длиной N.

Шаг 3: инициализация MD буфера.
Буфер из 4 слов {A, B, C, D} используется для вычисления хэш функции, который инициализируется в следующие значения:

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

Шаг 4: обработка потока блоками по 16 слов.
Определим четыре вспомогательные функции, каждая из которых принимает три параметра размеров в слово и производит результат - слово.

F(x, y, z) = (x & y) | (~x & z)
G(x, y, z) = (x & z) | (y & ~z)
H(x, y, z) = x ^ y ^ z
I(x, y, z) = y ^ (x | ~z)

Напомним, что & - побитовое И, | - побитовое ИЛИ, ^ - побитовое исключающее ИЛИ, ~ - побитовое отрицание. Функция F для каждого бита дает следующий результат: если X, то Y, иначе Z.
На этом шаге также используется таблица T[1..64], которая построена с помощью функции синуса: T = int(4294967296 * abs(sin(i))), где int() - целая часть. Например: T[1] = int(4294967296 * abs(sin(i))) = int(3614090360,282...) = 3614090360.
Также следует определить операцию x <<< y, как циклический сдвиг x влево на y бит.
Теперь рассмотрим сам алгоритм вычисления MD5 хэш функции.

// обработать входной поток блоками по 16 слов
for i = 0 to N/16 - 1 do
{
// копировать блок i в X
for j = 0 to 15 do
X[j] = M[i * 16 + j]

// Сохранить значения 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) <<< s)
// исполнить 16 следующих операций
[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) <<< s)
// исполнить 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]
// проход 3
// пусть [abcd k s i] обозначает операцию
// a = b + ((a + H(b, c, d) + X[k] + T) <<< s)
// исполнить 16 следующих операций
[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) <<< s)
// исполнить 16 следующих операций
[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
B += BB
C += CC
D += DD
}

Шаг 5: вывод MD5.
Результат вычисления (хэш) представлен четырьмя 32 битными словами - A, B, C, D (младшим записывается A, старшим - D). 128-битный MD5 хэш готов !

Примеры:
"a" - cc175b9c0f1b6a831c399e269772661
"abc" - 90150983cd24fb0d6963f7d28e17f72
"abrakadabra" - bda3bfdfa868d04f403838f5776f25e
"123456789012345678901234567890123456789012345678901234567890123456
78901234567890" - 57edf4a22be3c955ac49da2e217b67a

Подробнее об алгоритме MD5 можно прочитать в RFC1321.