Как написать хэш-функцию в C?

Таблицы Hash считаются самым быстрым/лучшим способом хранения/получения данных.

Мое понимание хэш-таблицы, хеширование выглядит следующим образом (Пожалуйста, поправьте меня, если я ошибаюсь или добавлю Если есть что-то еще):

  • A Таблица хэшей - это не что иное, как массив (одиночный или многомерный) для хранения значений.
  • Хеширование - это процесс поиска индекса/местоположения в массиве для вставки/извлечения данных. Вы берете элемент данных и передаете его как ключ в хеш-функцию, и вы получите индекс/местоположение, в которое нужно вставить/получить данные.

У меня вопрос:

Является ли хеш-функция, используемая для хранения/извлечения данных DIFFERENT из криптографическая хэш-функция, используемая в приложениях безопасности для аутентификации как MD5, HMAC, SHA-1 и т.д...?

Чем они отличаются?

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

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

Ответы

Ответ 1

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

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

В качестве примера довольно типичная нормальная хеш-функция может выглядеть примерно так:

// warning: untested code.
size_t hash(char const *input) { 

    const int ret_size = 32;
    size_t ret = 0x555555;
    const int per_char = 7;

    while (*input) { 
        ret ^= *input++;
        ret = ((ret << per_char) | (ret >> (ret_size - per_char));
   }
   return ret;
}

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

Ответ 2

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

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

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

Ответ 3

Цели дизайна разные.

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

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