Хэш-функция MD5

Функция MD5 (Message Digest 5) является последней модификацией целого семейства алгоритмов MD (MD2, MD4) и описана в RFC 1321.

Она получает на вход данные произвольной, в том числе и нулевой длины, а на выход выдает значение длиной 16 байт. Применительно к предыдущим обозначениям имеем, что L = 16 байт, а B = 64 байта.

Последовательность работы функции следующая.

1. Сообщение разбивается на блоки по 512 бит (64 байта). Длина последнего блока должна составлять 448 бит. Для этого неполный блок дополняется последовательностью, состоящей из одного единичного бита, за которым следуют нулевые биты. Дополнение также происходит и в случае, если последний блок имеет длину строго 448 байт (в этом случае добавляется одна 1 и 511 нулей).

2. Полученный последний блок из 448 бит дополняется еще 64 битами (до 512), в которых записана исходная длина сообщения в битах. Если исходная длина превышает величину 2⁶⁴, то берутся только последние 64 разряда этого числа. Причем в комбинации используется обратная перестановка. Т.е. первым идет младшее 32-разрядное слово, а затем старшее. В самих словах байты также идут в обратном порядке – от младших к старшим (это связано с представлением чисел в процессорах Intel, на которые ориентирован алгоритм).

3. Внутреннее состояние функции инициализируется стандартными значениями (здесь младшие байты идут первыми):

A = 0x01234567

B = 0x89ABCDEF

С = 0xFEDCBA98

D = 0x76543210

Для дальнейших вычислений также используются четыре функции, выполняющие побитные операции:

F(X,Y,Z) = XY Ú`XZ

G(X,Y,Z) = XZ Ú`ZY

H(X,Y,Z) = X xor Y xor Z

I(X,Y,Z) = Y xor (X Ú`Z)

Кроме того, применяется специальная таблица T из 64-х элементов (от 1 до 64) по 32 бита, значения которых равны

T(i) = [4294967296*abs(sin(i))],

где [] – означает целую часть числа, а i – задается в радианах.

4. Исходное состояние функции меняется путем последовательной обработки блоков данных по 512 бит, которая выполняется на основе следующих соотношений.

Обозначим:

X(j) – j-е слово из 32-х бит в блоке (т.е. от 0 до 15). Причем слово формируется с учетом порядка (сначала идут младшие байты);

N <<< s – циклический сдвиг слова N на s бит влево;

Å – сложение по модулю 2³², т.е. при переполнении слова в 32 бита, соответствующий разряд просто игнорируется.

Текущее состояние функции сохраняется в буфере:

AA = A; BB = B; CC = C; DD = D.

После чего проводится пересчет состояний на базе 4-х последовательно выполняемых операций:

A = B Å ((A Å F(B,C,D) Å X(i₁) Å T(j₁)) <<< s₁)

D = A Å ((D Å F(A,B,C) Å X(i₂) Å T(j₂)) <<< s₂)

C = D Å ((C Å F(D,A,B) Å X(i₃) Å T(j₃)) <<< s₃)

B = C Å ((B Å F(C,D,A) Å X(i₄) Å T(j₄)) <<< s₄)

Каждая из приведенных строк выполняется 16 раз в соответствии с индексами, представленными в табл. 9.4.

Таблица 9.4

После преобразования вычисляется новое состояние хэш-функции:

A = A Å AA; B = B Å BB; C = C Å CC; D = D Å DD.

5. Когда обработка последнего блока завершится, результатом хеширования будет состояние функции. Причем в порядке возрастания значимости байты следуют так: A, B, C, D.