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

Question

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

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

РЕДАКТИРОВАТЬ: Спасибо всем за быстрые и хорошо осведомленные ответы. Я решил использовать хэш MD5, и он отлично подходит для моих целей. Уникальность - важная проблема, но я не ожидаю, что количество этих хешей будет очень большим в любой момент времени - эти хеши представляют собой серверы программного обеспечения в домашней ЛВС, поэтому при максимуме их будет 5, может быть 10. 1005 *

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Кроме того, еще одна реализация C MD5, разработанная людьми.

Answer 6

Здесь - это реализация MD5 в C.

Answer 7

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

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

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

Answer 8

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

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

Answer 9

Используйте Apache DigestUtils:

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

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