Как хеш-функции кодируют бесконечное количество данных в конечное количество?

avatar
Finni
7 апреля 2018 в 22:35
287
2
0

Хеш-функции всегда создают вывод фиксированной длины, даже если ввод может быть бесконечно большим.

Так как же это возможно, что информация здесь не теряется? Разве некоторые входные данные не должны приводить к одному и тому же результату?

Источник

Ответы (2)

avatar
Primusa
7 апреля 2018 в 22:37
2

Да. Два ввода могут привести к одному и тому же результату, что приведет к коллизии хэшей.

Хеши спроектированы таким образом, что хешировать текст очень просто, но трудно обратить этот процесс вспять. Смысл хеширования не в хранении информации. Вместо этого в безопасности обычно используются хэши (а также структуры данных).

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

Набор хэшей — еще одно применение хеширования. Хешируя объект и сохраняя только хэши, вы можете проверить, присутствует ли объект в наборе или нет, за постоянное время. Вам нужно только просмотреть все объекты в наборе хэшей, которые имеют тот же хэш, что и объект, который вы проверяете. По мере роста размера хеш-набора увеличивается и вероятность коллизии хэшей.

Finni
7 апреля 2018 в 22:38
0

Таким образом, вы действительно можете использовать два или более паролей для входа в систему, если проверка пароля выполняется с помощью хеш-ключей?

Primusa
7 апреля 2018 в 22:39
0

Да, но вероятность совпадения двух хэшей для хорошего алгоритма хеширования почти равна нулю.

avatar
Jon Hanna
7 апреля 2018 в 22:43
1

Так как же это возможно, что здесь не теряется информация?

Это невозможно, и много информации потеряно.

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

В случае коллекции на основе хэша мы используем хэш-код, чтобы (надеюсь) иметь меньше коллизий, поэтому мы приближаемся к поиску O(1), но у нас есть некоторые средства для обработки, если коллизия все же произойдет.

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

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