Существуют ли обстоятельства, при которых алгоритм хеширования может быть гарантированно уникален?

Question

Если я хэширую похожие данные с ограниченным размером (например, номера социального страхования), используя алгоритм хеширования с большим размером байта, чем данные (например, sha-256), будет ли хеш гарантировать такой же уровеньУникальность как исходные данные?

Answer 1

Вероятность коллизии хеша не имеет никакого отношения к размеру входной строки (за исключением того, что она указывает, сколько входов необходимо сохранить уникальность среди). Возможно хэширование, когда вы хэшируете 0 и 1, используя идеальный алгоритм хэширования, хотя возможна 1 / (2 ^ длина бита). Что в случае с SHA-256 фактически равно нулю.

Хеш-коллизии - проблема парадокса дня рождения. В случае 256-битного хэша вероятность коллизии между двумя входами зависит исключительно от количества входов и составляет:

• 1 - (2 ^ 256)! / ((2 ^ 256 ^ inputcount) * (2 ^ 256-inputcount)!) Или, как говорили другие - в основном ноль для разумного количества входов.

Answer 2

Вы всегда можете создать индивидуальный хеш, который гарантирует уникальность.Для данных в известном домене (например, SSN) упражнение относительно простое.

Если целевое значение хеш-функции на самом деле имеет больше битов, чем то, что вы хешируете, хеш-код просто отображает входные значения в одно издоступные выходные значения.Это будет простое линейное отображение входного значения в виде многобайтового целого на выход в виде многобайтового целого.

Когда целевое значение хеш-функции содержит меньше битов, чем хешируется, уникальность никогда не может бытьгарантировано.

Answer 3

Другие отмечают, что столкновения не должны вызывать беспокойства; в этом весь смысл криптографически безопасных хеш-функций. Я просто хотел бы добавить следующее:

• Если ваш входной набор достаточно мал (например, данные SSN - их меньше миллиарда), то отсутствие коллизий поддается проверке: просто протестируйте его полностью.
• Если входной набор слишком велик для исчерпывающего сканирования, то ожидается, что отсутствие коллизии не может быть доказано . Ожидается, что хорошие хеш-функции будут действовать как случайные оракулы, и на случайном оракуле вы не сможете доказать такое свойство без исчерпывающих попыток. Возможность доказать отсутствие столкновения подозрительно выглядит как слабость функции.

Answer 4

Одна ключевая особенность криптографической защиты хеш-функции заключается в том, что вы защищены от коллизий вне всякого разумного сомнения, независимо от ввода. Это также справедливо для входных данных, которые короче, чем размер выходных данных, что аналогично длинному сообщению с небольшой энтропией. Таким образом, вы можете использовать SHA-2, не беспокоясь о столкновениях.

Answer 5

Если вы используете криптографический хеш, такой как SHA, краткий ответ - да.