Интернет магазин китайских планшетных компьютеров

Компьютеры - Структура МерклаДамгарда

Структура Меркла-Дамгарда — метод построения криптографических хеш-функций. Криптографическая хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное сообщение фиксированной длины. Этого можно достичь путём разбиения входного сообщение на блоки одинакового размера и их последовательной обработки односторонней функцией сжатия, которая преобразовывает входное сообщение фиксированной длины в более короткое выходное сообщение фиксированной длины. Функция сжатия либо может быть специально построена для хеширования либо может представлять собой функцию блочного шифрования. Хеш-функция Меркла-Дамгарда разбивает входное сообщение на блоки и работает с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего раунда.

Структура Меркла-Дамгарда была описана в докторской диссертации Ральфа Меркла. Ральф Меркл и Иван Дамгор независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива. Чтобы доказать устойчивость структуры, Меркл и Дамгор предложили дополнить сообщение блоком, который кодирует длину первоначального сообщения. Это называется упрочнение Меркла-Дамгарда.

Merkle-Damgård hash construction

На рисунке односторонняя функция сжатия обозначена f, и преобразует два входных блока фиксированной длины в выходной блок того же размера, что и входные. Алгоритм начинает с начального значения — вектора инициализации. Вектор инициализации — фиксированное значение. Для каждого блока сообщения, функция сжатия f принимает результат предыдущего раунда и блок сообщения, и производит промежуточный результат. Последний блок дополняется нулями, если необходимо. Также, добавляется блок с информацией о длине целого сообщения.

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