Коллизия хеш-функции

---

Колли́зия хеш-фу́нкции — два различных входных блока данных ${\displaystyle x}$ и ${\displaystyle y}$ для хеш-функции ${\displaystyle H}$ таких, что ${\displaystyle H(x)=H(y).}$

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

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

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

---