Файл: Функция хеширования.pdf

Введение

С хешированием сталкиваются едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.
Хеширование применяется для быстрого поиска в структурах данных и в криптографии, а также для проверки на наличия ошибок.
Хеширование это процесс получения уникального (чаще цифрового) идентификатора для объекта.
 

Хеширование

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

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

Примичание
Ранее были предложения назвать метод хеширования по русски - окрошка, а также рускоязычным эквивалентом термину хеширования – расстановка, но не один из них не прижился.

Хеш-функции

Пусть у нас есть множество X каких-то объектов. Текстовых файлов, чисел, бутылок пива... Ещё есть множество чисел Y(N) = {0, 1, 2, ..., N-1}. Имеем функцию f(x) = k, где x - объект из X, k - из Y(N). Такая функция будет зваться хеш-функцией (можно звать её также функцией хеширования). Она по сути разбивает X на N непересекающихся подмножеств, это разбиение имеет название хеширование.
Пример: X - целые неотрицательные числа, f(x) = x mod N (ищем остаток от деления). Эта хеш-функция называется методом деления. На практике метод деления используется в большинстве приложений, работающих с хешированием.

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

f(x) = x mod 4 (функция mod возвращает остаток от деления)

Ещё пример: X - опять целые неотрицательные числа. Функция f берёт первую цифру x. В этом случае N = 10.
Хеширование применяется для быстрого поиска в структурах данных и в криптографии. При этом хеш-функции, хорошие для первого, вряд ли хороши для второго применения, и наоборот. хеш-функции, применяемые в криптографии, также называются функциями криптографического хеширования. Как правило, хеш-функции в сфере структур довольно просты, функции криптографического хеширования имеют довольно сложное тело.

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

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

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

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

Хеш-таблицы

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

Разрешение коллизий

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

Метод цепочек.

Технология сцепления элементов состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i ; если таких элементов в множестве нет, в позиции i записан NULL. На рис. 2 демонстрируется реализация метода цепочек при разрешении коллизий. На ключ 002 претендуют два значения, которые организуются в линейный список.

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

Метод открытой адресации

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

Безопасное хранение паролей с помощью хеш-функций

Пусть есть у нас социальная сеть, база данных или прочее, где может быть вход по логину и паролю. Чтобы система проверила, правильно ли введён пароль, требуется где-то хранить пароли. Хранить пароль в открытом виде
не рекомендуется.
Причины:
- Любой файл можно открыть блокнотом и просмотреть.
- Если хранить в реестре, то также можно проследить обращение программы к реестру и обнаружить то место где хранятся пароли.
- Скомпилированную программу ( exe файл) можно вскрыть дизассемблегом(например ida pro) и отследить обращение к месту сравнения пароля(например soft-ice)

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

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

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

Контрольная сумма файла (хеш) — это определенное значение, которое рассчитывается по набору данных с использованием определенного алгоритма. Она помогает проверить целостность данных при их хранении и передаче.Если у двух файлов совпадает контрольная сумма, это значит, что эти файлы идентичны по содержанию, даже если по какой-то причине имеют разные названия.
Например вы скачали файл, а потом выяснили, что он дефектный (к примеру, программа, которой вы пытаетесь его открыть, выдает сообщение об ошибке, хотя остальные файлы этого же формата открывает «на ура»). Как проверить, был ли он дефектным изначально, или же произошли какие-то проблемы при скачивании? Для этого и нужна контрольная сумма файла.
Существуют различные алгоритмы хеширования для создания контрольных сумм. Скажем, программы-архиваторы используют так называемый циклический избыточный код (CRC). Он позволяет удостовериться, что распаковка файла из архива прошла без проблем, a полученный файл идентичен изначальному. Программа BitTorrent использует алгоритм SHA-1, чтобы проверять целостность загружаемых данных. Для проверки целостности скачанных файлов и поиска дубликатов файлов обычно используют алгоритм MD5.
Скажем, вы решили скачать дистрибутив операционной системы. Если при закачке произойдет какой-то сбой, операционная система может установиться «криво» или не установиться вообще. А контрольная сумма поможет определить, совпадает ли скачанный вами файл с изначальным. Для этих целей контрольную сумму обычно указывают на сайте, предоставляющем файлы для закачки. Вам нужно лишь узнать контрольную сумму скачанного вами файла и сравнить два значения. Если контрольные суммы совпадают, файлы идентичны.
Контрольная сумма определяется при помощи специальных программ. Одна из самых распространенных программ для проверки контрольных сумм файлов — HashTab