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

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

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

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

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

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

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

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

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

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

Это пример хорошего, а также пример того, почему вы никогда не хотите писать. Это хэш 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;
}

Edit:

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

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

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

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

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

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

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

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

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

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

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

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