2.4.2 Реализация хеш-функции на примере алгоритма md4

Хеширование — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest). Если у двух строк хеш-коды разные, строки гарантированно различаются, если одинаковые — строки, вероятно, совпадают.

Хеширование применяется для построения ассоциативных массивов, поиска дубликатов в сериях наборов данных, построения достаточно уникальных идентификаторов для наборов данных, контрольное суммирование с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не само сообщение, а его хеш-образ).

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

Как и другие алгоритмы семейства MD, MD4 разработан Рональдом Ривестом; данный алгоритм был предложен в 1990 г.

Структура алгоритма MD4 полностью соответствует схеме Меркля-Дамгаарда. Данная схема была предложена в 1988-1989 гг. независимо двумя известными криптологами: Ральфом Мерклем и Айвеном Дамгаардом.

Алгоритм MD4 вычисляет 128-битовое хэш-значение от входного блока данных переменного и неограниченного размера.

Прежде всего, входное сообщение разбивается на блоки размером по 512 битов. Последний блок всегда дополняется до 512-битового размера следующим образом:

сначала добавляется единичный бит;

затем – нулевые биты до размера 448 битов (т. е. 512 - 64); нулевые биты не добавляются, если после добавления единичного бита блок имеет 448-битовый размер;

к последовательности добавляется 64-битовое значение, равное размеру в битах исходной последовательности входных данных до дополнения.

В Ривест отметил, что если размер сообщения в битах превышает 264 - 1 (что можно считать крайне маловероятным), то значение размера становится невозможно записать в 64 бита. Поэтому в качестве размера записывается не L, а значение L mod 264.

Если изначально размер последнего блока равен 448 битам (или больше), дополнение выполняется все равно, при этом количество блоков увеличивается на один.

Для хранения промежуточных значений алгоритм использует 4 регистра по 32 бита, которые обозначаются как A, B, C и D. Каждый из 512-битовых блоков входных данных Mi поочередно обрабатывается следующим образом:

Блок входных данных представляется в виде 16 слов M[0]…M[15], каждое из которых является 32-битовым.

Содержимое регистров A…D копируется во временные переменные a…d.

Рис. 2.6 Итерация алгоритма MD4

Выполняются 48 итераций преобразований (см. рис. 2), в каждой из которых модифицируются переменные a…d с участием одного из слов блока сообщения M[0]…M[15]:

t = (a + fj(b, c, d) + M[xj] + Kj mod 232) <<< sj ; (2.6)

a = d;

d = c;

c = b;

b = t,

где:

j – номер итерации, j = 0…47;

t – временная 32-битовая переменная;

fj() – одна из следующих раундовых функций

Kj – модифицирующие константы

<<< – операция побитового циклического сдвига влево; количество битов сдвига sj определяется в зависимости от номера итерации.

Значения регистров A…D складываются по модулю 232 с полученными значениями переменных a…d соответственно.

Выходное значение алгоритма, т. е. 128-битовое хэш-значение сообщения – результат конкатенации регистров A…D после обработки последнего блока расширенного сообщения.

Алгоритм MD4 выглядит не более сложным в реализации, чем алгоритм MD2. В отличие от MD2, MD4 не содержит таблиц замен и может быть весьма компактно реализован аппаратно