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

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

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

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

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

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

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

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

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

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

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

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

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

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

Есть две основные цели хеш-функций:

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

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

Если вы просто создаете хеш-таблицу в программе, вам не нужно беспокоиться о том, насколько обратим или взломан алгоритм ... 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;
}

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

• Лэндон Курт Нолл рекомендует для его сайт алгоритм FVN-1A по сравнению с исходным алгоритмом FVN-1: улучшенный алгоритм лучше распределяет последний байт в хэше. Соответственно скорректировал алгоритм.

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

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

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

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

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

Хорошая хеш-функция должна

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

Модуль простого числа не удовлетворяет ни одной из этих точек. Этого просто недостаточно. Часто это лучше, чем ничего, но даже не быстро. Умножение на беззнаковое целое число и взятие модуля степени двойки так же хорошо распределяет значения, что совсем нехорошо, но всего с 2 циклами ЦП это намного быстрее, чем от 15 до 40, которое займет простой модуль ( да, целочисленное деление действительно такое медленное).

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

Среди прочих полезных перестановок:

• умножение на нечетное целое число
• бинарные вращения
• xorshift

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

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

Сначала вы берете хорошую некриптографическую хеш-функцию, затем применяете одностороннюю функцию, такую ​​как возведение в степень для простого поля или k, многие приложения (n*(n+1)/2) mod 2^k, перемежающиеся с xorshift, когда k - это количество бит в результирующем хеш-коде.