Что такое хеш и для чего он нужен? Методы построения хэш-функций.

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

Многие задачи в области информационных технологий весьма критичны к объемам данных. Например, если нужно сравнить между собой два файла размером по 1 Кб и два файла по 10 Гб, то это совершенно разное время. Поэтому алгоритмы, позволяющие оперировать более короткими и емкими значениями, считаются весьма востребованными.

Одной из таких технологий является Хэширование, которое нашло свое применение при решении массы задач. Но, думаю вам, как обычному пользователю, все еще непонятно, что же это за зверь такой и для чего он нужен. Поэтому далее я постараюсь объяснить все наиболее простыми словами.

Примечание : Материал рассчитан на обычных пользователей и не содержит многих технических аспектов, однако для базового ознакомления его более, чем достаточно.

Что такое Хэш или Хэширование?

Начну с терминов.

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

Хэширование - это сам процесс преобразования исходных текстов.

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

Как видите, у терминов несколько образное описание, из которого сложно понять для чего это все нужно. Поэтому сразу приведу небольшой пример (об остальных применениях расскажу чуть позже). Допустим, у вас есть 2 файла размером 10 Гб. Как можно быстро узнать какой из них нужный? Можно использовать имя файла, но его легко переименовать. Можно смотреть даты, но после копирования файлов даты могут быть одинаковыми или в иной последовательности. Размер, как сами понимаете, мало чем может помочь (особенно, если размеры совпадают или вы не смотрели точные значения байтов).

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

Примечание : В связи с тем, что Хэш в компьютером мире и в интернете весьма известное понятие, то нередко все то, что имеет отношение к Хэшу, сокращают до этого самого слова. Например, фраза "у меня используется Хэш MD5" в переводе означает, что на сайте или где-то еще используется алгоритм хэширования стандарта MD5.

Свойства Хеш-функций

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

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

А теперь к самим свойствам Хэш-функций:

1. На вход может подаваться текст любого размера, а на выходе получается блок данных фиксированной длины. Это следует из определения.

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

3. Хорошая функция свертки должна иметь хорошее распределение. Согласитесь, что если размер выходного Хэша, к примеру, 16 байт, то если функция возвращает всего 3 разных значения для любых текстов, то толку от такой функции и этих 16 байт никакого (16 байт это 2^128 вариантов, что примерно равно 3,4 * 10^38 степени).

4. Как хорошо функция реагирует на малейшие изменения в исходном тексте. Простой пример. Поменяли 1 букву в файле размером 10 Гб, значение функции должно стать другим. Если же это не так, то применять такую функцию весьма проблематично.

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

6. Скорость вычисления Хэша. Какой толк от функции свертки, если она будет долго вычисляться? Никакой, ведь тогда проще данные файлов сравнивать или использовать иной подход.

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

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

Вот теперь можно переходить к вопросу "а для чего это все?".

Зачем нужен Хэш?

Основные цели у Хэш-функций всего три (вернее их предназначения).

1. Проверка целостности данных. В данном случае все просто, такая функция должна вычисляться быстро и позволять так же быстро проверить, что, к примеру, скачанный из интернета файл не был поврежден во время передачи.

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

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

Где и как применяется Хэш?

Как вы, вероятно, уже догадались Хэш применяется при решении очень многих задач. Вот несколько из них:

1. Пароли обычно хранятся не в открытом виде, а в виде Хэш-сумм, что позволяет обеспечить более высокую степень безопасности. Ведь даже если злоумышленник получит доступ к такой БД, ему еще придется немало времени потратить, чтобы подобрать к этим Хэш-кодам соответствующие тексты. Вот тут и важна характеристика "сложность восстановления исходных данных из значений Хэша".

Примечание : Советую ознакомиться со статьей пара советов для повышения уровня безопасности паролей .

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

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

4. Для различных алгоритмов, связанных с безопасностью. Например, Хэш применяется в электронных цифровых подписях.

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

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

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

Известные Хэш-функции

Самыми известными считаются следующие три Хэш-функции.

Хеширование

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами.

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

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

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

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

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

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

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

Хэш-таблицы

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

