Как рассчитать вероятность столкновения с помощью md5?

Question

У меня есть ключи, длина которых может варьироваться от 1 до 256 символов *; Как я могу рассчитать вероятность того, что любые два ключа столкнутся при использовании md5 (за исключением грубого решения каждой клавиши)?

* набор символов ограничен [a-z.-]

Answer 1

Взгляните на парадокс дня рождения , который поможет вам проанализировать это. Короче говоря, поскольку MD5 является 128-битным хешем, вам нужно 2 ⁶⁴ элементов, прежде чем вероятность столкновения возрастет до 50%. Там есть предположение, что MD5 распределяется равномерно по этому 128-битному пространству, что, как я полагаю, не подходит, но приближается.

Если вы хотите получить представление о том, как эти числа соотносятся с вашим пространством для ключей, давайте предположим, что все ваши ключи состоят из 256 символов, у вас есть 26 ²⁵⁶ возможных ключей или 2 ¹⁰²³ , и, конечно, у вас есть 100% шанс столкновения после 2 ¹²⁸ ключей:)

Answer 2

Проверьте день рождения . Это именно то, что вы ищете.