Структура Меркля-Дамгарда

From CryptoWiki
Revision as of 20:51, 22 December 2013 by 13-03-DushaIF (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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