Хеширование

Хеш-функция, отображающая множество имён в множество натуральныых чисел

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

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

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

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

История

Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну (нем. Hans Peter Luhn), предложившему хеш-кодирование в январе 1953 года.

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число.^[1]

Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона (англ. W. Wesley Peterson) в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет был опубликована работа Вернера Бухгольца (нем. Werner Buchholz), в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.

В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем»^[2]. В 1968 году Роберт Моррис (англ. Robert Morris) опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Ершова использовалось слово «расстановка», а для коллизий использовался термин "конфликт" (Ершов использовал «расстановку» с 1956 года, в русскоязычном издании книги Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка»). Предлагалось также назвать метод русским словом «окрошка». Однако ни один из этих вариантов не прижился, и в русскоязычной литературе используется преимущественно термин «хеширование».^[3]

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

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

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

Предположим, для определённости, что количество ключей $K$, а хеш-функция $h(K)$ имеет не более $M$ различных значений:

$0<h(k)<M$

В качестве примера «плохой» хеш-функции можно привести функцию с $M=1000$, которая десятизначному натуральном числу $K$ сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа $K$. Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа.^[3]

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

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

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

$h(K)= K \mod M$

При этом очевидно, что при чётном $M$ значение функции будет чётным, при чётном $K$, и нечётным — при нечётном, что может привести к значительному смещению данных в файлах. Также не следует использовать в качестве $M$ степень основания счисления компьютера, так как хеш-код будет зависеть только от нескольких цифр числа $K$, расположенных справа, что приведет к большому количеству коллизий. На практике обычно выбирают простое $M$ — в большинстве случаев этот выбор вполне удовлетворителен.

Ещё следует сказать о методе хеширования, основанном на делении на полином по модулю два. В данном методе $M$ также должна являться степенью двойки, а бинарные ключи ($K=k_{n-1}k_{n-2}...k_{0}$) представляются в виде полиномов. В этом случае в качестве хеш-кода берутся значения коэффциентов полинома, полученного как остаток от деления $K$ на заранее выбранный полином $P$ степени $m$:

$K(x) \mod P(x) = h_{m-1}x^{m-1}+h_{1}x+h_{0}$

$h(x)=h_{m-1}...h_{1}h_{0}$

При правильном выборе $P(x)$ такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами.^[3]

Мультипликативная схема хеширования

Второй метод состоит в выборе некоторой целой константы $A$, взаимно простой с $w$, где $w$ — количество представимых машинным словом значений (в компьютерах IBM PC $2^{32}$). Тогда можем взять хеш-функцию вида:

$h(k) = \left[ M \left\lfloor \frac{A}{w}*K \right\rfloor \right]$

В этом случае, на компьютере с двоичной системой счисления, $M$ является степенью двойки и $h(K)$ будет состоять из старших битов правой половины произведения $A*K$.

Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией.^[3]

Одной из вариаций данного метода является хеширование Фибоначчи, основанное на свойствах золотого сечения. В качестве $A$ здесь выбирается ближайшее к $\varphi^{-1}*w$ целое число, взаимно простое с $w$^[3]

Хеширование строк переменной длины

Вышеизложенные методы применимы и в том случае, если нам необходимо рассматривать ключи, состоящие из нескольких слов или ключи переменной длины. Например можно скомбинировать слова в одно при помощи сложения по модулю $w$ или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу является хеш-функция Пирсона.

Хеширование Пирсона (англ. Pearson hashing) — алгоритм, предложенный Питером Пирсоном (англ. Peter Pearson) для процессоров с 8-битными регистрами, задачей которого является быстрое вычисление хеш-кода для строки произвольной длины. На вход функция получается слово $W$, состоящее из $n$ символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. Причем значение хеш-кода зависит от каждого символа входного слова.

Алгоритм можно описать следующим псевдокодом, который получает на вход строку $W$ и использует таблицу перестановок $T$

h := 0
for each c in W loop
  index := h xor c
  h := T[index]
end loop
return h

Среди преимуществ алгоритма следует отметить:

• Простоту вычисления;
• Не существует таких входных данных, для которых вероятность коллизии наибольшая;
• Возможность модификации в идеальную хеш-функцию.^[4]

В качестве альтернативного способа хеширования ключей, $K$ состоящих из $l$ символов ($K=x_{1}x_{2}...x_{l}$), можно предложить вычисление

$h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l})) \mod M$^[3]

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

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

Описание

