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

В качестве последнего примера широко используемого криптографического алгоритма мы рассмотрим MD5. MD5 — это хэш-функция для вычисления 128-битных дайджестов сообщений (message digests) фиксированной длины из двоичных исходных строк произвольной длины. Сначала исходная строка дополняется до общей длины в 448 бит (по модулю 512), после чего к ней добавляется длина исходной строки в виде 64-битового целого числа. В результате исходные данные преобразуются в набор 512-битных блоков.

Структура алгоритма приведена на рис. 8.9. Начиная с определенного постоянного 128-битового значения, алгоритм включает в себя k фаз, где k — число 512-битных блоков, получившихся из дополненного согласно алгоритму сообщения. В ходе каждой из фаз из 512-битного блока данных и 128-битного дайджеста, вычисленного на предыдущей фазе, вычисляется новый 128-битный дайджест. Фаза алгоритма MD5 состоит из четырех циклов вычислений, на каждом из которых используется одна из следующих четырех функций:

F(x, y, z) = (х AND у) OR ((NOT х) AND z),

G(x, y, z) = (х AND z) OR (у AND (NOT z)),

H(x, y, z) = x XOR у XOR z,

I(x, y, z) = y XOR (x OR (NOT z)).

Каждая из этих функций работает с 32-битными переменными x, y и z. Чтобы проиллюстрировать, как используются эти функции, рассмотрим 512-битный блок b дополненного сообщения на фазе k. Блок b разделяется на 16 32-битных подблоков b₀, b₁, …, b₁₅. Как показано на рис. 8.10, в ходе первого цикла для изменения четырех переменных (назовем их p, q, r и s соответственно) в ходе 16 итераций используется функция F. Эти переменные переносятся на очередной цикл, а после окончания этой фазы передаются на следующую. Всего существует 64 заранее определенных констант C_i. Для указания циклического сдвига влево используется запись х <<< п: биты в х сдвигаются на п позиций, причем биты, ушедшие за левую границу числа, добавляются справа.

Рис. 8.10. 16 итераций первого цикла MD5

Во втором цикле подобным же образом используется функция G, а H и I — соответственно в третьем и четвертом циклах. Каждый шаг, таким образом, включает в себя 64 итерации, и в очередной фазе используются вычисленные на предыдущей фазе значения р, q, r и s.

Дата добавления: 2014-01-13