Какова максимальная длина строки, которая будет хэшироваться? - PullRequest
5 голосов
/ 01 августа 2011

Интересно ... какова максимальная длина строки, которая будет хэшироваться?

Например, с хешем Hello, world! с SHA-1 проблем нет. Но как насчет строки длиной 100 000 000 символов? Это вообще работает? Это как-то увеличивает вероятность столкновения?

Есть ли ограничения?

Ответы [ 2 ]

10 голосов
/ 01 августа 2011

Википедия показывает максимальный размер сообщения в битах для SHA-1 как 2 ^ 64−1.Таким образом, это будет 2 ^ 60-1 символов Юникода.В десятичном виде 1 152 921 504 606 846 975 символов.

Максимальная длина языковых строк составляет 2 ГБ - 1 символ.

Вероятность столкновения зависит от проблемы дня рождения , в частности от бита "Таблица вероятностей".Я не достаточно умен слишком ленив, чтобы определить вероятность коллизий с использованием SHA-1 с набором строк по 100 МБ ...

3 голосов
/ 01 августа 2011

Вы можете хешировать длинные входные данные.Да, алгоритмы хеширования все еще работают на больших входах.Нет, больший вход не увеличивает вероятность столкновения.(Но они займут больше времени.) Вы должны иметь в виду, что 100 миллионов символов - это не так много байтов для компьютера, и большинство используемых сегодня хешей fast .Современному компьютеру может потребоваться несколько секунд, чтобы хэшировать такую ​​длинную строку.

Теоретических ограничений нет, а практические ограничения допускают любое разумное использование.

...