Хеш-функция

Хеш-функция (англ. hash function от hash — «превращать в фарш», «мешанина»), или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

Хеш-функции применяются в следующих случаях:

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

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

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

• разрядность;
• вычислительная сложность;
• криптостойкость.

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

История

Шифровка сообщений без возможности однозначной расшифровки, а только с целью подтверждения авторского приоритета, применялась издавна.

Галилео Галилей наблюдал кольца Сатурна, которые принял за «ушки». Не будучи уверен, но желая утвердить свой приоритет, он опубликовал сообщение с перестановленными буквами: smaismrmilmepoetaleumibunenugttauiras. В 1610 году он раскрыл исходную фразу: Altissimum planetam tergeminum obseruaui, что в переводе с латинского языка означает «высочайшую планету тройною наблюдал». Таким образом, на момент публикации первого сообщения исходная фраза не была раскрыта, но была создана возможность подтвердить её позже.

В середине 1650-х Христиан Гюйгенс разглядел кольца и опубликовал сообщение с буквами, расставленными по алфавиту: aaaaaaacccccdeeeeeghiiiiiiillllmmnnnnnnnnnooooppqrrstttttuuuuu. Через некоторое время была опубликована и исходная фраза: Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato — «Окружен кольцом тонким, плоским, нигде не подвешенным, наклоненным к эклиптике». От применения хеш-функции, включая и цель позднее подтвердить некоторое нераскрытое сообщение, данный случай отличается только тем, что выходное сообщение не имеет фиксированной длины, а определяется длиной входного. Фактически, расстановка букв исходного сообщения по алфавиту является некоторой хеш-функцией, но только с результатом нефиксированной длины.

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

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

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

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

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

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

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

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

Введём обозначения:

• [math]\displaystyle{ K }[/math] — количество «ключей» (входных данных);
• [math]\displaystyle{ h(k) }[/math] — хеш-функция, имеющая не более [math]\displaystyle{ M }[/math] различных значений (выходных данных).

То есть:

[math]\displaystyle{ \forall k\in [0;\,K): h(k) \lt M }[/math].

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

Рассмотрим несколько простых и надёжных реализаций «хеш-функций».

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

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

Хеш-функция может вычислять «хеш» как остаток от деления входных данных на [math]\displaystyle{ M }[/math]:

[math]\displaystyle{ h(k) = k \mod M }[/math],

где [math]\displaystyle{ M }[/math] — количество всех возможных «хешей» (выходных данных).

При этом очевидно, что при чётном [math]\displaystyle{ M }[/math] значение функции будет чётным при чётном [math]\displaystyle{ k }[/math] и нечётным — при нечётном [math]\displaystyle{ k }[/math]. Также не следует использовать в качестве [math]\displaystyle{ M }[/math] степень основания системы счисления компьютера, так как «хеш-код» будет зависеть только от нескольких цифр числа [math]\displaystyle{ k }[/math], расположенных справа, что приведёт к большому количеству коллизий. На практике обычно выбирают простое [math]\displaystyle{ M }[/math]; в большинстве случаев этот выбор вполне удовлетворителен.

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

Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе [math]\displaystyle{ M }[/math] должна являться степенью двойки, а бинарные ключи ([math]\displaystyle{ K=k_{n-1}k_{n-2}...k_{0} }[/math]) представляются в виде полиномов, в качестве «хеш-кода» «берутся» значения коэффициентов полинома, полученного как остаток от деления входных данных [math]\displaystyle{ K }[/math] на заранее выбранный полином [math]\displaystyle{ P }[/math] степени [math]\displaystyle{ m }[/math]:

[math]\displaystyle{ K(x) \mod P(x) = h_{m-1}x^{m-1} + \dots + h_{1}x + h_{0} }[/math]

[math]\displaystyle{ h(x) = h_{m-1} ... h_{1} h_{0} }[/math]

При правильном выборе [math]\displaystyle{ P(x) }[/math] гарантируется отсутствие коллизий между почти одинаковыми ключами.

