Interested Article - Хеш-функция
![](/images/007/337/7337568/1.jpg?rand=630695)
![](https://cdn.wafarin.com/avatars/6a6f9ac08513a095b191a1f0789b03ac.png)
- 2020-05-28
- 2
Хеш-функция ( англ. 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 года ( нем. ) (сотрудник фирмы IBM ) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую идею «хеширования».
В 1956 году ( англ. ) в своей работе « Computers and automation » первым описал идею «хеширования» такой, какой её знает большинство программистов сейчас. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса» остаток от деления на простое число .
В 1957 году в журнале « » была опубликована статья ( англ. ) о поиске текста в больших файлах . Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа ( нем. ), в которой было проведено обширное исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, однако никаких значимых работ не публиковалось.
В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана « Принципы цифровых вычислительных систем » . В 1968 году ( англ. ) опубликовал в журнале « Communications of the ACM » большой обзор по «хешированию». Эта работа считается « ключевой » публикацией, вводящей понятие о «хешировании» в научный оборот, и закрепившей термин «хеш», ранее применявшийся только специалистами ( жаргон ).
До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Петровича Ершова использовалось слово «расстановка», а для « коллизий » использовался термин «конфликт» ( А. П. Ершов использовал «расстановку» с 1956 года ). В русскоязычном издании книги Никлауса Вирта « Алгоритмы и структуры данных » 1989 года также используется термин «расстановка». Предлагалось также назвать метод другим русским словом: « окрошка ». Однако ни один из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование» .
Виды «хеш-функций»
«Хорошая» хеш-функция должна удовлетворять двум свойствам :
- быстрое вычисление;
- минимальное количество « коллизий ».
Введём обозначения:
- — количество «ключей» (входных данных);
- — хеш-функция, имеющая не более различных значений (выходных данных).
То есть:
- .
В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральному числу сопоставляет три цифры, выбранные из середины двадцатизначного квадрата числа . Казалось бы, значения «хеш-кодов» должны равномерно распределяться между « 000 » и « 999 », но для « реальных » данных это справедливо лишь в том случае, если « ключи » не имеют «большого» количества нулей слева или справа .
Рассмотрим несколько простых и надёжных реализаций «хеш-функций».
«Хеш-функции», основанные на делении
1. «Хеш-код» как остаток от деления на число всех возможных «хешей»
Хеш-функция может вычислять «хеш» как остаток от деления входных данных на :
- ,
где — количество всех возможных «хешей» (выходных данных).
При этом очевидно, что при чётном значение функции будет чётным при чётном и нечётным — при нечётном . Также не следует использовать в качестве степень основания системы счисления компьютера , так как «хеш-код» будет зависеть только от нескольких цифр числа , расположенных справа, что приведёт к большому количеству коллизий . На практике обычно выбирают простое ; в большинстве случаев этот выбор вполне удовлетворителен.
2. «Хеш-код» как набор коэффициентов получаемого полинома
Хеш-функция может выполнять деление входных данных на полином по модулю два. В данном методе должна являться степенью двойки, а бинарные ключи ( ) представляются в виде полиномов , в качестве «хеш-кода» «берутся» значения коэффициентов полинома , полученного как остаток от деления входных данных на заранее выбранный полином степени :
При правильном выборе гарантируется отсутствие коллизий между почти одинаковыми ключами .
«Хеш-функции», основанные на умножении
Обозначим символом количество чисел, представимых машинным словом . Например, для 32-разрядных компьютеров, совместимых с IBM PC , .
Выберем некую константу так, чтобы была взаимно простой с . Тогда хеш-функция, использующая умножение, может иметь следующий вид:
В этом случае на компьютере с двоичной системой счисления является степенью двойки, и будет состоять из старших битов правой половины произведения .
Одним из преимуществ хеш-функций, основанных на делении и умножении, является выгодное использование неслучайности реальных ключей. Например, если ключи представляют собой арифметическую прогрессию (например, последовательность имён «Имя 1», «Имя 2», «Имя 3»), хеш-функция, использующая умножение, отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшит количество коллизий по сравнению со случайной ситуацией .
Одной из хеш-функций, использующих умножение, является хеш-функция, использующая хеширование Фибоначчи . Хеширование Фибоначчи основано на свойствах золотого сечения . В качестве константы здесь выбирается целое число, ближайшее к и взаимно простое с , где — это золотое сечение .
Хеширование строк переменной длины
Вышеизложенные методы применимы и в том случае, если необходимо рассматривать ключи, состоящие из нескольких слов, или ключи переменной длины.
Например, можно скомбинировать слова в одно при помощи сложения по модулю или операции « исключающее или ». Одним из алгоритмов, работающих по такому принципу, является хеш-функция Пирсона.
Хеширование Пирсона — алгоритм, предложенный Питером Пирсоном ( англ. Peter Pearson ) для процессоров с 8-битовыми регистрами, задачей которого является быстрое преобразование строки произвольной длины в хеш-код. На вход функция получает слово , состоящее из символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.
Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок :
h := 0 for each c in W loop index := h xor c h := T[index] end loop return h
Среди преимуществ алгоритма:
- простоту вычисления;
- отсутствие таких входных данных, для которых вероятность коллизии наибольшая;
- возможность модификации в идеальную хеш-функцию .
В качестве альтернативного способа хеширования ключей , состоящих из символов ( ), можно предложить вычисление
Идеальное хеширование
Идеальной хеш-функцией ( англ. perfect hash function ) называется такая функция , которая отображает каждый ключ из набора во множество целых чисел без коллизий . В математике такое преобразование называется инъективным отображением.
Описание
- Функция называется идеальной хеш-функцией для , если она инъективна на .
- Функция называется минимальной идеальной хеш-функцией для , если она является идеальной хеш-функцией и .
- Для целого функция называется -идеальной хеш-функцией (k-PHF) для , если для каждого имеем .
Идеальное хеширование применяется, если требуется присвоить уникальный идентификатор ключу без сохранения какой-либо информации о ключе. Пример использования идеального (или скорее -идеального) хеширования: размещение хешей, связанных с данными, хранящимися в большой и медленной памяти, в небольшой и быстрой памяти. Размер блока можно выбрать таким, чтобы необходимые данные считывались из медленной памяти за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах . Также идеальное хеширование используется для ускорения работы алгоритмов на графах, если представление графа не умещается в основной памяти .
Универсальное хеширование
Универсальным хешированием называется хеширование, при котором используется не одна конкретная хеш-функция, а происходит выбор хеш-функции из заданного семейства по случайному алгоритму . Универсальное хеширование обычно отличается низким числом коллизий, применяется, например, при реализации хеш-таблиц и в криптографии.
Описание
Предположим, что требуется отобразить ключи из пространства в числа . На входе алгоритм получает данные из некоторого набора размерностью . Набор заранее неизвестен. Как правило, алгоритм должен обеспечить наименьшее число коллизий , чего трудно добиться, используя какую-то определённую хеш-функцию. Число коллизий можно уменьшить, если каждый раз при хешировании выбирать хеш-функцию случайным образом. Хеш-функция выбирается из определённого набора хеш-функций, называемого универсальным семейством .
Методы борьбы с коллизиями
Коллизией (иногда конфликтом или столкновением) называется случай, при котором одна хеш-функция для разных входных блоков возвращает одинаковые хеш-коды.
Методы борьбы с коллизиями в хеш-таблицах
Большинство первых работ, описывающих хеширование, посвящено методам борьбы с коллизиями в хеш-таблицах. Тогда хеш-функции применялись при поиске текста в файлах большого размера. Существует два основных метода борьбы с коллизиями в хеш-таблицах:
- метод цепочек (метод прямого связывания);
- метод открытой адресации.
При использовании метода цепочек в хеш-таблице хранятся пары « связный список ключей» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» — «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется ключей и списков, средний размер хеш-таблицы составит . В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в раз.
При использовании метода открытой адресации в хеш-таблице хранятся пары «ключ» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; пара «ключ» — «хеш-код» сохраняется в таблице. В этом случае при поиске по таблице по сравнению со случаем, в котором используются связные списки, ссылки не используются, выполняется последовательный перебор пар «ключ» — «хеш-код», перебор прекращается после обнаружения нужного ключа. Последовательность, в которой просматриваются ячейки таблицы, называется последовательностью проб .
Криптографическая соль
Для защиты паролей и цифровых подписей от подделки создано несколько методов, работающих даже в том случае, если криптоаналитику известны способы построения коллизий для используемой хеш-функции. Одним из таких методов является добавление к входным данным так называемой криптографической «соли» — строки случайных данных; иногда «соль» добавляется и к хеш-коду. Добавление случайных данных значительно затрудняет анализ итоговых хеш-таблиц. Данный метод, к примеру, используется при сохранении паролей в UNIX-подобных операционных системах .
Применение хеш-функций
Хеш-функции широко используются в криптографии.
Хеш используется как ключ во многих структурах данных — хеш-таблицаx , фильтрах Блума и декартовых деревьях .
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять криптографически стойкие , применяемые в криптографии , так как на них накладываются дополнительные требования. Для того, чтобы хеш-функция считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:
- необратимость : для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных , для которого ;
- стойкость к коллизиям первого рода : для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N , для которого ;
- стойкость к коллизиям второго рода : должно быть вычислительно неосуществимо подобрать пару сообщений , имеющих одинаковый хеш.
Данные требования не являются независимыми:
- обратимая функция нестойка к коллизиям первого и второго рода;
- функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.
Не доказано существование необратимых хеш-функций, для которых вычисление какого-либо прообраза заданного значения хеш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей.
Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n бит в среднем за примерно вычислений хеш-функции. Поэтому n -битовая хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к .
Криптографические хеш-функции должны иметь лавинный эффект — при малейшем изменении аргумента значение функции сильно изменяется. В частности, значение хеша не должно давать утечки информации даже об отдельных битах аргумента. Это требование является залогом криптостойкости алгоритмов хеширования, хеширующих пользовательский пароль для получения ключа .
Хеширование часто используется в алгоритмах электронно-цифровой подписи, где шифруется не само сообщение, а его хеш-код, что уменьшает время вычисления, а также повышает криптостойкость. Также в большинстве случаев вместо паролей хранятся значения их хеш-кодов.
Контрольные суммы
Алгоритмы вычисления контрольных сумм — несложные, быстрые и легко реализуемые аппаратно алгоритмы, используемые для защиты данных от непреднамеренных искажений, в том числе — от ошибок аппаратуры. С точки зрения математики такие алгоритмы являются хеш-функциями, вычисляющими контрольный код. Контрольный код применяется для обнаружения ошибок, которые могут возникнуть при передаче и хранении информации.
Алгоритмы вычисления контрольных сумм по скорости вычисления в десятки и сотни раз быстрее, чем криптографические хеш-функции, и значительно проще в аппаратном исполнении.
Платой за столь высокую скорость является отсутствие криптостойкости — возможность легко «подогнать» сообщение под заранее известную контрольную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем разрядность криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.
Простейшим алгоритмом вычисления контрольной суммы является деление сообщения (входных данных) на 32- или 16-битовые слова с последующим суммированием слов. Такой алгоритм применяется, например, в протоколах TCP/IP .
Как правило, алгоритмы вычисления контрольных сумм должны обнаруживать типичные аппаратные ошибки, например, должны обнаруживать несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов так называемых « циклических избыточных кодов » удовлетворяет этим требованиям. К ним относится, например, алгоритм CRC32 , применяемый в устройствах Ethernet и в формате сжатия данных ZIP .
Контрольная сумма, например, может быть передана по каналу связи вместе с основным текстом (данными). На приёмном конце контрольная сумма может быть рассчитана заново и может сравниваться с переданным значением. Если будет обнаружено расхождение, то при передаче возникли искажения, и можно запросить повторную передачу.
Пример применения хеширования в быту — подсчёт количества чемоданов, перевозимых в багаже. Для проверки сохранности чемоданов не требуется проверять сохранность каждого чемодана, достаточно посчитать количество чемоданов при погрузке и выгрузке. Совпадение чисел будет означать, что ни один чемодан не потерян. То есть, число чемоданов является хеш-кодом.
Данный метод можно дополнить для защиты передаваемой информации от фальсификации (метод MAC ). В этом случае хеширование производится криптостойкой функцией над сообщением, объединённым с секретным ключом, известным только отправителю и получателю сообщения. Криптоаналитик, перехватив сообщение и значение хеш-функции, не сможет восстановить код, то есть не сможет подделать сообщение (см. имитозащита ).
Геометрическое хеширование
Геометрическое хеширование ( англ. geometric hashing ) — метод, широко применяемый в компьютерной графике и вычислительной геометрии для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар точек среди множества точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Хеш-таблица в данном случае является массивом с двумя или более индексами и называется «файлом сетки» ( англ. grid file ). Геометрическое хеширование применяется в телекоммуникациях при работе с многомерными сигналами .
Ускорение поиска данных
Хеш-таблицей называется структура данных , позволяющая хранить пары вида «ключ» — «хеш-код» и поддерживающая операции поиска, вставки и удаления элемента. Хеш-таблицы применяются с целью ускорения поиска, например, при записи текстовых полей в базе данных может рассчитываться их хеш-код, и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста, и сразу станет известно, в каком разделе их надо искать. То есть искать надо будет не по всей базе, а только по одному её разделу, а это ускоряет поиск.
Бытовым аналогом хеширования в данном случае может служить размещение слов в словаре в алфавитном порядке. Первая буква слова является его хеш-кодом, и при поиске просматривается не весь словарь, а только слова, начинающиеся на нужную букву.
Примечания
- , с. 256.
- ↑ .
- Herbert Hellerman. Digital Computer System Principles. N.Y.: McGraw-Hill, 1967, 424 pp.
- ↑ .
- Pearson, Peter K. (June 1990), (PDF) , Communications of the ACM , 33 (6): 677, doi : , (PDF) из оригинала 9 мая 2016 , Дата обращения: 21 февраля 2017
- Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger. (неопр.) . — Springer Berlin / Heidelberg, 2009. 24 июля 2011 года.
- Miltersen, Peter Bro (англ.) (PDF). 24 июня 2009 года.
- .
- Wolfson, H.J. & Rigoutsos, I (1997). от 13 марта 2012 на Wayback Machine 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 .
- Никлаус Вирт . Алгоритмы и структуры данных. Новая версия для Оберона. — М. : «ДМК Пресс», 2010. — ISBN 978-5-94074-584-6 .
Ссылки
![](https://cdn.wafarin.com/avatars/6a6f9ac08513a095b191a1f0789b03ac.png)
- 2020-05-28
- 2