Хеш-функція

Хеш-функція ставить у відповідність іменам ціле число від 0 до 15. Є суперечність (колізія) між «John Smith» та «Sandra Dee», яким відповідає однакове значення.

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

Хешування (гешування, англ. hashing) — перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями, або функціями згортання, а їхні результати називають хешем, хеш-кодом, хеш-сумою, або дайджестом повідомлення (англ. message digest).

Хеш-функція використовується зокрема у структурах даних — хеш-таблицях, широко вживаних у програмному забезпеченні для швидкого пошуку даних. Хеш-функції використовуються для оптимізації таблиць та баз даних користуючись з того, що в однакових записів однакові значення хеш-функції. Такий підхід пошуку дублікатів ефективний у файлах великого розміру. Прикладом цього буде знаходження подібних ділянок у послідовностях ДНК. Криптографічна геш-функція дозволяє легко перевірити, що деякі вхідні дані зіставляються із заданим значенням хешу, але, якщо вхідні дані невідомі, то навмисно важко відновити вхідне значення (або еквівалентну альтернативу), знаючи збережене значення хеш-функції. Це використовується для забезпечення цілісності переданих даних, і є будівельним блоком для HMACs, які забезпечують аутентифікацію повідомлень.

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

Історія

Дональд Кнут приписує першу систематичну ідею гешування співробітнику IBM Ханса Петера Луна, який запропонував геш-кодування у січні 1953 року.

У 1956 році Арнольд Думи у своїй роботі «Computers and automation» першим представив концепцію гешування такою, якою її знає більшість програмістів у наш час. Думи розглядав гешування, як рішення «Проблеми словника», а також запропонував використовувати як геш-адресу залишок від ділення на просте число.

Першою значною роботою, яка була пов'язана з пошуком у великих файлах, була стаття Уеслі Пітерсона в IBM Journal of Research and Development 1957 року, в якій він визначив відкриту адресацію, а також вказав на погіршення продуктивності при видаленні. Через шість років була опублікована робота Вернера Бухгольца, у якій в значній мірі досліджувалися хеш-функції. Протягом кількох наступних років гешування широко використовувалося, однак не було опубліковано жодної значної роботи.

У 1967 році гешування в сучасному значенні згадано в книзі Херберта Хеллерман «Принципи цифрових обчислювальних систем». У 1968 році Роберт Морріс опублікував у Communications of the ACM великий огляд про гешування. Ця робота вважається публікацією, що вводить поняття про гешуванні в науковий обіг і остаточно закріпляє серед фахівців термін «геш».

До початку 1990-х років еквівалентом терміну «гешування», завдяки роботам Андрія Єршова, використовувалося слово рос. «расстановка», а для колізій використовувався термін рос. «конфликт» (Єршов використовував «расстановку» з 1956, а також в російськомовному виданні книги Ніклауса Вірта «Алгоритми та структури даних» (1989) використовується цей термін). Проте жоден з цих варіантів не прижився, і в літературі використовується переважно термін «гешування».

Опис

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

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

Розроблено багато алгоритмів гешування з різними властивостями (розрядність, обчислювальна складність, криптостійкість тощо). Вибір тієї чи іншої геш-функції визначається специфікою розв'язуваної задачі. Найпростішими прикладами геш-функцій можуть служити контрольна сума або CRC.

Види геш-функцій

Хороша геш-функція повинна задовольняти двом властивостям:

• Швидко обчислюватися;
• Мінімізувати кількість колізій

Припустимо, для визначеності, що $K$ — кількість ключів, а геш-функція $h(k)$ має не більше $M$ різних значень:

$\forall k\ 0\leqslant h(k)<M$

Як приклад «поганої» геш-функції можна навести функцію з $M=1000$, яка десятизначному натуральному числу $K$ співставляє три цифри, обрані з середини двадцятизначного квадрата числа $K$. Здавалося б, значення геш-кодів повинні рівномірно розподілитися між «000» і «999», але для реальних даних такий метод підходить лише у тому випадку, якщо ключі не мають великої кількості нулів зліва чи справа.

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

Геш-функції на основі ділення

Перший метод полягає у тому, що ми використовуємо як геш — залишок від ділення на $M$, де $M$ — це кількість всіх можливих гешів:

$h(K)=K\mod M$

При цьому очевидно, що при парному $M$ значення функції буде парним, при парному $K$. А непарним — при непарному, що може призвести до значного зсуву даних в файлах. Також не слід використовувати як $M$ базу системи числення комп'ютера, оскільки геш-код буде залежати тільки від кількох цифр числа $K$, розташованих праворуч, що призведе до великої кількості колізій. На практиці зазвичай обирають просте $M$ — в більшості випадків цей вибір цілком задовільний.

