Хешування
Хешування (англ. Hashing) - перетворення вхідного масиву даних довільної довжини в вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, а їх результати називають хешем, хеш-кодом або дайджестом повідомлення (англ. message digest). Хешування застосовується для порівняння даних: якщо у двох масивів хеш-коди різні, масиви гарантовано розрізняються; якщо однакові - масиви, швидше за все, однакові. У загальному випадку однозначної відповідності між вихідними даними і хеш-кодом немає в силу того, що кількість значень хеш-функцій менше, ніж варіантів вхідного масиву; існує безліч масивів, що дають однакові хеш-коди - так звані колізії. Імовірність виникнення колізій відіграє важливу роль в оцінці якості хеш-функцій. Існує безліч алгоритмів хешування з різними характеристиками (розрядність, обчислювальна складність, крипостійкість і т. п.). Вибір тієї чи іншої хеш-функції визначається специфікою розв'язуваної задачі. Найпростішими прикладами хеш-функцій можуть служити контрольна сума або CRC.
Контрольні суми
Нескладні, вкрай швидкі й легко реалізовані апаратні алгоритми, використовувані для захисту від ненавмисних спотворень, в тому числі помилок апаратури. За швидкістю обчислення в десятки і сотні разів швидше, ніж криптографічні хеш-функції, і значно простіші в апаратній реалізації. Платою за таку високу швидкість є відсутність криптостійкості - легка можливість підігнати повідомлення під заздалегідь відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біта) нижче, ніж криптографічних хешів (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій. Найпростішим випадком такого алгоритму є розподіл повідомлення на 32 - або 16 - бітні слова і їх підсумовування, що застосовується, наприклад, в TCP / IP. Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька поспіль помилкових біт до заданої довжини. Сімейство алгоритмів т. з. «Циклічних надлишкових кодів» задовольняє цим вимогам. До них відноситься, наприклад, CRC32, застосовуваний в апаратурі Ethernet і у форматі архівованих файлів ZIP.
Криптографічні хеш-функції
Серед безлічі існуючих хеш-функцій прийнято виділяти криптографічно стійкі, застосовувані в криптографії. Для того, щоб хеш-функція H вважалася криптографічно стійкою, вона повинна задовольняти трьом основним вимогам, на яких засновано більшість застосувань хеш-функцій в криптографії:
- Незворотність: для заданого значення хеш-функції m повинно бути обчислювально нездійсненно знайти блок даних X, для якого H (X) = m.
- Стійкість до колізій першого роду: для заданого повідомлення M повинно бути обчислювально нездійсненно підібрати інше повідомлення N, для якого H (N) = H (M).
- Стійкість до колізій другого роду: має бути обчислювально нездійсненно підібрати пару повідомлень, що мають однаковий хеш.
Дані вимоги не є незалежними:
- Оборотна функція нестійка до колізій першого і другого роду. Функція, нестійка до колізій першого роду, нестійка до колізій другого роду; зворотне невірно.
- Слід зазначити, що не доведено існування необоротних хеш-функцій, для яких обчислення будь-якого прообразу заданого значення хеш-функції теоретично неможливо. Зазвичай знаходження зворотного значення є лише обчислювально складним завданням.
Атака «днів народження» дозволяє знаходити колізії для хеш-функцій з довжиною значень n бітів в середньому за приблизно 2n / 2 обчислень хеш-функції. Тому n-бітова хеш-функція вважається криптостійкою, якщо обчислювальна складність перебування колізій для неї близька до 2n / 2. Для криптографічних хеш-функцій також важливо, щоб при найменшій зміні аргументу значення функції сильно змінювалося (лавинний ефект). Зокрема, значення хешу не повинно давати витоку інформації навіть про окремі біти аргументу. Ця вимога є запорукою криптостійкості алгоритмів хешування, хешуючих пароль користувача для отримання ключа.
Застосування хеш - функцій
Хеш-функції також використовуються в деяких структурах даних - хеш-таблицяx, фільтрах Блума і декартових деревах. Вимоги до хеш-функції в цьому разі інші:
- хороша перемешіваемость даних
- швидкий алгоритм обчислення
Звірка даних
У загальному випадку це застосування можна описати, як перевірка деякою інформацією на ідентичність оригіналу, без використання оригіналу. Для звірки використовується хеш-значення перевіреної інформації. Розрізняють два основні напрямки цього застосування:
Перевірка на наявність помилок
Наприклад, контрольна сума може бути передана по каналу зв'язку разом з основним текстом. На приймальному кінці, контрольна сума може бути розрахована наново і її можна порівняти з переданим значенням. Якщо буде виявлено розбіжність, то це означає, що при передачі виникли спотворення і можна запросити повтор. Побутовим аналогом хешування в даному випадку може служити прийом, коли при переїздах у пам'яті тримають кількість місць багажу. Тоді для перевірки не потрібно згадувати про кожнe валізу, а досить їх порахувати. Збіг буде означати, що ні одну валізу не втрачено. Тобто, кількість місць багажу є його хеш-кодом. Даний метод легко доповнити до захисту від фальсифікації переданої інформації (метод MAC). У цьому випадку хешування проводиться криптостійкою функцією над повідомленням, об'єднаним з секретним ключем, відомим тільки відправнику і одержувачу повідомлення. Таким чином, криптоаналітик не зможе відновити код, за перехоплених повідомлень і значенням хеш-функції, тобто, не зможе підробити повідомлення.
Прискорення пошуку даних
Наприклад, під час запису текстових полів у базі даних може розраховуватися їх хеш код і дані можуть поміщатися в розділ, що відповідає цій хеш-функції. Тоді при пошуку даних треба буде спочатку обчислити хеш-код тексту і відразу стане відомо, в якому розділі їх треба шукати, тобто, шукати треба буде не по всій базі, а лише по одному її розділу (це сильно прискорює пошук). Побутовим аналогом хешування в даному випадку може служити розміщення слів у словнику за алфавітом. Перша літера слова є його хеш-кодом, і при пошуку ми переглядаємо не весь словник, а тільки потрібну літеру.
