Я ищу точную математику вероятности коллизий для MD5, SHA1 и SHA256 на основе парадокса дня рождения.
Я ищу что-то вроде графика, который говорит, что у вас есть 10 ^ 8 ключей, это вероятность. Если у вас 10 ^ 13 ключей, это вероятность и т. Д.
Я просмотрел множество статей, но мне трудно найти что-то, что дает мне эти данные. (Идеальным вариантом для меня была бы формула или код, который вычисляет это для любого предоставленного размера хэша)
Представим, что у нас есть действительно случайная хеш-функция, которая преобразует строки в n-битные числа. Это означает, что существует 2 n возможных хэш-кодов, и хэш-код каждой строки выбирается равномерно случайным образом из всех этих возможностей.
Парадокс дня рождения, в частности, гласит, что если вы видели примерно √ (2k) элементов, вероятность столкновения составляет 50%, где k - количество различных возможных выходов. В случае, когда хеш-функция выводит n-битный вывод, это означает, что вам понадобится примерно 2 хэша n / 2, прежде чем вы получите коллизию. Вот почему мы обычно выбираем хэши, которые выводят 256 бит; это означает, что нам потребовалось бы хешировать 2 128 ≈10 38 элементов, прежде чем возникнет разумная вероятность столкновения. С 512-битным хешем вам понадобится около 2 256, чтобы получить 50% вероятность столкновения, а 2 256 - это приблизительное количество протонов в известной вселенной.
Точная формула для вероятности столкновения с n-битной хеш-функцией и хешированием k строк:
1-2 n! / (2 kn (2 n - k)!)
Непосредственно работать с этой величиной довольно сложно, но мы можем получить приличное приближение к этой величине, используя выражение
1 - e -k 2 / 2 n + 1
Итак, чтобы получить (примерно) вероятность p шанс столкновения, мы можем решить, чтобы получить
p ≈ 1 - e -k 2 / 2 n + 1
1 - p ≈ e -k 2 / 2 n + 1
ln (1 - p) ≈ -k 2 / 2 n + 1
-ln (1 - p) ≈ k 2 / 2 n + 1
-2 n + 1 ln (1 - p) ≈ k 2
2 (n + 1) / 2 √ (-ln (1 - p)) ≈ k
В качестве последнего приближения предположим, что мы имеем дело с очень выбором p. Тогда ln (1 - p) ≈ -p, поэтому мы можем переписать это как
k ≈ 2 (n + 1) / 2 √p
Обратите внимание, что здесь все еще есть термин-монстр 2 (n + 1) / 2, поэтому для 256-битного хеша ведущий член равен 2 128,5, что просто огромно. Например, сколько элементов мы должны увидеть, чтобы с вероятностью 2 -50 столкнуться с 256-битным хешем? Это было бы примерно
2 (256 + 1) / 2 √2 -50
= 2 257/2 2 -50/2
= 2 207/2
= 2 153,5.
Таким образом, вам понадобится ошеломляюще огромное количество хешей, чтобы иметь исчезающе шанс столкновения. Представьте, что 2 153,5 составляет примерно 10 45, что при вычислении одной наносекунды на один хэш потребует больше времени, чем вычисление длины вселенной. И после всего этого вы получите вероятность успеха 2 -50, что примерно равно 10 -15.
Собственно, именно поэтому мы выбираем такое большое количество бит для наших хэшей! Это делает крайне маловероятным случайное столкновение.
(Обратите внимание, что хэш-функции, которые у нас есть сегодня, на самом деле не являются действительно случайными, поэтому люди советуют не использовать MD5, SHA1 и другие, у которых обнаружены слабые места в безопасности.)
Надеюсь это поможет!
