Хэширующая функция это многозначная функция H, ставящая в соответствие своему аргументу M произвольной длины значение h=H(M) фиксированной длины. Простая хэширующая функция - f(x) = 0 для всех целых x. Более интересна функция f(x) = x mod 37, которая отображает x в остаток от деления x на 37. Хэш-функции используемые в криптографических приложениях обладают следующими свойствами:
Хэш-значение сообщения может использоваться в качестве его уникального идентификатора. Если сообщение изменить, то изменится и хэш-значение. Найти другое сообщение с точно таким же хэш-значением практически невозможно. Благодаря этому свойству хэш-функции можно использовать для проверки целостности документов и для цифровой подписи. Предположим, что Алиса отправила Бобу некоторое сообщение, и хочет быть уверена, что никто посторонний не изменит сообщение по пути к Бобу. Алиса может вычислить значение хэш-функции для сообщения и передать это значение Бобу некоторым защищённым образом (например по телефону). Боб, приняв сообщение, может вычислить его хэш-значение и сравнить с тем, которое передала Алиса. Если значения совпадут, то сообщение дошло без изменений, в противном случае сообщение было повреждено. Очевидно, что наиболее важным параметром хэш-функции является длина возвращаемого ею значения. Если эта длина n бит, то для того, чтобы найти сообщение M', имеющее такое же хэш-значение, как и M, придётся перебрать в среднем 2n-1 различных сообщений.
Свойство сильной устойчивости к коллизиям так же является очень важным. Предположим, что Чарли хочет, чтобы Алиса подписала некоторый документ, но он знает, что Алиса его ни за что не подпишет. Чарли может создать другой документ, который Алиса согласится подписать, а затем, внося случайные изменения в оба документа (например, добавляя пробелы в разных местах текста) он может найти пару разных документов с одинаковым хэш-значением перебрав всего 2n/2 вариантов[4]. После этого Чарли даёт Алисе на подпись вариант хорошего документа, а затем прилагает полученную подпись к варианту плохого документа с тем же хэш-значением.
[4] Это явление называется парадоксом дней рождений. Если Вы хотите, чтобы с вероятностью 1/2 у одного из пришедших к Вам гостей день рождения совпадал с Вашим, то придётся пригласить 253 человека. Если же Вы хотите, чтобы с вероятностью 1/2 день рождения совпадал у любых двух гостей, то достаточно пригласить только 23 человека.