Существуют ли обстоятельства, при которых алгоритм хеширования может быть гарантированно уникальным?
Если я хэширую аналогичные данные с ограниченным размером (например, номера социального страхования) с использованием алгоритма хеширования с большим размером байта, чем у данных (например, sha-256), хеш будет гарантировать тот же уровень уникальности, что и исходные данные?
5 ответов
Вероятность коллизии хеша не имеет никакого отношения к размеру входной строки (за исключением того, что она указывает, сколько входных данных вам необходимо для сохранения уникальности). Возможно хэширование, когда вы хэшируете 0 и 1, используя идеальный алгоритм хэширования, хотя возможна 1/(2^ длина бита). Что в случае с SHA-256 фактически равно нулю.
Хеш-коллизии - проблема парадокса дня рождения. В случае 256-битного хэша вероятность коллизии между двумя входами зависит исключительно от количества входов и составляет:
- 1 - (2 ^ 256)! / ((2 ^ 256 ^ inputcount) * (2 ^ 256-inputcount)!) Или, как говорили другие - в основном ноль для разумного количества входов.
Вы всегда можете создать индивидуальный хеш, который гарантирует уникальность. Для данных в известном домене (например, SSN) упражнение относительно простое.
Если целевое хеш-значение на самом деле имеет больше доступных битов, чем то, что вы хешируете, хеш просто отображает входные значения в одно из доступных выходных значений. Это будет простое линейное отображение входного значения в виде многобайтового целого на выход в виде многобайтового целого.
Когда целевое хеш-значение имеет меньше битов, чем хешируется, уникальность никогда не может быть гарантирована.
Другие отмечали, что столкновения не должны вызывать беспокойства; в этом весь смысл криптографически безопасных хеш-функций. Я просто хотел бы добавить следующее:
- Если ваш входной набор достаточно мал (например, данные представляют собой SSN - их меньше миллиарда), то отсутствие коллизий поддается проверке: просто протестируйте их полностью.
- Если входной набор слишком велик для исчерпывающего сканирования, то ожидается, что отсутствие коллизии не может быть доказано. Ожидается, что хорошие хеш-функции будут действовать как случайные оракулы, и на случайном оракуле вы не сможете доказать такое свойство без исчерпывающих попыток. Возможность доказать отсутствие столкновения подозрительно выглядит как слабость функции.
Если вы используете криптографический хеш, такой как SHA, тогда короткий ответ - да.
Одна из ключевых особенностей криптографически защищенной хеш-функции заключается в том, что вы защищены от коллизий вне всякого сомнения, независимо от ввода. Это также справедливо для входных данных, которые короче, чем размер выходных данных, что аналогично длинному сообщению с небольшой энтропией. Таким образом, вы можете использовать SHA-2, не беспокоясь о столкновениях.