Предполагая равномерное распространение в диапазоне хэшей MD5 и SHA-1 для случайных строк (что не так), и предполагая, что мы говорим только о двух строках, а не о пуле строк (поэтому мы избегаем парадокса дня рождения -типные сложности):
Хэш MD5 имеет ширину 128 бит, а SHA-1 - 160. С приведенными выше предположениями две строки A и B имеют вероятность столкновения P, если оба хэша конфликтуют. Так
P(both collide) = P(MD5 collides) * P(SHA-1 collides)
И
P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)
So
P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87
Опять же, если у вас есть пул строк и вы пытаетесь определить вероятности столкновений с пулом, вы находитесь в домене парадокс дня рождения, и эта вероятность, которую я рассчитал здесь, неприменима. Это и хэши не так единообразны, как должны быть. На самом деле у вас будет гораздо более высокая частота столкновений, но она все равно будет крошечной.
ИЗМЕНИТЬ
Поскольку вы имеете дело с парадоксом дня рождения, примените ту же логику, что и решение парадокса дня рождения. Давайте посмотрим на это с точки зрения всего одной хеш-функции:
N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)
Давайте представим, что у нас есть хорошее четное количество хешей, например 2 ^ 29 (примерно 530 миллионов).
P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)
Короче, я даже не хочу думать о вычислении этого числа. Я даже не знаю, как это можно оценить. Вам, по крайней мере, понадобится калькулятор произвольной точности, который может обрабатывать огромные факториалы, не умирая.
Обратите внимание, что вероятности будут следовать кривой, которая начинается почти с 0, когда N = 1 or 2, и достигает 1, когда N >= 2^288, по форме похожая на ту, что на странице Википедии для парадокса дня рождения.
Парадокс дня рождения достигает P = .5, когда N = 23. Другими словами, вероятность столкновения составляет 50%, когда N равно 6% от S. Если это масштабируется (я не уверен, что это так), это означает, что вероятность столкновения будет 50%, когда 6% от 2 ^ 288 хешей. 6% от 2 ^ 288 составляет около 2 ^ 284. Ваше значение N (несколько сотен миллионов) и близко не к этому. Это практически несущественно по сравнению с вашим S, поэтому не думаю, что вам есть о чем беспокоиться. Столкновения маловероятны.
person
Welbog
schedule
24.08.2009