«Хеш-функции», основанные на умножении

Обозначим символом [math]\displaystyle{ w }[/math] количество чисел, представимых машинным словом. Например, для 32-разрядных компьютеров, совместимых с IBM PC, [math]\displaystyle{ w = 2^{32} }[/math].

Выберем некую константу [math]\displaystyle{ A }[/math] так, чтобы [math]\displaystyle{ A }[/math] была взаимно простой с [math]\displaystyle{ w }[/math]. Тогда хеш-функция, использующая умножение, может иметь следующий вид:

[math]\displaystyle{ h(K) = \left[ M \left\lfloor \frac{A}{w}*K \right\rfloor \right] }[/math]

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

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

Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи. Хеширование Фибоначчи основано на свойствах золотого сечения. В качестве константы [math]\displaystyle{ A }[/math] здесь выбирается целое число, ближайшее к [math]\displaystyle{ \varphi^{-1}*w }[/math] и взаимно простое с [math]\displaystyle{ w }[/math], где [math]\displaystyle{ \varphi }[/math] — это золотое сечение.

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

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

Например, можно скомбинировать слова в одно при помощи сложения по модулю [math]\displaystyle{ w }[/math] или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.

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

Алгоритм можно описать следующим псевдокодом, который получает на вход строку [math]\displaystyle{ W }[/math] и использует таблицу перестановок [math]\displaystyle{ T }[/math]:

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

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

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

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

[math]\displaystyle{ h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l})) \mod M }[/math]

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

Идеальной хеш-функцией (англ. perfect hash function) называется такая функция, которая отображает каждый ключ из набора [math]\displaystyle{ S }[/math] во множество целых чисел без коллизий. В математике такое преобразование называется инъективным отображением.

Описание

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

Идеальное хеширование применяется, если требуется присвоить уникальный идентификатор ключу без сохранения какой-либо информации о ключе. Пример использования идеального (или скорее [math]\displaystyle{ k }[/math]-идеального) хеширования: размещение хешей, связанных с данными, хранящимися в большой и медленной памяти, в небольшой и быстрой памяти. Размер блока можно выбрать таким, чтобы необходимые данные считывались из медленной памяти за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, если представление графа не умещается в основной памяти.

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

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

Описание

Предположим, что требуется отобразить ключи из пространства [math]\displaystyle{ U }[/math] в числа [math]\displaystyle{ [m] }[/math]. На входе алгоритм получает данные из некоторого набора [math]\displaystyle{ S \in U }[/math] размерностью [math]\displaystyle{ n }[/math]. Набор заранее неизвестен. Как правило, алгоритм должен обеспечить наименьшее число коллизий, чего трудно добиться, используя какую-то определённую хеш-функцию. Число коллизий можно уменьшить, если каждый раз при хешировании выбирать хеш-функцию случайным образом. Хеш-функция выбирается из определённого набора хеш-функций, называемого универсальным семейством [math]\displaystyle{ H = \{ h : U \to [m] \} }[/math].

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

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

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

Методы борьбы с коллизиями в хеш-таблицах

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

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

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

При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» — «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется [math]\displaystyle{ N }[/math] ключей и [math]\displaystyle{ M }[/math] списков, средний размер хеш-таблицы составит [math]\displaystyle{ \frac{N}{M} }[/math]. В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в [math]\displaystyle{ M }[/math] раз.

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

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

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

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

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

Хеш-функции широко используются в криптографии.

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

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

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

Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии, так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция [math]\displaystyle{ H }[/math] считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

• необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных [math]\displaystyle{ X }[/math], для которого [math]\displaystyle{ H(X) = m }[/math];
• стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого [math]\displaystyle{ H(N) = H(M) }[/math];
• стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений [math]\displaystyle{ (M, M') }[/math], имеющих одинаковый хеш.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 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.
• Никлаус Вирт. Алгоритмы и структуры данных. Новая версия для Оберона. — М.: «ДМК Пресс», 2010. — ISBN 978-5-94074-584-6.

Ссылки

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