Содержание

Меню


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

  • Основы криптографии
    Шифры
    Цифровые подписи
    Хеш-функции
    Криптоанализ
    Дополнительный материал
    MKZT© 2009 год
    Hosted by uCoz