Усечение хеша md5, Как рассчитать вероятность столкновения?

Я хочу урезать хеш md5 примерно до половины размера. Сколько это увеличивает вероятность столкновений? если я имею дело с около 500 000 поколений, я должен беспокоиться о столкновении? что насчет 1 м поколений.

Ответы

Ответ 1

Математика, которую вы ищете, находится на странице Wikipedia дня рождения.

Рассмотрим следующий эксперимент. Из набора значений H выберем n значений равномерно случайным образом, тем самым допуская повторения. Пусть p (n; H) - вероятность того, что в течение этого эксперимента по меньшей мере одно значение выбрано более одного раза. Эта вероятность может быть аппроксимирована как

p(n;H) ~= 1-e^(-n^2/(2H))

С 128 бит вероятность столкновения между 500 000 хэш-значениями составляет 10 -28. Если вы уменьшите вдвое размер пространства столкновения, вероятность столкновения будет 10 -9. То есть, хотя шанс значительно больше, он все еще очень, очень низок. Это зависит от того, насколько критически важно, чтобы не было столкновений. 10 -9 составляет порядка одного миллиарда, поэтому, в то время как крайне маловероятно, он находится в пределах возможностей.

Для справки:

10 28= 10 octillion = 10 миллиардов миллиардов миллиардов

10 9= 1 млрд.

Ответ 2

Там интересная математическая проблема, называемая проблема дня рождения, которая касается такой ситуации. Дело в том, что чем больше записей вы входите, тем выше вероятность столкновения.

Следуя таблице, указанной в приведенной выше ссылке, если ваши дайджесты имеют 64 бита каждый (поскольку один хэш MD5 составляет 128 бит), и что MD5 имеет равномерное распределение, существует очень низкая вероятность столкновения двух хэшей. Он становится значительным (1% шанс или больше) на 610 000 000 записей.