Однонаправленные хэш-функции. Однонаправленная функция ЩМ) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h

Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у однонаправленных хэш-функций есть дополнительные свойства, делающие их однонаправленными [1065]:

Зная М, легко вычислить h.

Зная Я, трудно определить М, для которого H(M)=h.

Зная М, трудно определить другое сообщение, М', для которого ЩМ)= ЩМ').

Если бы Мэллори умел делать трудные вещи, он смог бы разрушить безопасность любого протокола, и с-пользующего однонаправленную хэш-функцию. Смысл однонаправленных хэш-функций и состоит в обеспече­нии для М уникального идентификатора ("отпечатка пальца"). Если Алиса подписала М с помощью алгоритма цифровой подписи на базе ЩМ), а Боб может создать М', другое сообщение, отличное от М, для которого ЩМ)= ЩМ'), то Боб сможет утверждать, что Алиса подписала М'.

В некоторых приложениях однонаправленности недостаточно, необходимо выполнение другого требования, называемого устойчивостью к столкновениям.

Должно быть трудно найти два случайных сообщения, М и М', для которых ЩМ)= ЩМ').

Помните вскрытие методом дня рождения из раздела 7.4? Оно основано не на поиске другого сообщения М', для которого ЩМ)= ЩМ'), а на поиске двух случайных сообщений ,МиМ', для которых ЩМ)= ЩМ').

Следующий протокол, впервые описанный Гидеоном Ювалом (Gideon Yuval) [1635], показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обм а-на Боба.

(1) Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству

(2) Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хэш-функции. (Этими изменениями могут быть действия, подобные следующим: замена ПРОБЕЛА комбинацией ПРО­БЕЛ-ЗАБОЙ-ПРОБЕЛ, вставка одного-двух пробелов перед возвратом каретки, и т.д. Делая или не делая по одному изменению в каждой из 32 строк, Алиса может легко получить 2 ³² различных документов.)

(3) Алиса сравнивает хэш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. (Если выходом хэш-функции является всего лишь 64-разрядное зн а-чение, Алиса, как правило, сможет найти совпадающую пару сравнив 2 ³² версий каждого документа.) Она восстанавливает два документа, дающих одинаковое хэш-значение.

(4) Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только хэш-значение.