Хеширование

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

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

Применение хеширования:

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

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

Существует множество алгоритмов хеширования с различными свойствами:

Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функции может служить обрамление данных циклическим избыточным кодом (англ. «CRC»: Cyclic Redundancy Code).

История[править | править вики-текст]

Дональд Кнут — относит первую систематическую идею «хеширования» к сотруднику «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]

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

«Хеш-функции», основанные на делении[править | править вики-текст]

1. «Хеш-код» как остаток от деления на число всех возможных «хешей»[править | править вики-текст]

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

h(K)= K \mod M

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

2. «Хеш-код» как набор коэффициентов получаемого полинома[править | править вики-текст]

Ещё — следует сказать о методе «хеширования», основанном на делении на полином по модулю два. В данном методе — 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.

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