Если длина хэша больше длины ввода, можно ли считать, что вероятность коллизии строго равна нулю? Навеяно соседним вопросом про возможность коллизий при хэшировании. Пусть у нас есть некоторая криптостойкая функция, генерирующая из последовательности байт произвольной длины хэш определенной длины. Верно ли, что если длина входа этой функции меньше длины выхода, то на множестве всех допустимых входов этой функции с длиной меньше длины выхода заведомо не будет коллизий? По крайней мере, мощность множества возможных входов явно меньше мощности множества возможных выходов, то есть это утверждение может быть истинным.

21 Авг 2019 в 06:06
193 +1
1
Ответы
1

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

20 Апр в 13:23
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Название заказа не должно быть пустым
Введите email
Бесплатные доработки
Гарантированные бесплатные доработки
Быстрое выполнение
Быстрое выполнение от 2 часов
Проверка работы
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Название заказа не должно быть пустым
Введите email
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 92 943 авторам
Первые отклики появятся уже в течение 10 минут
Прямой эфир