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

Понятное дело, что количество комбинаций хеш-суммы для каждого алгоритма огромное, но ведь файлов (или даже простых строк) еще больше.
  • Вопрос задан
  • 2877 просмотров
Решения вопроса 2
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
количество комбинаций хеш-суммы для каждого алгоритма огромное, но ведь файлов (или даже простых строк) еще больше

Возможных файлов больше. Реально использованных -- гораздо меньше. Т.е. если мы возьмём 109 компьютеров перебирающих 109 файлов в секунду, то чтобы перебрать все возможные значения sha1 потребуется 2160/1018 = 1030 секунд, т.е. 4 * 1022 лет, что существенно больше возраста Вселенной.
Ответ написан
Комментировать
tsarevfs
@tsarevfs
C++ developer
Действительно, в общем случае коллизий не избежать. Однако, на практике вполне достаточно того что коллизии маловероятны.
Можно посмотреть на примеры использования хешей:
* контрольная сумма — проверка того что большой файл не испорчен или не изменен. Вероятность коллизии ~= 1/2^HASH_LENGTH при случайных изменениях. Хорошие криптографические хеш функции предполагают, что подобрать данные с заданым хешом очень сложно.
* hash map. Коллизия в этой структуре данных это нормальная ситуация. Коллизии отслеживаются и обрабатываются различными способами, и если их становится слишком много пространство хешей расширяют.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
В дополнение к совершенно правильному ответу @jcmvbkbc :

По парадоксу дней рождения первая коллизия наиболее вероятно наступит, когда будет создано sqrt(2^N), т.е. 2^(N/2) документов. Так вот чтобы создать такую массу файлов для MD5 все население земного шара должно создавать по одному документу каждую секунду в течение 100 лет.
Ответ написан
Комментировать
DmitriyEntelis
@DmitriyEntelis
Думаю за деньги
На практике, на живых данных и шаловливых пользователях коллизии в hash функции встречаются гораздо чаще чем это можно ожидать теоретически. Поэтому на живом проекте важно помнить, что если хеш функции совпадают, это значит не "исходные строки совпадают", а "вероятно исходные строки совпадают"
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы