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

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

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

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

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

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

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

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

Рис. 7.7. Общая схема вычисления однонаправленной хэш-функции

Часто функции хэширования строят используя в качестве однона­правленной функции симметричный блочный алгоритм шифрования (DES, ГОСТ 28147-89) в режиме с обратной связью, принимая последний блок шифротекста за хэш-значение всего документа. Так как длина блока в указанных алгоритмах невелика (64 бита), то часто в качестве хэш-значения используют два блока шифротекста. Одна из возможных схем хэширования на основе блочного алгоритма шифрования изображена на рис. 7.8.

Рис. 7.8. Схема вычисления однонаправленной функции хэширования на базе блочного алгоритма шифрования