Как хеш-функции кодируют бесконечное количество данных в конечное количество?
Хеш-функции всегда создают выходные данные фиксированной длины, даже если входные данные могут быть бесконечно большими.
Так как же возможно, что здесь не теряется никакая информация? Тогда разве некоторые входные данные не должны давать одинаковый результат?
Ответы 2
Да. Два входа могут привести к одному и тому же выходу, что приведет к конфликту хешей.
Хеши спроектированы таким образом, что хеширование текста очень легко, но изменить процесс вспять сложно. Смысл хеширования не в хранении информации. Вместо этого в системе безопасности обычно используются хеши (а также структуры данных).
Например, веб-сайты будут хешировать пароли пользователей и хранить хеши вместо физических паролей. Таким образом, если безопасность веб-сайта нарушена, злоумышленник может получить только хэши, которые по-прежнему не позволяют злоумышленнику войти в систему, поскольку очень сложно реконструировать пароль.
Хеш-набор - еще одно применение хеширования. Хешируя объект и сохраняя только хеши, вы можете проверить, присутствует ли объект в наборе или нет в постоянное время. Вам нужно только выполнить поиск по всем объектам в наборе хешей, которые имеют тот же хэш, что и проверяемый объект. По мере роста размера хеш-набора увеличивается и вероятность хеш-коллизии.
Да, но вероятность того, что два хеша точно совпадают для хорошего алгоритма хеширования, почти равна нулю.
So how is it possible, that no information is lost here?
Это невозможно, и много информации теряется.
В случае идеального хэша коллизии нет, и мы можем даже утверждать, что информация на самом деле не потеряна (она просто не содержится только в системе), потому что мы знаем все возможные входные данные и знаем, что в созданных хэшах нет коллизий, но их можно использовать в качестве индекса, что невозможно или не так хорошо с входными данными, поэтому они полезны.
В случае коллекции на основе хешей мы используем хэш-код, чтобы (надеюсь) иметь несколько коллизий, поэтому мы приближаемся к поиску O (1), но у нас есть некоторые средства для его обработки, если коллизия все же произойдет.
В случае криптографического хеша у нас могут быть коллизии, но это крайне сложно сделать сознательно по тем же (грубо говоря) причинам, почему сложно взломать современную криптографию, поэтому, хотя у вас может быть два пароля с одним и тем же хешем, вы не могли найти его нелегко (особенно если вы, например, не собираетесь иметь пароль на несколько тысяч страниц текста).
В случае хэша контрольной суммы у нас могут быть коллизии, но их маловероятность означает, что если у нас есть коррупция, у нас, вероятно, не будет совпадающего хэша.
То есть вы действительно могли бы использовать два или более паролей для входа в систему, если проверка пароля выполняется с помощью хеш-ключей?