Що таке хеш і хешування — введення для програмістів-початківців

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

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

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

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

 

Навіщо потрібне хешування?

Щодня обсяг даних в Інтернеті збільшується у багато разів і постійно ускладнюється процес зберігання цих даних. Якщо ви робите невеликий сайт, підсумковий обсяг даних може бути не таким вже й великим, але навіть його необхідно зберігати, мати до нього доступ і ефективно обробляти. Однією з найпоширеніших структур даних, що використовується для цієї мети, є структура даних Масив (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)

 

 

Замість епілогу

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

Відчували раніше себе трохи «загубленим» у сфері хешування? Сподіваємося, що сьогоднішній урок додав вам впевненості та розуміння цієї теми. Дякуємо за увагу!