Расчет хеш-коллизий с 160 битами

Question

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

Спасибо за помощь:)

Answer 1

Практическое правило заключается в том, что после столкновения чисел sqrt(n) вероятность столкновения составляет 50%. Число немного больше, но квадратный корень является хорошим ориентиром. Так что в вашем случае вероятность столкновения составляет 50% после 2 ^ 80 попыток.

Другое эмпирическое правило заключается в том, что после 4*sqrt(n) вероятность получения дубликата практически равна вероятности.

В соответствии с https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem, вы можете вычислить число n значений, которое вам нужно нарисовать, чтобы получить вероятность p дубликата:

n = sqrt(2 * d * ln(1/(1-p)))

Где ln - натуральный логарифм, а p - вероятность от 0 до 1,0.

Итак, в вашем случае:

n = sqrt(2 * 2^160 * ln(1/.25))
n = sqrt(2^161 * 1.38629)

Что меньше 2 ^ 81.

Answer 2

Где-то в диапазоне 2 septillion. Это 2 000 000 000 000 000 000 000 000 сообщений. Вот уравнение.

chance of collision = 1 - e^(-n^2 / (2 * d))

Где n - количество сообщений, d - количество возможностей. Так что если d равно 2^160, то n будет в окрестности 2^80.7.