Войти
В криптографии, Устойчивость к коллизиям - это свойство криптографических хэш-функций : хеш-функция H устойчива к коллизиям, если трудно найти два входа, которые хешируют один и тот же выход; то есть два входа a и b, где a ≠ b, но H (a) = H (b). Принцип означает, что любая хеш-функция с большим количеством входов, чем выходов, обязательно будет иметь такие коллизии; чем сложнее их найти, тем более криптографически безопасна хеш-функция.
«парадокс дня рождения » устанавливает верхнюю границу сопротивления столкновениям: если хеш-функция производит N битов вывода, злоумышленник, который вычисляет только 2 (или 
Криптографические хеш-функции обычно предназначены для защиты от коллизий. Однако многие хеш-функции, которые когда-то считались устойчивыми к столкновениям, позже были сломаны. В частности, MD5 и SHA-1 опубликовали методы, более эффективные, чем грубая сила для обнаружения коллизий. Однако у некоторых хэш-функций есть доказательство того, что обнаружение коллизий по крайней мере так же сложно, как и сложная математическая задача (например, целочисленная факторизация или дискретный логарифм ). Эти функции называются доказуемо защищенными.
Семейство функций {h k : {0, 1} → {0, 1}}, сгенерированный некоторым алгоритмом G, является семейством устойчивых к коллизиям хэш-функций, если | m (k) |>| l (k) | для любого k, т. е. h k сжимает входную строку, и каждый h k может быть вычислен за полиномиальное время, заданное k, но для любого вероятностного полиномиального алгоритма A мы имеем
где пренебрежение (·) обозначает некоторую незначительную функцию, а n - параметр безопасности.
Устойчивость к столкновениям желательна по нескольким причинам.