Основное отличие таблиц от других динамических множеств – вычисление адреса элемента по значению ключа.

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

Например, записная книжка. Страницы книжки помечены буквами. Страница, помеченная некоторой буквой, содержит фамилии, начинающиеся с этой буквы. Большое множество фамилий разбито на 28 подмножеств. При поиске книжка сразу открывается на нужной букве и поиск ускоряется.

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

Поиск в хэш-таблицах осуществляется в два этапа:

первый шаг – вычисление хэш-функции, которая преобразует ключ поиска в табличный адрес :

второй шаг – процесс разрешения конфликтов при обработке таких ключей.

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

Хэш-функции

Основное назначение хэш-функции - поставить в соответствие различным ключам по возможности разные не отрицательные целые числа.

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

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

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

хэш-функцию легко вычислить ;

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

на близких значениях аргумента хэш-функция принимает далекие друг от друга значения.

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

Пусть p ( key ) - плотность распределения запросов ключей. Тогда в идеальном случае плотность распределения запросов входов таблицыg ( H ( key )) д. быть такой, чтобы в среднем число элементов, кот. надо пройти в цепочках близнецов, было минимальным.

Пример .

Пусть имеется множество ключей

{0, 1, 4, 5, 6, 7, 8, 9, 15, 20, 30, 40}

и пусть таблица допускает 4 входа.

Можно построить хэш-функцию:

h (key ) = key % 4 .

Тогда получатся следующие адреса для входов

{0, 1, 2, 3} таблицы:

3·0,5+1,5·0,25+0,5·0,08+1·0,17 ≈ 2,1 элемента списка.

Пример с другой хэш-функцией.

В среднем потребуется пройти 4·1,5·0,25 = 1,5 элемента списка.

Если это информационно-поисковая система, то повысится ее производительность при поиске примерно на 25%.

Методы построения хэш-функций

Модульное хэширование

Простой, эффективный и часто используемый метод хэширования.

Размер таблицы выбирается в виде простого числа m и вычисляется хэш-функция как остаток от деления :

h (key ) = key % m

key – целое числовое значение ключа,

m - число хэш-значений (входов хэш-таблицы).

Такая функция называется модульной и изменяется от 0 до (m - 1 ).

Модульная хэш-функция на языке С++:

typedef int HashIndexType ;

HashIndexType Hash (int Key )

{ return Key % m ; }

Пример

key = {1, 3, 56, 4, 32, 40, 23, 7, 41,13, 6,7}

Пусть m = 5

h (key ) = {1, 3, 1, 4, 2, 0, 3, 2, 1, 3, 1, 2}

Важен выбор m .Чтобы получить случайное распределение ключей надо брать простое число.

Мультипликативный метод

Хэш-функция:

h(key) =

0 < A < 1 – константа.

12 mod 5 = 2 (остаток от деления 12 на 5).

5,04 mod1 = 0,04 (выделяется дробная часть)

Пример

key = 123456

m = 10000

A = 0,6180339887499 = 0,618…

h (key ) = =

Аддитивный метод

Используется для строк переменной длины (размер таблицы m равен 256).

