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

Question

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

function Hash(key)
  return key mod PrimeNumber
end

(мод является оператором% в C и аналогичных языках)

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

Answer 1

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

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

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

Это на самом деле один из случаев, когда я советую прочитать то, что Кнут должен сказать в Искусство компьютерного программирования , том. 3. Еще одно хорошее чтение - Жюльен Уокер Искусство хеширования .

Answer 2

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

http://www.azillionmonkeys.com/qed/hash.html

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

Answer 3

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

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

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

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

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

Answer 4

Это хороший пример, а также пример того, почему вы никогда не захотите его написать. Это хэш Фаулера / Нолла / Во (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: улучшенный алгоритм лучше рассеивает последний байт в хэше Я соответственно скорректировал алгоритм.

Answer 5

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

Answer 6

То, что вы говорите здесь, это то, что вы хотите иметь тот, который использует сопротивление столкновению. Попробуйте использовать SHA-2. Или попробуйте использовать (хороший) блочный шифр в функции одностороннего сжатия (никогда раньше не пробовал), как AES в режиме Миягучи-Пренель. Проблема в том, что вам нужно:

1) есть IV. Попробуйте использовать первые 256 бит дробных частей константы Хинчина или что-то в этом роде. 2) иметь схему заполнения. Легко. Возьмите его из хеша, такого как MD5 или SHA-3 (Keccak [произносится «кет-чак»]). Если вы не заботитесь о безопасности (несколько других сказали это), посмотрите на FNV или lookup2 Боба Дженкинса (на самом деле я первый, кто рекомендует lookup2). Также попробуйте MurmurHash, это быстро (проверьте это: .16 cpb ).

Answer 7

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

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

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

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

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

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

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

Надеюсь, это поможет!