Что такое хеш и хеширование — введение для начинающих программистов

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

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

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

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

 

Зачем нужно хеширование?

Каждый день объем данных в Интернете увеличивается во много раз, и постоянно усложняется процесс хранения этих данных. Если вы делаете небольшой сайт, итоговый объем данных может быть не таким уж и большим, но, тем не менее, даже его необходимо хранить, иметь к нему доступ и эффективно обрабатывать. Одной из наиболее распространенных структур данных, используемой для этой цели, является структура данных Массив (Array).

Теперь, внимание вопрос: если есть Массив, зачем нам нужна новая структура данных? Ответ на этот вопрос кроется в слове «эффективность». Хотя сохранение данных в массиве занимает небольшое время, поиск в нем занимает больше времени. Это время кажется небольшим, но если мы имеем дело с большим набором данных, оно значительно возрастает и делает использование типа данных Array (массив) неэффективным.

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

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

 

Из каких компонентов состоит хеширование?

Есть 3 базовых компонента, которые определяют хеширование:

1. Ключ: это входные данные. Ключом может выступать любой текст, строка или число, или их комбинации. Ключу, после обработки хеш-функцией, присваивается индекс в таблице (структуре) данных
2. Хеш-функция: от английского hash — буквально «превращать в фарш, смешивать«. Обрабатывает математическим алгоритмом входящие данные (ключ) и в результате возвращает индекс элемента в хеш-таблице (массиве данных)
3. Хеш-таблица: относится к структуре данных; хранит информацию ассоциативным образом (пары ключ-значение) в массиве. Здесь каждому значению данных присваивается свой собственный, и в идеале, уникальный индекс. Этот индекс также называют другими различными именами: хеш-индекс, хеш-сумма, или просто хеш.

 

 

Упрощенный пример процесса хеширования

Предположим, у нас есть массив данных из строк, в данном примере, из пар букв русского алфавита:

{"АБ", "ВГ", "ДЕ"}

и нам нужно сохранить его в таблице, используя хеширование.

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

Шаг №1: Мы знаем, что хеш-функция (некая математическая формула) используется для расчета индекса (хеш-значения) в таблице данных.

Шаг №2: Назначим простейший индекс каждой букве алфавита, например, так:

"А" = 1, "Б" = 2, "В" = 3 ... и т.д.

Шаг №3: Теперь мы можем получить числовое значение (индекс) каждой строки, путем суммирования всех значений (простейшая хеш-функция):

"АБ" = 1 + 2 = 3,
"ВГ" = 3 + 4 = 7,
"ДЕ" = 5 + 6 = 11
… и так далее

Шаг №4: Теперь предположим, что у нас есть таблица из 6 колонок для хранения этих строк (по количеству букв). Используемая в примере простейшая хеш-функция представляет собой сумму символов в таблице ключей. Мы можем вычислить расположение строки в массиве, используя деление по модулю на 6 (по количеству колонок). Деление по модулю — это остаток от деления исходных данных на максимальное количество итоговых данных. Например, в PHP это можно получить так:

<?php
/* $a % $b */echo (3 % 6); // 3
echo (7 % 6); // 1
echo (11 % 6); // 5
…
?>

Шаг №5: Итак, в хеш-таблицу мы сохраним следующие индексы:

"АБ" — 3 по модулю 6 = 3,
"ВГ" — 7 по модулю 6 = 1, и
"ДЕ" — 11 по модулю 6 = 5.

 

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

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

 

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

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

К другим видам хеш-функций можно отнести (от простых к более сложным):

1. Метод среднего (середины) квадрата
2. Использование многочлена (полинома)
3. Метод умножения
4. Алгоритм Пирсона
5. Универсальное хеширование (выбор случайного алгоритма из набора хеш-функций)
6. Двойное хеширование
7. MD5, SHA-1, SHA-2
8. алгоритм SHA-3 Keccak
9. и т.д.

 

Где используется структура хеш-данных и хеширование:

• Хеш используется в сложных структурах данных
• Хеш используется в базах данных для индексирования
• Хеш используется для проверки кэша
• Хеш можно использовать для безопасности пароля. Например, в базу данных сохраняется не сам пароль, а хеш пароля. На принципе хеширования часто строятся генераторы сложных паролей
• Хеш используется в криптографии
• В алгоритмах электронно-цифровой подписи
• При использовании алгоритма Рабина-Карпа (для поиска плагиата)
• В майнинге криптовалют, при блокчейне
• Для создания контрольных сумм файлов, хеш-сумм (например, в торрентах)
• Антивирусы хранят в базе не сами образцы вредоносных программ, а хеши этих вирусов
• Чтобы удостовериться в целостности переданных данных по SSH; протокола SSL/TLS и т.п.

 

Использование хеширования в криптографии

На ранних этапах становления Интернета для хеширования использовался алгоритм MD5 (Подпись Сообщения 5 — Message Digest 5) — довольно простой 128-битный алгоритм хеширования. MD5-хеш состоит из 32 цифр.

Пример использования в PHP:

<?php
echo md5("пароль");
// Результат: e242f36f4f95f12966da8fa2efd59992

 

Затем появился SHA-1 (Алгоритм безопасного хеширования 1 — Secure Hash Algorithm 1). Здесь используется сгенерированный 160-битный хеш, состоящий из 40 цифр.

Пример использования в PHP:

<?php
echo sha1("пароль");
// Результат: 5670b4358ae287fe8e74c2ff6f6293f905409077

С 2011 года алгоритмы MD5 и SHA-1 считаются небезопасными, из-за подверженности атакам с использованием «коллизий».

На сегодняшний день наиболее безопасными считаются алгоритмы хеширования 2й версии семейства SHA-2, а именно SHA-256 и SHA-512.

Примеры использования в PHP:

<?php
echo hash("sha256", "пароль");
// Результат: 2dbc574daca52689a24fb60e835f8c19a36400830df7350859dd32d1abaaec5d
echo hash("sha512", "пароль");
// Результат: f1d4b1ee047ec217264547763efb27c17c069eabc9f23124a223a1a859ca5cefe112a3e3cefe1cdc4331ecb70f9982f16dc67e250142476adae6ce9bc44f3a08
?>

 

Преимущества структуры хеш-данных и хеширования

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

Наглядный пример:

<?php
echo hash("sha256", "пароль");
// Результат: 2dbc574daca52689a24fb60e835f8c19a36400830df7350859dd32d1abaaec5d
echo hash("sha256", "Пароль");
// Результат: cb1a2074b3a027ffa7d7d9c54682c3835fffc7f6d620d8a38532f075cc2f17a0
// Во втором примере мы заменили одну букву — и получили совершенно другой результат!
?>

 

Недостатки структуры хеш-данных

1. Хеш неэффективен при большом количестве вероятных коллизий
2. Коллизий хешей практически не избежать при большом наборе возможных ключей
3. Хеш не допускает нулевых (null) значений
4. Уязвимость к атакам с использованием «коллизий» (для MD5 и SHA-1)

 

 

Вместо эпилога

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

Чувствовали ранее себя немного «потерянным» в сфере хеширования? Надеемся, что сегодняшний урок прибавил вам уверенности и понимания данной темы. Спасибо за внимание!