Вероятность столкновений SHA1

Question

Учитывая набор из 100 различных строк равной длины, как вы можете количественно оценить вероятность того, что столкновение SHA1 для строк вряд ли возможно??

Answer 1

ли 160 бит хэш-значения генерируется по SHA-1 достаточно большой, чтобы обеспечить отпечатков пальцев каждого блока является уникальным? Предполагая, что случайные значения хэш-функции с распределением равномерной, коллекция п различных блоков данных и хеш- функция, которая генерирует б битов, то вероятность р, что будет один или более столкновений ограничена числом пар блоков умножается на на вероятность столкновения данной пары .

(источник: http://bitcache.org/faq/hash-collision-probabilities)

Answer 2

Это Birthday Problem - статья дает приятные аппроксимации, которые позволяют легко оценить вероятность. Фактическая вероятность будет очень очень низкой - см. Пример this question.

Answer 3

Хорошо, вероятность столкновения будет равна 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * ((2^160 - 99)/2^160).

Подумайте о вероятности столкновения 2 предметов в пространстве 10. Первый элемент уникален с вероятностью 100%. Вторая уникальна с вероятностью 9/10. Таким образом, вероятность того, что оба уникальны, составляет 100% * 90%, а вероятность столкновения равна 1 - (100% * 90%) или 1 - ((10 - 0)/10) * ((10 - 1)/10), или 1 - ((10 - 1)/10).

Это маловероятно. У вас должно быть много строк, чтобы это была отдаленная возможность.

Посмотрите на таблицу на this page on Wikipedia; просто интерполировать между строками для 128 бит и 256 бит.