Какова вероятность столкновения md5, если я перехожу в 2 ^ 32 набора строк?
Могу ли я сказать, что ответ равен 2 ^ 32/2 ^ 128 = 1/1.2621774e-29, поскольку длина бит хэша md5 равна 128?
Какова вероятность столкновения md5, если я перехожу в 2 ^ 32 набора строк?
Ответ 1
Этот вопрос похож на так называемый "парадокс дня рождения" .
В теории вероятностей день рождения или парадоксальный день рождения относится к вероятности того, что в наборе из n случайно выбранных людей некоторые пары из них будут иметь тот же день рождения, По принципу голубины вероятность достигает 100%, когда число людей достигает 367 (так как 366 возможных дней рождения, включая 29 февраля). Однако вероятность 99% достигается всего 57 человек, а вероятность 50% - у 23 человек. Эти выводы основаны на предположении, что каждый день года (кроме 29 февраля) одинаково вероятен для дня рождения.
Математика, лежащая в основе этой проблемы, привела к известной криптографической атаке, названной атакой дня рождения, которая использует эту вероятностную модель для уменьшения сложности взломать хэш-функцию.
Согласно статье Википедии, вероятность столкновения при выборе n= 2 32 случайных чисел из пространства с d= 2 128 приблизительно:
Если вы работаете с этим вычислением, вероятность составляет около 2,7 × 10 -20. Это очень небольшая вероятность, но обратите внимание, что она на 9 порядков выше, чем ваш предлагаемый расчет.