{ HashIndexType h = 0;

while (*str)

h += (*str)++;

return h ;

Недостаток аддитивного метода: не различаются схожие слова и анаграммы, т.е. h (XY ) = h (YX )

Аддитивный метод , в котором ключом является символьная строка. В хеш-функции строка преобразуется в целое суммированием всех символов и возвращается остаток от деления на m (обычно размер таблицы m = 256).int h(char *key, int m) {int s = 0;while(*key)s += *key++;return s % m;}Коллизии возникают в строках, состоящих из одинакового набора символов, например, abc и cab .Данный метод можно несколько модифицировать, получая результат, суммируя только первый и последний символы строки-ключа.int h(char *key, int m) {int len = strlen(key), s = 0;if(len < 2) // Если длина ключа равна 0 или 1,s = key; // возвратить keyelse s = key + key;return s % m;}В этом случае коллизии будут возникать только в строках, например, abc и amc .

хеш-функция принимает ключ и вычисляет по нему адрес в таблице (адресом может быть индекс в массиве, к которому прикреплены цепочки), то есть она, например, из строки "abcd" может получить число 3, а из строки "efgh" может получить число 7 а потом первая структура цепочки берётся через hash, или через hash дальше идёт поиск по цепочке, пока в цепочке структур из hash не будет найдено "abcd", или в цепочке структур из hash не будет найдено "efgh" когда структура с "abcd" найдена, берутся и возвращаются остальные её данные, или она вообще вся возвращается (адрес её), чтобы можно было остальные данные из неё взять а цепочка структур создаётся потому, что многие разные ключи, имеют один и тот же адрес в таблице, то есть, например, хеш-функция для "abcd" может выдать 3 и для "zxf9" тоже может выдать 3, таким образом они сцепляются в цепочку, которая повисает на третьем индексе массива......

В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент.

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

Исключающее ИЛИ

Используется для строк переменной длины. Метод аналогичен аддитивному, но различает схожие слова. Заключается в том, что к элементам строки последовательно применяется операция «исключающее ИЛИ»

typedef unsigned char HashIndexType;

unsigned char Rand8;

HashIndexType Hash(char *str)

{ unsigned char h = 0;

while (*str) h = Rand8;

return h ; }

Здесь Rand 8 – таблица из 256 восьмибитовых случайных чисел.

размер таблицы <= 65536

typedef unsigned short int HashIndexType;

unsigned char Rand8;

HashIndexType Hash(char *str)

{ HashIndexType h; unsigned char h1, h2;

if (*str == 0) return 0;

h1 = *str; h2 = *str + 1; str++;

while (*str)

{ h1 = Rand8; h2 = Rand8;

str++; }

h = ((HashIndexType)h1 << 8) | (HashIndexType)h2;

return h % HashTableSize }

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

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

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

Однако время на генерирование случайных чисел будет слишком большим .

Можно использовать псевдослучайные числа.

// генератор псевдослучайных чисел

typedef int HashIndexType;

HashIndexType Hash(char *v, int m)

{ int h, a = 31415, b = 27183;

for(h = 0; *v != 0 ; v++, a = a*b % (m - l))

h = (a*h + *v) % m;

return (h < 0) ? (h + m) : h;

Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.

О себе

О хэшировании

Хэш-функцией называется всякая функция h:X -> Y , легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X - множество всех сообщений, Y - множество двоичных векторов фиксированной длины.

Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x 1 , x 2) двух переменных, где x 1 , x 2 и y - двоичные векторы длины m , n и n соответственно, причем n - длина свертки, а m - длина блока сообщения.
Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M 1 , M 2 ,.., M N применяют следующую последовательную процедуру вычисления свертки:

H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = H N

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

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

О статистических свойствах и требованиях

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

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

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

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

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

Это была теоретическая часть, которая пригодится нам в дальнейшем…

О популярных хэш-алгоритмах

Алгоритмы CRC16/32 - контрольная сумма (не криптографическое преобразование).

Алгоритмы MD2/4/5/6 . Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 - очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.

Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 - собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

Российский стандарт - ГОСТ 34.11-94 .

В следующей статье

Обзор алгоритмов MD (MD4, MD5, MD6).

Литература

А. П. Алферов, Основы криптографии.

Брюс Шнайер, Прикладная криптография.

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

Что это такое?

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

Характеристики

Рассмотрим ключевые характеристики исследуемых алгоритмов. В числе таковых:

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

В числе иных важнейших свойств хэш-функции:

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

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

Требования к хэш-функциям

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

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

Структура

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

В какой структуре может быть представлена используемая в подобных целях хеш-функция? Пример ее составления может быть таким: H (hash, то есть, хэш) = f (T (текст), H1), где H1 — алгоритм обработки текста T. Данная функция хеширует T таким образом, что без знания H1 открыть его как полноценный файл будет практически невозможно.

Использование хэш-функций на практике: скачивание файлов

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

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

Хэш-функция и ЭЦП

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

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

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

Проверка паролей

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

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

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

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

Коллизии хэш-функций

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

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

История появления

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

Популярные стандарты хеширования

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

В свою очередь, при шифровании достаточно широкое применение находят стандарты MD4 и MD5. Еще один популярный криптографический алгоритм — SHA-1. В частности, он характеризуется размером хэша 160 бит, что больше, чем у MD5 — данный стандарт поддерживает 128 бит. Есть российские стандарты, регулирующие использование хэш-функций, — ГОСТ Р 34.11-94, а также заменивший его ГОСТ Р 34.11-2012. Можно отметить, что величина хэша, предусмотренная алгоритмами, принятыми в РФ, составляет 256 бит.

Стандарты, о которых идет речь, могут быть классифицированы по различным основаниям. Например, есть те, что задействуют алгоритмы блочные и специализированные. Простота вычислений на основе стандартов первого типа часто сопровождается их невысокой скоростью. Поэтому в качестве альтернативы блочным алгоритмам могут задействоваться те, что предполагают меньший объем необходимых вычислительных операций. К быстродействующим стандартам принято относить, в частности, отмеченные выше MD4, MD5, а также SHA. Рассмотрим специфику специальных алгоритмов хеширования на примере SHA подробнее.

Особенности алгоритма SHA

Применение хэш-функций, базирующихся на стандарте SHA, чаще всего осуществляется в области разработки средств цифровой подписи документов DSA. Как мы отметили выше, алгоритм SHA поддерживает хэш 160 бит (обеспечивая так называемый «дайджест» последовательности символов). Изначально рассматриваемый стандарт делит массив данных на блоки по 512 бит. При необходимости, если длина последнего блока не дотягивает до указанной цифры, структура файла дополняется 1 и необходимым количеством нулей. Также в конце соответствующего блока вписывается код, фиксирующий длину сообщения. Рассматриваемый алгоритм задействует 80 логических функций, посредством которых обрабатывается 3 слова, представленные в 32 разрядах. Также в стандарте SHA предусмотрено использование 4 констант.

Сравнение алгоритмов хеширования

Изучим то, как соотносятся свойства хэш-функций, относящихся к разным стандартам, на примере сопоставления характеристик российского стандарта ГОСТ Р 34.11-94 и американского SHA, который мы рассмотрели выше. Прежде всего, следует отметить то, что алгоритм, разработанный в РФ, предполагает осуществление 4 операций по шифрованию в расчете на 1 цикл. Это соответствует 128 раундам. В свою очередь, в течение 1 раунда при задействовании SHA предполагается вычисление порядка 20 команд, при том что всего раундов 80. Таким образом, использование SHA позволяет в течение 1 цикла обработать 512 бит исходных данных. В то время как российский стандарт способен осуществить операции за цикл в 256 бит данных.

Специфика новейшего российского алгоритма

Выше мы отметили, что стандарт ГОСТ Р 34.11-94 был заменен более новым — ГОСТ Р 34.11-2012 «Стрибог». Исследуем его специфику подробнее.

Посредством данного стандарта могут быть реализованы, как и в случае с алгоритмами, рассмотренными выше, криптографические хеш-функции. Можно отметить, что новейший российский стандарт поддерживает блок входных данных в объеме 512 бит. Основные преимущества ГОСТ Р 34.11-2012:

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

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

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

Рассмотрим более подробно, каким образом исследуемые нами типы алгоритмов могут задействоваться в сфере криптографии. Ключевое требование к соответствующим функциям — стойкость к коллизиям, о которых мы сказали выше. То есть не должны формироваться повторяющиеся значения хеш-функции, если значения эти уже присутствуют в структуре соседствующего алгоритма. Прочим отмеченным выше критериям криптографические функции также должны соответствовать. Понятно, что всегда есть некая теоретическая возможность восстановления исходного файла на основе хэша, особенно если в доступе есть мощный вычислительный инструмент. Однако подобный сценарий предполагается свести к минимуму, благодаря надежным алгоритмам шифрования. Так, вычислить хэш-функцию будет очень сложно, если ее вычислительная стойкость соответствует формуле 2^{n/2}.

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

Итеративные схемы

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

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

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

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

Блочный алгоритм

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

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