Шанс столкновения хешей

Извините, если это дублирующийся вопрос; большинство из тех, что я нашел, над моей головой, поэтому я, возможно, пропустил ответ.Шанс столкновения хешей

Для данного хэша, скажем MD5 (128 бит), какова вероятность столкновения хэшей с 10^12 из них?

Моей математика не большой, я придумал с этим уравнением (я думаю, что это правильно), но не имею ни малейшего представления о том, как решить эту проблему:

Collision_Chance = 1 - (1 - (1/2^128))^(10^12)

Я предполагаю, что это где-то около 10^-26, звучит ли это правильно?

Благодаря

Edit: Я думаю, что моя оценка очень неправильно. См. Birthday Paradox

источник

2014-01-11 Jodes

«Парадокс дня рождения» - это термин google. И шанс на SQRT (n), в вашем случае 128 бит - >> 64 бит. А 10^12 - менее 64 бит. – wildplasser

@wildplasser «Шанс о SQRT (n)» - что это значит? Шанс должен быть числом от 0 до 1. sqrt (n) - это число значений, для которых вероятность столкновения равна 1/2. –

Небрежная формулировка. Если у вас есть пространство ключей из 128 бит, и вы произвольно выбираете из этого, вероятность столкновения (в кумулятивной выборке) проходит предел .5, когда у вас есть около 2^64 элементов в вашем наборе. У вашей википедии есть правильная формулировка (и формулы) – wildplasser

Что говорит ваша формула для значений 2^128 + 1? Я считаю, что он не говорит, что вероятность столкновения равна 1, поэтому она не может быть прав. на самом деле, я знаю, что это не так - правильная формула довольно большая и громоздкая, но есть хорошие аппроксимации с использованием экспоненты доли. SO не набирает формулы, поэтому я не буду пытаться писать формулы здесь.

Лучшее ключевое слово для поиска - возможно, «birthday attack».

источник

2014-01-11 13:27:08

'Что говорит ваша формула для наличия значений 2^128 + 1?' Я не думаю, что это говорит о том, что ?! Если кто-то может объяснить, как прийти к правильной вероятности приведенного выше примера, приближения или иначе, это было бы здорово. – Jodes

Что я имел в виду: предположим, что у вас есть 2^128 + 1 хэш-значения. Что говорит ваша формула о вероятности столкновения? (Это должно быть 1.) (И мой ответ содержит ссылку, указывающую на правильную формулу приближения.) –

Спасибо. Формула аппроксимации была именно тем, что я хотел. – Jodes

Почему столкновение с хешем может быть проблемой? Хеши никогда не предназначены для создания уникальных ценностей, а только для упрощения быстрого первого сравнения.

Если у вас возникли проблемы с хеш-коллизиями, вы используете его неправильно.

источник

2014-01-11 13:21:17

-1 Это просто неправильно. Многие хэш-функции * * предназначены для того, чтобы сделать коллизии исчезающе маловероятными, а хэш-функции с этими свойствами имеют множество отличных приложений. См. Http://en.wikipedia.org/wiki/Cryptographic_hash_function для определений и примеров. – delnan

@ delnan 'маловероятно' является ключевым словом здесь. Хеш-функция всегда либо: буквальная копия элемента (и, следовательно, уникальная), либо операция, которая ультимативно упрощает данные (и, следовательно, представляет собой сжатие с потерями). Нет никакой гарантии, и никакое намерение не создавать уникальные хеши. –

Вы, кажется, ссылаетесь на принцип пигментных отверстий. Этот принцип верен, но это не значит, что мы никогда не должны проектировать систему, которая будет дрожать перед лицом хеш-коллизий (о чем вы, по-видимому, говорите). Это будет противоречить современной практике криптографии и нескольким другим областям, которые полагаются на хеш-столкновения (для некоторых хорошо выбранных хэш-функций), менее вероятными, чем, например, космический луч, переворачивающий результат сравнения. Фактически, эти системы часто не имеют, или логически не могут, полного исходного значения для сравнения. – delnan

ответ

Смежные вопросы