Ще слід сказати про метод гешування, в основі якого полягає ділення на поліном по модулю два. У даному методі $M$ також повинна бути ступенем двійки, а бінарні ключі ($K=k_{n-1}k_{n-2}...k_{0}$) мають вигляд поліномів. У цьому випадку як геш-код беруться значення коефіцієнтів полінома, отриманого як залишок від ділення $K$ на заздалегідь обраний поліном $P$ ступеня $m$:

$K(x)\mod P(x)=h_{m-1}x^{m-1}+\dots +h_{1}x+h_{0}$

$h(x)=h_{m-1}...h_{1}h_{0}$

При правильному виборі $P(x)$ такий спосіб гарантує відсутність колізій між майже однаковими ключами.

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

Другий метод полягає у виборі деякої цілої константи $A$, взаємно простої з $w$, де $w$ — кількість можливих варіантів значень у вигляді машинного слова (в комп'ютерах IBM PC $2^{32}$). Тоді маємо змогу взяти геш-функцію виду:

$h(K)=\left[M\left\lfloor {\frac {A}{w}}*K\right\rfloor \right]$

У цьому випадку, на комп'ютері з двійковою системою числення, $M$ являє собою ступінь двійки, а $h(K)$ складатиметься зі старших бітів правої половини добутку $A*K$.

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

Однією з варіацій даного методу є гешування Фібоначчі, засноване на властивостях золотого перетину. Як $A$ тут обирається найближче до $\varphi ^{-1}*w$ ціле число, взаємно просте з $w$

Гешування рядків змінної довжини

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

Гешування Пірсона — алгоритм, запропонований Пітером Пірсоном (англ. Peter Pearson) для процесорів з 8-бітними регістрами, завданням якого є швидке обчислення геш-коду для рядка довільної довжини. На вхід функція отримує слово $W$, що складається з $n$ символів, кожен розміром 1 байт, і повертає значення в діапазоні від 0 до 255. При цьому значення геш-коду залежить від кожного символу вхідного слова.

Алгоритм можна описати таким псевдокодом, який отримує на вхід рядок $W$ і використовує таблицю перестановок $T$

h := 0
For each  c  in  W  loop
    index := h xor c
    h := T [index]
End loop'
Return  h

Серед переваг алгоритму слід зазначити:

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

Як альтернативний спосіб гешування $K$ ключів, котрі складаються з $l$ символів ($K=x_{1}x_{2}...x_{l}$), можна запропонувати обчислення

$h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l}))\mod M$

Застосування геш-функцій

Геш-функції широко використовуються в криптографії, а також у багатьох структурах даних — Геш-таблицях, фільтрах Блума і декартових деревах.

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

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

• Незворотність : для заданого значення геш-функції m має бути обчислювально неможливо знайти блок даних $X$, для якого $H(X)=m$.
• Стійкість колізіям першого роду : для заданого повідомлення M має бути обчислювально неможливо підібрати інше повідомлення N , для якого $H(N)=H(M)$.
• Стійкість до колізій другого роду : має бути обчислювально неможливо підібрати пару повідомлень $~(M,M')$, що мають однаковий геш.

Дані вимоги залежні один від одного:

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

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

Атака «днів народження» дозволяє знаходити колізії для геш-функції з довжиною значень n бітів в середньому за приблизно $2^{n/2}$ обчислень геш-функції. Тому n -бітна геш-функція вважається крипостійкою, якщо обчислювальна складність знаходження колізій для неї близька до $2^{n/2}$.

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

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

Геометричне гешування

Геометричне гешування (англ. Geometric hashing) — широко застосовуваний у комп'ютерній графіці й обчислювальній геометрії метод для вирішення завдань на площині або в тривимірному просторі, наприклад, для знаходження найближчих пар в множині точок або для пошуку однакових зображень. Геш-функція в даному методі зазвичай отримує на вхід якийсь метричний простір і розділяє його, створюючи сітку з клітин. Таблиця у цьому випадку є масивом з двома або більше індексами і має назву файл сітки (англ. Grid file). Геометричне гешування також застосовується в телекомунікаціях при роботі з багатовимірними сигналами.

Прискорення пошуку даних

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

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

Див. також

• Список криптографічних алгоритмів
• Фільтр Блума — інтенсивно використовує геш-функції

Деякі алгоритми гешування

HAVAL MD2 MD4 MD5 N-Hash

RIPEMD-160 SHA Snefru Tiger Whirlpool

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 11.3 Геш-функції. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)