Ответ 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. Он только "сильно подозревается" (случайный оракул с входами намного дольше, чем вывод должен быть сюръективным).