Функции хэширования
Функция хэширования H представляет собой отображение, на вход которого подается сообщение переменной длины M, а выходом является строка фиксированной длины H(M). В общем случае H(M) будет гораздо меньшим, чем M, например, H(M) может быть 128 или 256 бит, тогда как M может быть размером в мегабайт или более.
Функция хэширования может служить для обнаружения модификации сообщения. То есть, она может служить в качестве криптографической контрольной суммы (также называемой кодом обнаружения изменений или кодом аутентификации сообщения).
Теоретически возможно, что два различных сообщения могут быть сжаты в одну и ту же свертку (так называемая ситуация "столкновения"). Поэтому для обеспечения стойкости функции хэширования необходимо предусмотреть способ избегать столкновений. Полностью столкновений избежать нельзя, поскольку в общем случае количество возможных сообщений превышает количество возможных выходных значений функции хэширования. Однако, вероятность столкновения должна быть низкой.
Для того, чтобы функция хэширования могла должным образом быть использована в процессе аутентификации, функция хэширования H
должна обладать следующими свойствами:
1. H может быть применена к аргументу любого размера;
2. Выходное значение H имеет фиксированный размер;
3. H(x) достаточно просто вычислить для любого x. Скорость вычисления хэш-функции должна быть такой, чтобы скорость выработки и проверки ЭЦП при использовании хэш-функции была значительно больше, чем при использовании самого сообщения;
4. Для любого y с вычислительной точки зрения невозможно найти x, такое что H(x)=y.
5. Для любого фиксированного x с вычислительной точки зрения невозможно найти x' № x, такое что H(x')=H(x).
Свойство 5 гарантирует, что не может быть найдено другое сообщение, дающее ту же свертку. Это предотвращает подделку и также позволяет использовать H в качестве криптографической контрольной суммы для проверки целостности.
Свойство 4 эквивалентно тому, что H является односторонней функцией. Стойкость систем с открытыми ключами зависит от того, что открытое криптопреобразование является односторонней функцией-ловушкой. Напротив, функции хэширования являются односторонними функциями, не имеющими ловушек.
