Хэш строки определенной длины

Question

Есть ли способ генерации хэша строки, чтобы сам хэш имел определенную длину? У меня есть функция, которая генерирует 41-байтовые хэши (SHA-1), но мне нужно, чтобы она была максимально на 33 байта (из-за определенных ограничений аппаратного обеспечения). Если я урезаю 41-байтовый хеш до 33, я, наверное (конечно!) Потерял бы уникальность.

Или, на самом деле, я полагаю, что алгоритм MD5 прекрасно подойдет, если я смогу найти код C для одного с вашей помощью.

EDIT: Спасибо всем за быстрые и знающие ответы. Я решил пойти с хешем MD5, и он подходит для моей цели. Уникальность - важная проблема, но я не ожидаю, что количество этих хэшей будет очень большим в любой момент времени - эти хэши представляют собой серверы программного обеспечения в домашней локальной сети, поэтому при макс. Будет 5, может быть, 10.

Answer 1

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

md5: http://www.md5hashing.com/c++/

кстати. md5 - 16 байт, sha1 - 20 байт, а sha256 - 32 байта, однако, как шестнадцатеричные, они все удваиваются по размеру. Если вы можете хранить байты, вы можете даже использовать sha256.

Answer 2

Я считаю, что алгоритм хэширования MD5 имеет 32-значное число, поэтому, возможно, он будет более подходящим.

Редактировать: для доступа к функциональности MD5 должно быть возможно подключиться к библиотекам openssl. Однако вы упомянули аппаратные ограничения, поэтому это может быть невозможно в вашем случае.

Answer 3

Вы можете использовать Elf hash (< - C код) или другую простую хеш-функцию, подобную этой, вместо MD5 или SHA-X. Они не являются безопасными, но они могут быть настроены на любую длину вам нужно

Answer 4

Вероятности столкновения с 33-байтовой 1/2^132 (по случаю дня рождения Paradox)

Так что не беспокойтесь о теряя уникальность.

Обновление: я не проверял фактическую длину байта SHA1. Вот соответствующий расчет: столкновение 32-гола (33 байта шестнадцатеричного символа завершения) происходит только тогда, когда количество хэшей строк становится вокруг sqrt (2^(32 * 4)) = 2^64.

Answer 5

Here является реализацией MD5 в С.

Answer 6

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

Лично я использовал бы MD5 (если вам нужно сохранить текст) или хеш 256b (32B), такой как SHA256 (если вы можете хранить в двоичном формате) в этой ситуации. Усечение другого алгоритма хэширования на 33B тоже работает, и МОЖЕТ увеличить возможность генерации хеш-коллизий. Это зависит от алгоритма.

Also, yet another C implementation of MD5, by the people who designed it.

Answer 7

Там нет больше шансов столкновения с подстрокой (sha_hash, 0, 33), чем с любым другим хэшем, который имеет длину 33 байта, из-за путями алгоритмы хэширования предназначены (энтропия равномерно распространено в полученной строке).

Answer 8

Если я урезаю 41-байтовый хеш до 33, я, вероятно, (конечно!) Потерял бы уникальность.

Что заставляет вас думать, что у вас есть уникальность сейчас? Да, очевидно, что вероятность столкновения явно выше, если вы играете только с 33 байтами вместо 41, но вам нужно полностью осознавать, что столкновения только когда-либо маловероятны, а не невозможны для любой ситуации, когда имеет смысл использовать хэш в первую очередь. Если вы хешируете более 41 байта данных, есть явно более возможные комбинации, чем есть хеши.

Теперь, лучше ли вам урезать хэш SHA-1 или использовать более короткий хэш, такой как MD5, я не знаю. Я думаю, что я был бы более уверен, сохраняя весь хэш, но MD5 имеет known vulnerabilities, который может быть или не быть проблемой для вашего конкретного приложения.

Answer 9

Использование Apache в DigestUtils:

http://commons.apache.org/codec/api-release/org/apache/commons/codec/digest/DigestUtils.html#md5Hex(java.lang.String)

преобразует хэш в 32 символов шестнадцатеричной строки.