Я делаю приложение, которое хранит документы и дает каждому UID на основе SHA1 дайджеста нескольких вещей, включая метку времени. В дайджесте много символов, и я хочу, чтобы пользователи могли идентифицировать документы, используя первые х символов полного дайджест. Какая хорошая ценность для x, если количество документов может составлять около 10K - 100K?
Сколько можно обрезать хэш SHA1 и быть уверенным в наличии уникального идентификатора?
Ответ 1
Адаптируя формулы на википедии для проблемы дня рождения, вы можете приблизить вероятность столкновения как e^(-n^2/(2^(b+1))), где n количество документов и b - это количество бит. График этой формулы с n = 100 000, похоже, вам понадобится b > 45 по крайней мере. Я был бы более склонен идти с 64, чтобы сделать его приятным и круглым. Тем не менее, у вас есть план борьбы с столкновениями, если они происходят (возможно, слегка измените временную метку или добавьте nonce?)
В этом случае, если sha1 основан не только на содержании документа, почему бы просто не сделать его случайным ID? В этом случае столкновения - это не проблема, так как вы всегда можете генерировать новое случайное число и повторять попытку (вероятность столкновения с одной попыткой одна и та же).
Ответ 2
Будьте осторожны с усечением, так как нет доказательств того, что меньший хэш является безопасным. См. Kelsey http://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf. Келси дает эвристические аргументы, указывающие на то же ( "Связанные выходы хеша" и "Близкие столкновения" ). Бихам/Чен предлагают примеры ближних столкновений; и Кнудсен демонстрирует Усеченные Дифференциалы.
В конце концов, вы, вероятно, захотите подавать свои данные в HMAC с усеченным размером (размер также переваривается HMAC), а затем используется усеченный HMAC.
Ответ 3
На самом деле это не значение; часть того, что делает SHA хорошим универсальным алгоритмом хеширования, состоит в том, что подобные данные не обязательно приводят к аналогичным хешированным значениям. Лучше всего (не зная ничего о своей системе) просто искать список документов, чьи хэши начинаются со значения, предоставленного пользователем, либо представить их со списком документов для выбора или перехода непосредственно к документу если есть только один.
Ответ 4
Это generalization проблема дня рождения, В вашем случае n - количество документов, а вместо константы 365 у вас будет количество возможностей, которые дает обрезание (так что для k бит это 2 k).
Конечно, точный расчет не может быть и речи, но вы можете использовать approximation.
Ответ 5
Ну, здесь, возможно, слишком упрощен ответ.
Если с полным sha1 вы получите около 1 в 2 ^ 160 вероятность столкновения, то, усекая один символ, вы увеличиваете шансы столкновения на 16 (все возможные значения усеченного символа)... что составляет 2 ^ 4. Итак, если вы усекаете x символов, вы получаете шансы на 1 из 2 ^ (160 - 4 * x) шансов на столкновение. Правильно?