Что такое хорошая хэш-функция?

Существует две главных цели хеш-функций:

• для рассеивания точек данных однородно в n биты.
• для безопасной идентификации входных данных.

невозможно рекомендовать хеш, не зная то, для чего Вы используете его.

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

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

Это - пример хорошего и также пример того, почему Вы никогда не хотели бы писать тот. Это - Fowler / Noll / Vo (FNV) Хеш, который является в равной степени гением информатики и чистым вуду:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Редактирование:

• Landon Curt Noll рекомендует на его сайт алгоритм FVN-1A по исходному FVN-1 алгоритму: улучшенный алгоритм лучше рассеивает последний байт в хеше. Я скорректировал алгоритм соответственно.

Хорошая хеш-функция имеет следующие свойства:

1. , Учитывая хеш сообщения в вычислительном отношении невозможно для взломщика найти другое сообщение таким образом, что их хеши идентичны.

2. , Учитывая пару сообщения, m' и m, в вычислительном отношении невозможно найти два таким образом, что это h (m) = h (m')

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

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

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

А более современный хеш, такой как Whirpool является лучшим выбором. Это не страдает от этих, расширение сообщения нападает и использует ту же математику в качестве использования AES для доказательства безопасности против множества нападений.

Hope, которая помогает!

Нет такой вещи, как “good хеширует function” для универсальных хешей (редактор да, я знаю, что существует такая вещь как “universal hashing”, но это не то, что я имел в виду). В зависимости от контекста различные критерии определяют качество хеша. Два человека уже упомянули SHA. Это - криптографический хеш, и это не во всей пользе для хеш-таблиц, которые Вы, вероятно, имеете в виду.

Хеш-таблицы имеют совсем другие требования. Но тем не менее, нахождение хорошей хеш-функции универсально трудно, потому что различные типы данных выставляют другую информацию, которая может быть хеширована. Как показывает опыт, хорошо рассмотреть весь информация, которую тип содержит одинаково. Это не всегда легко или даже возможно. По причинам статистики (и следовательно коллизия), также важно генерировать хорошее распространение по пространству задач, т.е. все возможные объекты. Это означает, что при хешировании чисел между 100 и 1050 это бесполезно, чтобы позволить старшей значащей цифре играть большую роль в хеше, потому что для ~ 90% объектов, эта цифра будет 0. Намного более важно позволить последним трем цифрам определить хеш.

Точно так же при хешировании строк важно рассмотреть все символы †“кроме тех случаев, когда известно заранее, что первые три символа всех строк будут тем же; рассмотрение их затем является отходами.

Это - на самом деле один из случаев, где я советую для чтения то, что Knuth должен заявить в Искусство Программирования , издание 3. Другим хорошим чтением является Julienne Walker Искусство Хеширования .

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