Инструменты пользователя

Инструменты сайта


examination:mszki:question29

29.Принципы хэширования и создание хэш-фукций.

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

Виды хеш-функций

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

  1. Быстро вычисляться;
  2. Минимизировать количество коллизий

Хеш-функции основанные на делении

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

h(K) = K mod M

Идеальное хеширование

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

Универсальное хеширование

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

Методы борьбы с коллизиями

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

В хеш-таблицах

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

  1. Метод цепочек(метод прямого связывания)
  2. Метод открытой адресации

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

Криптографическая соль

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

examination/mszki/question29.txt · Последние изменения: 2014/01/15 08:20 (внешнее изменение)