Хеширование

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

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

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

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

Существует множество алгоритмов хэширования с различными свойствами (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хэш-функции определяется спецификой решаемой задачи. Простейшими примерами хэш-функций могут служить контрольная сумма или 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]

Виды хэш-функций[править | править вики-текст]

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

  • быстро вычисляться;
  • минимизировать количество коллизий

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

\forall k\ 0 \leqslant 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}+\dots+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]

Универсальное хэширование[править | править вики-текст]

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

Описание[править | править вики-текст]

Предположим, что мы хотим отобразить ключи из пространства 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.
  • Никлаус Вирт. "Алгоритмы и структуры данных". — М.: Мир, 1989. — ISBN 5-03-001045-9.

Ссылки[править | править вики-текст]