Логика выполнения MD5

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

512 бит 512 бит

Рис. 9.3. Логика выполнения MD5

Алгоритм получает на входе сообщение произвольной длины, обрабатывает его блоками по 512 бит и создает в качестве выхода дайджест сообщения длиной 128 бит. Алгоритм состоит из следующих шагов:

Шаг 1: добавление недостающих битов

Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина ≡ 448 mod 512). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

64-битное представление длины исходного (до добавления) сообщения в битах присоединяется к результату первого шага. Если первоначальная длина больше, чем 2⁶⁴, то используются только последние 64 бита. Таким образом, поле содержит длину исходного сообщения по модулю 2⁶⁴.

В результате первых двух шагов создается сообщение, длина которого кратна 512 битам. Это расширенное сообщение представляется как последовательность 512-битных блоков Y₀, Y₁,..., Y_L-1, при этом общая длина расширенного сообщения равна L * 512 битам. L – число блоков по 512 бит исходного сообщения. Таким образом, длина полученного расширенного сообщения кратна шестнадцати 32-битным словам.

Рис. 9.4. Структура расширенного сообщения

Шаг 3: инициализация MD-буфера

Используется 128-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются следующими шестнадцатеричными числами:

А = 01234567

В = 89ABCDEF

C = FEDCBA98

D = 76543210

Шаг 4: обработка последовательности 512-битных (16-словных) блоков

Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как H_MD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую f_F, f_G, f_H и f_I соответственно. В каждом цикле выполняется перемешивание битов блока сообщения с битами промежуточного состояния.

После выполнения четырёх циклов промежуточное состояние регистров складывается с текущим результатом для получения выходного значения функции.

Каждый цикл принимает в качестве входа текущий 512-битный блок Y_q, обрабатывающийся в данный момент, и 128-битное значение буфера ABCD, которое является промежуточным значением работы алгоритма, и изменяет содержимое этого буфера. Каждый цикл также использует четвертую часть 64-элементной таблицы T[1... 64], построенной на основе функции sin. i-ый элемент T, обозначаемый T[i], имеет значение, равное целой части от 2³² * abs (sin (i)), i задано в радианах. Так как abs (sin (i)) является числом между 0 и 1, каждый элемент Т является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения MD_q+1 выход четырех циклов складывается по модулю 2³² с MD_q. Сложение выполняется независимо для каждого из четырех слов в буфере.

Шаг 5: выход

После обработки всех L 512-битных блоков выходом L-ой стадии является 128-битный дайджест сообщения.

Обработка 512 битного блока сообщения по алгоритму MD5 представлена на рисунке 9.5.

Рис. 9.5. Обработка очередного 512 битного блока по алгоритму MD5

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