Функция хеширования (хеш-функция) Н представляет собой отображение, на вход которого подастся сообщение переменной длины М, а выходом является строка фиксированной длины Н (М). В общем случае Н (М) будет гораздо меньшим, чем М, например, Н (М) может быть 128 или 256 бит, тогда как М может быть размером в мегабайт или более.
Функция хеширования может служить для обнаружения модификации сообщения, т. е. она может служить в качестве криптографической контрольной суммы (также называемой кодом обнаружения изменений (MDC — Manipulation Detection Code) или проверкой целостности сообщения (MIC — Message Integrity Check)).
Теоретически возможно, что два различных сообщения могут быть сжаты в одну и ту же свертку (так называемая ситуация «столкновения»).
Поэтому для обеспечения стойкости функции хеширования необходимо предусмотреть способ избегать столкновений. Полностью столкновений избежать нельзя, поскольку в общем случае количество возможных сообщений превышает количество возможных выходных значений функции хеширования. Однако вероятность столкновения должна быть низкой.
Для того чтобы функция хеширования могла должным образом быть использована в процессе аутентификации, функция хеширования Н должна обладать следующими свойствами:
- 1. Н может быть применена к аргументу любого размера.
- 2. Выходное значение Н имеет фиксированный размер.
- 3. Н (х) достаточно просто вычислить для любого х. Скорость вычисления хеш-функции должна быть такой, чтобы скорость выработки и проверки ЭЦП при использовании хеш-функции была значительно больше, чем при использовании самого сообщения.
- 4. Для любого у с вычислительной точки зрения невозможно найти х такое, что Н (х) = у.
- 5. Для любого фиксированного х с вычислительной точки зрения невозможно найти х' Ф х такое, что Н (х') = Н (х).
Последнее свойство гарантирует отсутствие другого сообщения, дающего ту же свертку, что предотвращает подделку и позволяет использовать Н в качестве криптографической контрольной суммы для проверки целостности.
Четвертое свойство эквивалентно тому, что Н является односторонней функцией. Стойкость систем с открытыми ключами зависит от того, что открытое криптопреобразование является односторонней функциейловушкой. Напротив, функции хеширования являются односторонними функциями, нс имеющими ловушек. Классическая хеш-функция является открытым преобразованием. В случае, когда она зависит от ключа, результат се вычисления носит название кода аутентификации сообщения (MAC — Message Authentication Code).
