Идеальный метод хеширования для широкого распределения значений? - PullRequest
8 голосов
/ 07 октября 2010

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

Это так же просто, как выбрать проверенный алгоритм хеширования с наибольшим размером дайджеста?Или есть какие-то тонкости, о которых я должен знать?Сейчас я смотрю либо на SHA-256, либо на 512.

Ответы [ 5 ]

2 голосов
/ 07 октября 2010

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

2 голосов
/ 07 октября 2010

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

Когда хеш-функция имеет выход n битов, можно найти столкновение с работой около 2 n / 2 , поэтому на практике хеш-функция с менее чем 140 битами вывода не может быть криптографически сильной. Более того, некоторые хеш-функции имеют недостатки, которые позволяют злоумышленникам быстрее находить столкновения; такие функции называются «нарушенными». Ярким примером является MD5.

Если вы не находитесь в обстановке безопасности и боитесь только случайных столкновений (то есть никто не будет активно пытаться спровоцировать столкновение, это может произойти только из-за чистой неудачи), тогда сломанный криптографический хеш Функция будет в порядке. Обычная рекомендация - MD4 . Криптографически говоря, он настолько сломан, насколько это возможно, но для не криптографических целей он чертовски быстр и обеспечивает 128 бит вывода, что позволяет избежать случайных коллизий.

Однако есть вероятность, что у вас не возникнет проблем с производительностью SHA-256 или SHA-512. На самом простом ПК они уже обрабатывают данные быстрее, чем может обеспечить жесткий диск: если вы хэшируете файл, чтение файла будет узким местом, а не хешированием. Я бы посоветовал использовать SHA-256, возможно, обрезать его вывод до 128 бит (если он используется в ситуациях, не связанных с безопасностью), и рассмотреть возможность переключения на другую функцию, только если какая-то проблема, связанная с производительностью, должным образом замечена и измерена.

1 голос
/ 08 октября 2010

Если криптографическая безопасность не имеет значения, вы можете посмотреть на эту ссылку & на эту .Самым быстрым и простым (для реализации) было бы хэширование Пирсона, если вы планируете вычислять хеш для заголовка / имени, а затем выполните поиск.или вы можете посмотреть на сверхбыстрый хеш здесь .Это также очень хорошо для не криптографического использования.

0 голосов
/ 20 октября 2010

В этом случае криптографическое хеширование не является излишним, хотя я понимаю, что современные компьютеры делают этот расчет довольно быстро? Я предполагаю, что у ваших пользователей будет уникальный идентификатор пользователя. Когда они загружают, вам просто нужно увеличить число. Таким образом, вы будете представлять их внутренне как userid1_song_1, userid1_song_2 и т. Д. Вы можете сохранить эту информацию в базе данных вместе с ней как уникальный ключ вместе с указанным пользователем именем.

Вы также не упомянули размер этих песен. Если это midi, то размер файла будет небольшим. Если размеры файлов велики (скажем, 3 МБ), то расчеты ша не будут мгновенными. На моем ноутбуке core2-duo сумма в 3,2 МБ, равная sha256, занимает 0,25 с; для sha1sum - 0,2 секунды.

Если вы намереваетесь использовать криптографический хеш, то sha1 должен быть более чем достаточным, и вам не нужен sha256. Никаких столкновений - хотя они существуют - пока не обнаружено. Git, Mercurial и другие распределенные системы контроля версий используют sh1. Git - это система, основанная на контенте, и использует sha1, чтобы узнать, был ли контент изменен.

0 голосов
/ 07 октября 2010

Что не так с чем-то вроде md5sum? Или, если вы хотите более быстрый алгоритм, я бы просто создал хеш из длины файла (мод 64K, чтобы уместить в два байта) и 32-битной контрольной суммы. Это даст вам 6-байтовый хеш, который должен быть разумно хорошо распределенным. Это не слишком сложно для реализации.

Конечно, как и во всех решениях хэширования, вы должны отслеживать коллизии и менять алгоритм, если количество элементов становится слишком низким. Это будет верно независимо от выбранного алгоритма (поскольку ваши пользователи могут начать загружать вырожденные данные).

Возможно, вы обнаружите, что пытаетесь решить проблему, которая не существует (иными словами, возможно, YAGNI).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...