1. Функция $h(k)\colon U\to [m]$ называется идеальной хеш-функцией для $S\subseteq U$, если она инъективна на $S$;
2. Функция $h(k)\colon U\to [m]$ называется минимальной идеальной хеш-функцией для $S\subseteq U$, если она является ИХФ и $m = n = |S|$;
3. Для целого $k\ge 1$, функция $h(k)\colon U\to [m]$ называется $k$-идеальной хеш-функцией (k-PHF) для $S\subseteq U$ если для каждого $j\in [m]$ имеем $|\{x\in S | h(x) = j\}|\le k$.

Идеальное хеширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе. Одним из наибоее очевидных примеров использования идеального (или скорее k-идеального) хеширования является ситуация, когда мы распологаем небольшой быстрой памятью, где размещаем значения хешей, связанных с данными хранящимися в большой, но медленной памяти. Причем размер блока можно выбрать таким, что необходимые нам данные, хранящиеся в медленной памяти, будут получены за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, в тех случаях, когда представление графа не умещается в основной памяти. ^[5]

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

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

Описание

Предположим, что мы хотим отобразить ключи из пространства $U$ в числа $[m]$. На входе алгоритм получает некоторый набор данных $S\in U$ и размерностью $n$, причем неизвестный заранее. Как правило целью хеширования является получение наименьшего числа коллизий, чего трудно добиться используя какую-то определенную хеш-функцию.

В качестве решения такой проблемы можно выбирать функцию случайным образом из определенного набора, называемого универсальным семейством $H = \{ h : U \to [m] \}$.^[6]

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

Основная статья: Коллизия хеш-функции

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

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

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

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

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

Первый метод заключается в поддержке $M$ связных списков, по одному на каждое значение хеш-функции. В списке хранятся ключи, дающие одинаковое значение хеш-кодов. В общем случае, если мы имеем $N$ ключей и $M$ списков, средний размер списка будет $\frac{N}{M}$ и хеширование приведет к уменьшению среднего количества работы по сравнению с последовательным поиском примерно в $M$ раз.

Второй метод состоит в том, что в массиве таблицы хранятся пары ключ-значение. Таким образом мы полностью отказываемся от ссылок и просто просматриваем записи таблицы, пока не найдем нужный ключ $K$ или пустую позицию. Последовательность, в которой просматриваются ячейки таблицы называется последовательностью проб.^[3]

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

Основная статья: Соль (криптография)

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

Применение хеш-функций

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

Криптографические хеш-функции

Основная статья: Криптографическая хеш-функция

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

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

Данные требования не являются независимыми:

• Обратимая функция нестойка к коллизиям первого и второго рода.
• Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

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

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

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

Контрольные суммы

Основная статья: Контрольная сумма

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

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

Платой за столь высокую скорость является отсутствие криптостойкости — лёгкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.

Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP.

Как правило, к такому алгоритму предъявляются требования отслеживания типичных аппаратных ошибок, таких, как несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов т. н. «циклических избыточных кодов» удовлетворяет этим требованиям. К ним относится, например, CRC32, применяемый в устройствах Ethernet и в формате сжатия данных ZIP.

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

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

Геометрическое хеширование

Геометрическое хеширование (англ. Geometric hashing) – широко применяемый в компьтерной графике и вычислительной геометрии метод для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар в множестве точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Таблица в данном случае является массивом с двумя или более индексами и называется файл сетки(англ. Grid file). Геометрическое хеширование также применяется в телекоммуникациях при работе с многомерными сигналами.^[8]

Ускорение поиска данных

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

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

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

Примечания

1. ↑ ^{1 2} Никлаус Вирт.Алгоритмы и структуры данных
2. ↑ Herbert Hellerman. Digital Computer System Principles. N.Y.: McGraw-Hill, 1967, 424 pp.
3. ↑ ^{1 2 3 4 5 6 7} Дональд Кнут. Искусство программирования
4. ↑ Pearson, Peter K. (June 1990), "«Fast Hashing of Variable-Length Text Strings»", Communications of the ACM Т. 33 (6): 677, doi:10.1145/78973.78978, <http://portal.acm.org/citation.cfm?id=78978> 
5. ↑ Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger (2009). «Hash, displace, and compress» (PDF) (Springer Berlin / Heidelberg). Проверено 2011-08-11.
6. ↑ Miltersen, Peter Bro Universal Hashing (PDF). Архивировано из первоисточника 24 июня 2009.
7. ↑ Брюс Шнаейр, Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си
8. ↑ Wolfson, H.J. & Rigoutsos, I (1997). Geometric Hashing: An Overview. IEEE Computational Science and Engineering, 4(4), 10-21.

Литература

• Брюс Шнайер "Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си". — М.: Триумф, 2002. — ISBN 5-89392-055-4

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0

• Никлаус Вирт "Алгоритмы и структуры данных". — М.: Мир, 1989. — ISBN 5-03-001045-9

Ссылки

• Теория хеш-функций
• Информация по электронной цифровой подписи

Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.