Если длина хэша больше длины ввода, можно ли считать, что вероятность коллизии строго равна нулю?
Навеяно соседним вопросом про возможность коллизий при хэшировании. Пусть у нас есть некоторая криптостойкая функция, генерирующая из последовательности байт произвольной длины хэш определенной длины. Верно ли, что если длина входа этой функции меньше длины выхода, то на множестве всех допустимых входов этой функции с длиной меньше длины выхода заведомо не будет коллизий? По крайней мере, мощность множества возможных входов явно меньше мощности множества возможных выходов, то есть это утверждение может быть истинным.
Для правильного вопроса надо знать половину ответа
В общем случае неверно. Для каждого конкретного случая надо рассматривать хэш-функцию и математически доказывать такое утверждение.
Однако вашему условию удовлетворяет функция f(x) = x.
Нет, f(x)=x хотя действительно не дает коллизий, но она и не имеет постоянную длину выхода. Можно, конечно, использовать функцию типа f(x)=pad(x,0,n) где n - константа, 0 - чем добавлять до требуемой длины, такая подойдет. Вообще, интересуют MD5 и SHA1, при том, что известно, что к SHA1 подобрали коллизии, но на длине 32кбайт. Есть ли для них доказательства такого утверждения?
Максим Гришин, Для MD5 показаны коллизии на длине 512 бит.
Проводил ли кто-нибудь проверку или доказательство на малых длинах - не знаю. В принципе, такое доказательство особого смысла не имеет, так как изначальное назначение хэш-функций - ускорение сравнения объектов, когда полное сравнение проводится только при совпадении хэшей. И для этих целей имеет смысл только хэш-функция, дающая гораздо более короткий результат, чем изначальные данные. Использование в криптографии - это уже более позднее применение.
