Вероятность хеш-столкновения
Извиняюсь, если это дублирующий вопрос; большинство из тех, что я нашел, у меня над головой, так что, возможно, я пропустил ответ.
Для данного хеша, скажем, MD5 (128 бит), какова вероятность столкновения хеша с 10^12 из них?
Моя математика не очень хорошая, я придумал это уравнение (я думаю, что оно правильное), но не знаю, как его решить:
Collision_Chance = 1 - (1 - (1/2 ^ 128)) ^ (10^12)
Я предполагаю, что это где-то около 10^-26, это звучит примерно так?
Спасибо
Изменить: я думаю, что моя оценка очень неправильно. Смотрите парадокс дня рождения
2 ответа
Что ваша формула говорит о наличии 2^128 + 1 значений? Я считаю, что это не говорит о том, что вероятность столкновения равна 1, поэтому она не может быть правильной. на самом деле, я знаю, что это не так - правильная формула довольно большая и громоздкая, но есть хорошие приближения, использующие экспоненту дроби. SO не набирает формулы, поэтому я не буду пытаться писать формулы здесь.
Лучшее ключевое слово для поиска - " атака на день рождения".
Почему коллизия хешей будет проблемой? Хэши никогда не предназначены для генерации уникальных значений, только для быстрого первого сравнения.
Если у вас возникли проблемы с хеш-коллизиями, вы используете это неправильно.