5.2 Методы построения криптографических хэш-функций

В ряде криптографических приложений, особенно в схемах электронной цифровой подписи, необходимым элементом является криптографически стойкая хэш-функция [Si], [DP], [Schndr], [Ro], [NY]. Под этим термином обычно понимается функция , отображающая сообщения произвольной длины в хэш-код фиксированной длины. При этом предполагается, что либо не существует эффективного алгоритма для нахождения такой пары сообщений , что (хэш-функция стойкая в сильном смысле), либо не существует эффективного алгоритма для нахождения при заданном такого , что (хэш-функция стойкая в слабом смысле) [PS], [Da].

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

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

Практические методы построения хэш-функций можно условно разделить на три группы [Pr], [PS]: методы построения хэш-функций на основе какого-либо алгоритма шифрования (предполагается, что шифратор стойкий [Wi], [PrBGV], [LaM]), методы построения хэш-функций на основе какой-либо известной вычислительно трудной математической задачи [AMOV] и методы построения хэш-функций "с нуля" [Me], [MMO], [StM].

Известна попытка использовать быстрое преобразование Фурье для построения хэш-алгоритма [BGG], [DBGV], [Schnrr1], [Schnrr2]. Все предложенные варианты такой функции оказались нестойкими [Va]. Попытки построить хэш-функции на основе вычислительно трудных задач мы в данном разделе не рассматриваем.

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

• 5.2.1 N-хэш
• 5.2.2 MD4
• 5.2.3 MD5
• 5.2.4 SECURE HASH ALGORITHM (SHA)
• 5.2.5 RIPE-MD
• 5.2.6 HAVAL
• 5.2.7 Схемы хэширования, использующие алгоритмы блочного шифрования
• 5.2.8 MDC