Хеш-функции / Алгоритм хэш-функции MD2

Хэширование и эл подпись 2

Request for Comments: 1319 MD2

Тpи алгоpитма сеpии MD pазpаботаны Ривестом в 1989-м, 90-м и 91-м году соответст­венно. Все они пpеобpазуют текст пpоизвольной длины в 128-битный хэш. Алгоритм MD предназначается для использования в ЭЦП для сжатия большого файла перед его под­писью секретным ключом в криптосистеме с ОК, например

Сложность нахождения инверсии, то есть сообщения с тем же дайджестом определя­ется величиной 2¹²⁸ , а коллизии, то есть двух сообщений с одинаковым дайджестом 2⁶⁴.

Предположим, что имеем на входе сообщение длиной b байт.

m₀ m₁ ... m_b-1

Шаг 1. Добавление Padding Bytes

Сообщение расширяется (is "padded") так, чтобы его длина в байтах стала крат­на 16. Расширение выполняется даже, если длина сообщения уже кратна 16. К сообщению добав­ляется "i" bytes (i=1..16) of value "i"

Обозначим результирующее сообщение M₀ ... M_N-1

Шаг 2 Добавление 16 байтной контрольной суммы (Checksum)

При ее вычислении используется 256-байтовую "random" permutation, созданную из цифр числа . Обозначим S[i] - i-тый элемент таблицы

L:= C₀=… =C₁₅:=0 { Обнуляем контрольную сумму}

For i = 0 to N/16-1 do { обрабатываем каждый 16-байтовый блок}

For j = 0 to 15 do {Обрабатываем блок i}

C_j:= S[M_i*16+j  L].

L:= C_j

end

end

Получаем 16-байтовую checksum C₀ ...С₁₅ , добавляемую к сообщению.

Получим сообщение M*₀…M*_N'-1 с добавленной контрольной суммой, где N'=N + 16.

Шаг 3. Инициализация MD Buffer

Для вычисления дайджеста используется 48-байиный буфер X , первоначально об­нуленный

Шаг 4. Обработка сообщения в 16-байтных блоках

For i = 0 to N'/16-1 do {Обработка каждого 16 байтного блока}

For j = 0 to 15 do X_16+j:= M_i*16+j {Копируем блок i в X}

X_32+j:= X_16+j  X_j

end

0 15 16 31 32 47

t:= 0.

For j = 0 to 17 do {делаем 16 проходов}

For k = 0 to 47 do {Проход j]

t, X_k:=X_k  S_t

end

t:= (t+j) mod 256.

end

end

Шаг 5. Вывод

после окончания алгоритма из X₀ ... Х₁₅. берется дайджест сообщения

Т.е. алгоpитм MD2 пpедполагает:

* дополнение текста до длины, кpатной 128 битам;

* вычисление 16-битной контpольной суммы (стаpшие pазpяды отбpасываются);

* добавление контpольной суммы к тексту;

* повтоpное вычисление контpольной суммы.

ПАЗИ Криптография с ОК 15.07.19 2