Криптографические хэш-функции достигают каждого возможного значения, например. они сюръективны?

Возьмите часто используемую двоичную хэш-функцию - например, SHA-256. Как следует из названия, он выводит 256-битное значение.

Пусть A - множество всех возможных бинарных значений в 256 бит. А очень большой, но конечный.

Пусть B - множество всех возможных двоичных значений. B бесконечен.

Пусть C - множество значений, полученных при запуске SHA-256 на каждом члене B. Очевидно, что это невозможно сделать на практике, но я предполагаю, что мы все еще можем сделать математический анализ.

Мой вопрос: По необходимости C ⊆ A. Но C = A?

EDIT: Как было отмечено некоторыми ответами, это полностью зависит от рассматриваемой функции. Итак, если вы знаете ответ для какой-либо конкретной хэш-функции, скажите об этом!

Ответ 1

Прежде всего, отметьте, что SHA-256 не принимает все возможные двоичные строки в качестве входных данных. Как определено FIPS 180-3, SHA-256 принимает в качестве входной последовательности любую последовательность бит длиной менее 2 ^ 64 бит (то есть не более 18446744073709551615 бит). Это очень распространено; все хеш-функции как-то ограничены формальной длиной ввода. Одна из причин заключается в том, что понятие безопасности определяется с учетом вычислительной стоимости; есть порог о вычислительной мощности, который может нанести любой атакующий. Входы, выходящие за заданную длину, потребуют больше, чем максимальная вычислительная мощность, чтобы просто оценить функцию. Короче говоря, криптографы очень осторожны в бесконечности, потому что бесконечно стремятся предотвратить четкость определения безопасности, не говоря уже о количественном определении. Поэтому ваш входной набор C должен быть ограничен последовательностями до 2 ^ 64-1 бит.

Говоря, давайте посмотрим, что известно о сюръективности функции хеш-функции.

Хэш-функции пытаются эмулировать случайный оракул, концептуальный объект, который выбирает выходы случайным образом при единственном ограничении, что он "запоминает" предыдущие входы и выходы, и, если данный уже увиденный ввод, он возвращает тот же результат, что и раньше, По определению случайный оракул может быть доказан сюръективным только путем попыток ввода и исчерпания выходного пространства. Если выход имеет размер n бит, то ожидается, что для исчерпания выходного пространства размером 2 ^ n потребуется около 2 ^ (2n) отдельных входов. Для n = 256 это означает, что для хэширования около 2 ^ 512 сообщений (например, все сообщения из 512 бит) должно быть достаточно (в среднем). SHA-256 принимает входы гораздо дольше, чем 512 бит (действительно, он принимает входы до 18446744073709551615 бит), поэтому представляется весьма правдоподобным, что SHA-256 является сюръективным.

Однако не доказано, что SHA-256 является сюръективным, и это ожидается. Как показано выше, доказательство сюръективности случайного оракула требует огромной вычислительной мощности, существенно больше, чем просто атаки, такие как прообразы (2 ^ n) и столкновения (2 ^ (n/2)). Следовательно, хорошая хэш-функция "не должна" позволять на самом деле доказать свойство, такое как сюръективность. Было бы очень подозрительно: безопасность хэш-функции проистекает из неразрешимости их внутренней структуры, и такая неразрешимость должна решительно противостоять любой попытке математического анализа.

Как следствие, сюръективность формально не доказана для любой достойной хэш-функции, и даже для "сломанных" хеш-функций, таких как MD4. Он только "сильно подозревается" (случайный оракул с входами намного дольше, чем вывод должен быть сюръективным).

Ответ 2

Не обязательно. Принцип "голубиная скважина" гласит, что когда был создан еще один хэш за пределами размера А, существует вероятность столкновения 1, но он не указывает, что каждый отдельный элемент из A был сгенерирован.

Ответ 3

Это действительно зависит от хэш-функции. Если вы используете эту действительную хеш-функцию:

Int256 Hash (string input) {
    return 0;
}

то очевидно, что C!= A. Таким образом, "например, SHA256" является довольно важной записью для рассмотрения.

Чтобы ответить на ваш реальный вопрос: я так считаю, но я просто догадываюсь. Википедия не предоставляет никакой осмысленной информации об этом.

Ответ 4

Не обязательно. Это будет зависеть от хэш-функции.

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

Ответ 5

Это не всегда так. Однако качество, требуемое для хэш-алгоритма, следующее:

Мощность B
Перестановка хэшей в B (каждое значение в B должно иметь такую же вероятность быть хешем)