Криптографические хеш-функции достигают каждого возможного значения, например, действительно ли они сюръективны?
Возьмите наиболее часто используемую двоичную хеш-функцию - например, SHA-256. Поскольку имя подразумевает, оно производит 256 битовых значений.
Позвольте A быть множеством всех возможных двоичных значений на 256 битов. A является чрезвычайно большим, но конечным.
Позвольте B быть множеством всех возможных двоичных значений. B бесконечен.
Позвольте C быть множеством значений, полученным рабочим SHA-256 на каждом члене B. Очевидно, это не может быть сделано на практике, но я предполагаю, что мы можем все еще сделать математический анализ его.
Мой Вопрос: При необходимости, C ⊆ A. Но C = A?
Править: Как был указан некоторыми ответами, это совершенно зависит от, имеет рассматриваемую функцию. Так, если Вы знаете ответ для какой-либо конкретной хеш-функции, скажите так!
5 ответов
Во-первых, отметим, что SHA-256 не принимает все возможные двоичные строки в качестве входных. Как определено в FIPS 180-3 , SHA-256 принимает в качестве входных данных любую последовательность битов длиной меньше 2 ^ 64 бит (т. Е. Не более 18446744073709551615 бит). Это очень часто; все хэш-функции каким-то образом ограничены формальной длиной ввода. Одна из причин заключается в том, что понятие безопасности определяется в отношении вычислительных затрат; существует порог вычислительной мощности, который может получить любой злоумышленник. Для входных данных, превышающих заданную длину, потребуется больше, чем максимальная вычислительная мощность, чтобы просто оценить функцию. Короче говоря, криптографы очень настороженно относятся к бесконечности, потому что бесконечность, как правило, мешает даже определению безопасности, не говоря уже о количественной оценке. Таким образом, ваш входной набор C должен быть ограничен последовательностями до 2 ^ 64-1 бит.
При этом давайте посмотрим, что известно о сюръективности хеш-функции.
Хеш-функции пытаются имитировать случайный оракул , концептуальный объект, который выбирает выходные данные случайным образом с единственным ограничением, что он «запоминает» предыдущие входные и выходные данные, и, если задан уже видимый входной сигнал, он возвращает тот же результат, что и раньше. По определению, случайный оракул можно доказать сюръективностью, только попробовав вводимые данные и исчерпав пространство вывода. Если выход имеет размер n бит, то ожидается, что потребуется около 2 ^ (2n) отдельных входов, чтобы исчерпать пространство вывода размером 2 ^ n .Для n = 256 это означает, что хеширования около 2 ^ 512 сообщений (например, всех сообщений размером 512 бит) должно быть достаточно (в среднем). SHA-256 принимает входные данные намного длиннее 512 бит (действительно, он принимает входные данные длиной до 18446744073709551615 бит), поэтому кажется весьма правдоподобным , что SHA-256 является сюръективным.
Однако не было доказано, что SHA-256 сюръективен, и это ожидается . Как показано выше, для доказательства сюръективности случайного оракула требуется очень много вычислительной мощности, существенно больше, чем простые атаки, такие как прообразы ( 2 ^ n ) и коллизии ( 2 ^ (n / 2 ) ). Следовательно, хорошая хеш-функция «не должна» допускать фактического доказательства такого свойства, как сюръективность. Это было бы очень подозрительно: безопасность хеш-функций проистекает из неразрешимости их внутренней структуры, и такая неразрешимость должна решительно противодействовать любым попыткам математического анализа.
Как следствие, сюръективность формально не доказана ни для одной приличной хеш-функции, и даже для «сломанных» хеш-функций, таких как MD4. Это только «очень подозрительно» (случайный оракул с входными данными намного длиннее, чем выход, должен быть сюръективным).
Это не всегда так. Однако для алгоритма хеширования требуются следующие качества:
- Мощность B
- Перераспределение хешей в B (каждое значение в B должно иметь одинаковую вероятность, чтобы быть хешем)
Не обязательно. Принцип «ящика» гласит, что как только сгенерирован еще один хэш, превышающий размер A, вероятность коллизии равна 1, но он не утверждает, что каждый отдельный элемент A был сгенерирован.
Не обязательно. Это будет зависеть от хеш-функции.
Вероятно, было бы идеально, если бы хеш-функция была сюръективной , но есть вещи, которые обычно более важны, например, низкая вероятность коллизий.
Это действительно зависит от хеш-функции. Если вы используете эту допустимую хеш-функцию:
Int256 Hash (string input) {
return 0;
}
, то очевидно, что C! = A.Так что «например, SHA256» - довольно важное замечание, которое следует учитывать.
Чтобы ответить на ваш настоящий вопрос: я верю в это, но я просто предполагаю. Википедия не дает по этому поводу сколько-нибудь значимой информации.