5.1 Введение

Хэш-функции являются необходимым элементом ряда криптографических схем. Под этим термином понимаются функции, отображающие сообщения произвольной длины (иногда длина сообщения ограничена, но достаточно большим числом) в значения фиксированной длины. Последние часто называют хэш-кодами. Таким образом, у всякой хэш-функции имеется большое количество коллизий, т. е. пар значений таких, что . Основное требование, предъявляемое криптографическими приложениями к хэш-функциям, состоит в отсутствии эффективных алгоритмов поиска коллизий.

Схемы электронной подписи -- основная сфера применения хэш-функций в криптографии. Поскольку используемые на практике схемы электронной подписи не приспособлены для подписания сообщений произвольной длины, а процедура, состоящая в разбиении сообщения на блоки и в генерации подписи для каждого блока по отдельности, крайне неэффективна, единственным разумным решением представляется применение схемы подписи к хэш-коду сообщения. Нетрудно понять, что наличие эффективных методов поиска коллизий для хэш-функции подрывает стойкость протокола электронной подписи. Хэш-функции используются также в некоторых протоколах аутентификации для снижения их коммуникационной сложности, т. е. для уменьшения длин пересылаемых сообщений (см. главу 3), и в некоторых других криптографических протоколах (см., например, главу 8).

В разделе 5.2 рассматриваются методы построения криптографических хэш-функций. Приводятся некоторые известные конструкции и, в ряде случаев, результаты анализа. В разделе 5.3 обсуждаются вопросы эффективности хэш-функций. Некоторые методы криптоанализа хэш-функций, не вошедшие в раздел 5.2, приводятся в разделе 5.4. Заключительный раздел 5.5 посвящен теоретическим аспектам.