Криптографические хеш-функции должны соответствовать следующим строгим требованиям:
- Сопротивление поиску прообраза (слабо устойчивость к обращению): Дан по хешу H, должна быть ничтожно малая вероятность найти сообщение M такое, что H(M) = H.
- Сопротивление поиску второго прообраза (сильная устойчивость к обращению): Дан M, должна быть ничтожно малая вероятность найти другое сообщение M’ (не равное M) такое, что H(M’) = H(M).
- Сопротивление коллизиям: Должна быть ничтожно малая вероятность найти любые два различных сообщения M и M’, таких что H(M) = H(M’).
Помимо этих основных требований, криптографические хеш-функции должны обладать следующими желательными свойствами:
- Определенность: Хеш-функция должна всегда возвращать один и тот же хеш для данного сообщения.
- Эффективность: Хеш-функция должна быть вычислительно быстрой.
- Устойчивость к атакам на длину: Хеш-функция должна оставаться безопасной даже при увеличении длины сообщения.
Как вычислить хэш функцию?
Вычисление Хеш-Функций
Хеш-функции используются для создания компактных и уникальных представлений данных, известных как хеш-коды. Распространенным методом вычисления хеш-кода из строки S является использование полиномиальной хеширования:
h(S) = S[0] + S[1] * P + S[2] * P^2 + S[3] * P^3 + … + S[N] * P^N
- где:
- P — некоторое простое число, например, 31
- S[i] — i-й символ в строке S
- N — длина строки S
В этом методе корни символов (S[0], S[1], …, S[N]) последовательно умножаются на степени простого числа P, а затем эти произведения суммируются для получения хеш-кода.
Преимущества Использования Простых Чисел
Использование простого числа в качестве P помогает снизить вероятность коллизий (когда разные строки дают одинаковый хеш-код). Простые числа имеют ограниченное количество делителей, что делает менее возможным найти две строки, которые дают одинаковый хеш-код.
Дополнительные Интересные Факты
- Полиномиальное хеширование используется в алгоритмах поиска подстрок, таких как алгоритм Кнута-Морриса-Пратта.
- Хеш-функции широко применяются в криптографии, например, в алгоритмах цифровой подписи и протоколах проверки подлинности.
- Метод полиномиального хеширования легко реализуется и имеет низкую вычислительную сложность.