 |
|
Классификация функций хэширования
Функцией хэширования (в широком смысле) называется функция 
, удовлетворяющая минимум двум требованиям [1]:
1. Сжатие – функция отображает входное сообщение 
произвольной конечной длины в хэш-значение 
небольшой фиксированной длины, при этом входное сообщение будем называть прообразом.
2. Простота вычисления – для заданной функции и сообщения , 
вычисляется не выше чем с полиномиальной сложностью.
Все существующие функции хэширования можно разделить на два больших класса: бесключевые хэш-функции, зависящие только от сообщения, и хэш-функции с секретным ключом, зависящие как от сообщения, так и от секретного ключа.
Подклассом бесключевых хэш-функций являются коды обнаружения изменений (modification detection codes, MDC-коды). В криптографии применяются специфические подклассы MDC-кодов, являющиеся однонаправленными и бесколлизионными хэш-функциями, которые получили широкое распространение в системах цифровой подписи.
Функции выработки кодов аутентификации сообщений (КАС) являются подклассом ключевых хэш-функций и обладают дополнительным свойством вычислительной стойкости.
По используемым внутренним преобразованиям функции хэширования можно разделить на:
функции, использующие битовые логические преобразования. Эти функции применяют к входному сообщению побитовые нелинейные операции “И”, “ИЛИ”, “НЕ”, “ИСКЛЮЧАЮЩЕЕ ИЛИ”, различные сдвиги и, как правило, являются многоцикловыми;
функции, использующие блочные симметричные шифры. Используются в основном для реализации функций выработки КАС;
функции, использующие преобразования в группах, полях и кольцах с целочисленным или полиномиальным базисом;
функции, использующие матричные преобразования.