ТребованияДля того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии: § Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m должно быть вычислительно невозможно найти блок данных X, для которого H (X) = m. § Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого H (N) = H (M). § Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений Данные требования не являются независимыми: § Обратимая функция нестойка к коллизиям первого и второго рода. § Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно. Следует отметить, что не доказано существование необратимых хеш-функций, для которых вычисление какого-либо прообраза заданного значения хеш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей. Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n битов в среднем за примерно 2 n / 2 вычислений хеш-функции. Поэтому n -битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2 n / 2. Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект). В частности, значение хеша не должно давать утечки информации даже об отдельных битах аргумента. Это требование является залогом криптостойкости алгоритмов хеширования пользовательских паролей для получения ключей.
|
, имеющих одинаковый хеш.
