Основы современной криптографии

       

Функции хэширования


Функция хэширования 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 является односторонней функцией. Стойкость систем с открытыми ключами зависит от того, что открытое криптопреобразование является односторонней функцией-ловушкой. Напротив, функции хэширования являются односторонними функциями, не имеющими ловушек.



Содержание раздела