MD4
Оглавление
Описание
Алгоритм
Пример
MD4 (Message Digest 4) — хеш-функция, разработанная профессором Массачусетского университета Рональдом
Ривестом в 1990 году, и впервые описанная в RFC 1186.
Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения.
Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для
выполнения процедур проверкиподлинности удаленных рабочих станций Windows. Является предшественником MD5.
Одна операция MD4. Хеширование с MD4 сотоит из 48 таких операций,
сгруппированных в 3 раунда по 16 операций.
F — нелинейная функция;в каждом раунде функция меняется.
Mi означает 32-битный блок входного сообщения,
а Ki — 32-битная константа, различная для каждой операции.
Алгоритм MD4
Предполагается, что на вход подано сообщение, состоящее из b бит, хеш которого нам предстоит вычислить.
Здесь b — произвольное неотрицательное целое число; оно может быть нулем, не обязано быть кратным восьми,
и может быть сколь угодно большим.
Запишем сообщение побитово, в виде:
Ниже приведены 5 шагов, используемые для вычисления хеша сообщения.
Шаг 1. Добавление недостающих битов.
Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в
результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится
всегда, даже если сообщение изначально имеет нужную длину.
Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются
биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению
добавляется как минимум 1 бит, и как максимум 512
Шаг 2. Добавление длины сообщения.
64-битное представление b (длины сообщения перед добавлением набивочных битов) добавляется к результату
предыдущего шага. В маловероятном случае, когда b больше, чем 2 в степени 64, используются только 64 младших бита.
Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды.
На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной кратной 512 битам.
Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Пусть M[0...N-1] означает
массив слов получившегося сообщения (здесь N кратно 16).
Шаг 3. Инициализация MD-буфера.
Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (A,B,C,D)(32-битных регистров): . Эти регистры
инициализируются следующими шестнадцатеричными числами (младшие байты сначала):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Шаг 4. Обработка сообщения блоками по 16 слов.
Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова,
и по ним вычисляет одно 32-битное слово.
На каждую битовую позицию F действует как условное выражение: если X, то Y; иначе Z. Функция F могла бы быть
определена с использованием вместо V, поскольку XY и _XZ не могут равняться 1 одновременно. G действует на каждую
битовую позицию как функция максимального значения: если по крайней мере в двух словах из X,Y,Z соответствующие
биты равны 1, то G выдаст 1 в этом бите, а иначе G выдаст бит, равный 0. Интересно отметить, что если биты X, Y
и Z статистически независимы, то биты F(X,Y,Z) и G(X,Y,Z) будут также статистически независимы. Функция H
реализует побитовый xor, она обладает таким же свойством, как F и G.
Шаг 5. Формирование хеша.
Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и
заканчивая старшим битом D.
Пример
MD4("The quick brown fox jumps over the lazy dog")
= 1bee69a46ba811185c194762abaeae90
128-битные MD4 хеши представляют собой 32-х значное число в 16-ричном формате. В следующем примере показан хеш 43-байтной строки ASCII
Виды
MD6
MD4
MD5
SECURE HASH ALGORITHM (SHA)
RIPE-MD
HAVAL
MDC
|
