Хеширование

Материал из Википедии — свободной энциклопедии

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

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

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

Содержание

1 Криптографические хэш-функции
2 Применение хеширования
- 2.1 Сверка данных
  - 2.1.1 Проверка на наличие ошибок
  - 2.1.2 Проверка парольной фразы
- 2.2 Ускорение поиска данных
3 Список алгоритмов

[править] Криптографические хэш-функции

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

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

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

[править] Применение хеширования

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

хорошая перемешиваемость данных
быстрый алгоритм вычисления

[править] Сверка данных

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

[править] Проверка на наличие ошибок

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

Бытовым аналогом хеширования в данном случае может служить приём, когда при переездах в памяти держат количество мест багажа. Тогда для проверки не нужно вспоминать про каждый чемодан, а достаточно их посчитать. Совпадение будет означать, что ни один чемодан не потерян. То есть, количество мест багажа является его хеш-кодом.

[править] Проверка парольной фразы

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP. В них хранятся лишь хэш-значения парольных фраз из учётных записей пользователей.

[править] Ускорение поиска данных

Основная статья: Хеш-таблица

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

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