Интернет магазин китайских планшетных компьютеров

Компьютеры - Коллизия хеш-функции

Коллизией хеш-функции H называется два различных входных блока данных x и y таких, что H = H.

Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму. В некоторых частных случаях, когда множество различных входных данных конечно, можно задать инъективную хеш-функцию, по определению не имеющую коллизий. Однако для хеш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины, коллизии обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных будет бесконечно — и любые два набора данных из этого множества образуют коллизию.

Пример

Рассмотрим в качестве примера хеш-функцию H = xmod 19, определенную на множестве целых чисел. Её область значений состоит из 19 элементов, а область определения — бесконечна. Так как множество прообразов заведомо больше множества значений, коллизии обязаны существовать.

Построим коллизию для этой хеш-функции для входного значения 38, хеш-сумма которого равна нулю. Так как функция H — периодическая с периодом 19, то для любого входного значения y, значение y+19 будет иметь ту же хеш-сумму, что и y. В частности, для входного значения 38 той же хеш-суммой будут обладать входные значения 57, 76, и т. д. Таким образом, пары входных значений, образуют коллизии хеш-функции H.