Функции хэширования. Требования предъявляемые к функциям хэширования. Ключевые функции хэширования. Безключевые функции хэширования.

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

Функцией хэширования называется функция h, удовлетворяющая минимум двум требованиям:

Сжатие – функция h отображает входное сообщение x (прообраз) произвольной длины в хэш-значение y=h(x) небольшой фиксированной длины.

Простота вычисления – для заданной функции h и сообщения x, h(x) вычисляется не выше чем с полиномиальной сложностью.

Хэш-функции используются при формировании ЭЦП, проверки целостности и организации индексированного поиска данных, в алгоритмах аутентификации (хеширование паролей).

Свойства хэш-функций:

Однонаправленность – вычислительная сложность нахождения неизвестного прообраза для предварительно заданного хэш-значения.

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

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

Свойства 1 и 2 предотвращают воздействия злоумышленника на канал связи (препятствуют подмене, изменению и посылке ложных сообщений злоумышленником от лица отправителя), свойство 3 не допускает ситуацию, когда абонент 1 подбирает абоненту 2 на подпись два договора с одинаковым значением хэш-функции: «нормальный» и «невыгодный» для абонента 2, но выгодный для себя. Абонент 2 подписывает «нормальный» договор, т.о. абонент 1 получает подпись и для «невыгодного» договора.

Алгоритм хеширования должен быть открытым.

Ключевые функции хеширования

В криптографических приложениях к таким функциям предъявляют следующие основные требования:

- невозможность фабрикации (сложность подбора сообщения с правильным значением свертки);

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

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

При вычислении используют секретный ключ, известный отправителю и получателю. Данные функции применяются в ситуациях, когда сто­роны доверяют друг другу. Основная их задача – доказательство того, что сообщение передал человек, знающий секретный ключ, а также что оно не было изменено или подменено при передаче.