Однонаправленные хэш-функции

Обычно на практике хэш-функция сжимает подписываемый документ M до нескольких десятков или сотен бит. Хэш-функция Н(·) принимает в качестве аргумента сообщение (документ) M произвольной длины и возвращает хэш-значение H(M)=z фиксированной длины. Как было отмечено ране хэшированная информация является сжатым двоичным представлением основного сообщения произвольной длины. Напомним, что значение хэш-функции H(M) сложным образом зависит от документа M и не позволяет восстановить сам документ M.

Хэш-функция должна удовлетворять целому ряду условий:

· хэш-функция должна быть чувствительна к всевозможным изменениям в тексте M, таким как вставки, выбросы, перестановки и т.п.;

· хэш-функция должна обладать свойством необратимости, то есть задача подбора документа M', который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;

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

Большинство хэш-функций строится на основе однонаправленной функции f(·), которая образует выходное значение длиной n при задании двух входных значений длиной n. Этими входами являются блок исходного текста M_i и хэш-значение R_i–1 предыдущего блока текста:

R_i = f (M_i, R_i–1).

Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения M.

Построение однонаправленной хэш-функции

В результате однонаправленная хэш-функция всегда формирует выход фиксированной длины n (независимо от длины входного текста).

Однонаправленные хэш-функции на основе симметричных блочных алгоритмов. Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение M посредством блочного алгоритма в специальных режимах CBC – сцепление блоков щифра или CFB – обратная связь по шифртексту с помощью фиксированного ключа и некоторого вектора инициализации. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения M. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообщения MAC (Message Authentication Code).

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

Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые схемы хэширования проектируют так, чтобы хэш-значение имело длину, равную двойной длине блока.

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

Обобщенная схема формирования хэш-функции

Ее работа описывается выражениями:

R₀ = I_R,

R_i = E_A(B) Å C,

где I_R – некоторое случайное начальное значение; A, B и C могут принимать значения M_i, R_i–1, (M_i Å R_i–1) или быть константами, E_A – функция шифрования на ключе A.