|
[[Файл:Hash table 4 1 1 0 0 1 0 LL.svg|thumb|240px|ГешХеш-функція ставить у відповідність іменам ціле число від 0 до 15. Є суперечність (колізія) між «John Smith» та «Sandra Dee», яким відповідає однакове значення.]]
'''ГешХеш-функція''' ('''Хеш-функція)''' — [[Підпрограма|функція]], що перетворює вхідні дані будь-якого (як правило великого) розміру в дані фіксованого розміру.
'''ГешуванняХешування''' (хешування, {{lang-en|hashing}}) — перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються '''гешхеш-функціями''' або '''функціями згортання''', а їхні результати називають гешемхешем, '''гешхеш-кодом''', гхеш'''еш-сумою''', або '''дайджестом повідомлення''' ({{lang-en|message digest}}).
ГешХеш-функція використовується зокрема у структурах даних — [[хеш-таблиця|гешхеш-таблицях]], широко використовується у програмному забезпеченні для швидкого пошуку даних. ГешХеш-функції використовуються для оптимізації таблиць та баз даних за рахунок того, що у однакових записів однакові значення гешхеш-функції. Такий підхід пошуку дублікатів ефективний у файлах великого розміру. Прикладом цього буде знаходження подібних ділянок у послідовностях [[ДНК]]. [[Криптографічна геш-функція|Криптографічна хеш-функція]] дозволяє легко перевірити, що деякі вхідні дані зіставляються із заданим значенням гешухешу, але, якщо вхідні дані невідомі, то навмисно важко відновити вхідне значення (або еквівалентну альтернативу), знаючи збережене значення гешхеш-функції.
Це використовується для забезпечення [[Цілісність інформації|цілісності]] переданих даних, і є будівельним блоком для [[HMAC]]s, які забезпечують [[Аутентифікація повідомлень|аутентифікацію повідомлень]].
ГешХеш-функції пов'язані (і їх часто плутають) з [[Контрольна сума|контрольною сумою]], контрольними цифрами, [[Відбитки пальців (інформатика)|відбитками пальців]], [[Рандомізація функції|рандомізацією функцій]], кодами, що виправляють помилки, і з шифрами. Хоча ці поняття певною мірою збігаються, кожен з них має свою власну область застосування і вимоги і є розробленим і оптимізованим по-різному.
== Історія ==
[[Дональд Кнут]] приписує першу систематичну ідею гешуванняхешування співробітнику IBM {{не перекладено|треба=Ханс Петер Лун|текст=Ханса Петера Луна|мова=en|є=Hans Peter Luhn}}, який запропонував гешхеш-кодування у січні 1953 року.
У 1956 році {{не перекладено|треба=Арнольд Думи||мова=en|є=Arnold Dumey}} у своїй роботі «Computers and automation» першим представив концепцію гешуванняхешування такою, якою її знає більшість програмістів у наш час. Думи розглядав гешуванняхешування, як рішення «Проблеми словника», а також запропонував використовувати як гешхеш-адресу залишок від ділення на просте число.{{sfn|Никлаус Вирт. Алгоритмы и структуры данных}}
Першою значною роботою, яка була пов'язана з пошуком у великих файлах, була стаття {{не перекладено|Уеслі Пітерсон|Уеслі Пітерсона|en|W. Wesley Peterson}} в ''IBM Journal of Research and Development'' 1957 року, в якій він визначив відкриту адресацію, а також вказав на погіршення продуктивності при видаленні. Через шість років була опублікована робота {{не перекладено|Вернер Бухгольц|Вернера Бухгольца|de|Werner Buchholz (Ingenieur)}}, у якій в значній мірі досліджувалися гешхеш-функції. Протягом кількох наступних років гешуванняхешування широко використовувалося, однак не було опубліковано жодної значної роботи.
У 1967 році гешуванняхешування в сучасному значенні згадано в книзі Херберта Хеллерман «Принципи цифрових обчислювальних систем»<ref> Herbert Hellerman. Digital Computer System Principles. N.Y .: McGraw-Hill, 1967, 424 pp.</ref>. У 1968 році {{не перекладено|Роберт Морріс (кріптограф)|Роберт Морріс|en|Robert Morris (cryptographer)}} опублікував у ''Communications of the ACM'' великий огляд про гешуванняхешування. Ця робота вважається публікацією, що вводить поняття про гешуванніхешуванні в науковий обіг і остаточно закріпляє серед фахівців термін «гешхеш».
До початку 1990-х років еквівалентом терміну «гешуванняхешування», завдяки роботам [[Єршов Андрій Петрович|Андрія Єршова]], використовувалося слово «расстановка» (рос.), а для колізій використовувався термін «конфликт» (рос.) (Єршов використовував «расстановку» з 1956, а також в російськомовному виданні книги [[Ніклаус Вірт|Ніклауса Вірта]] «Алгоритми та структури даних» (1989) використовується цей термін). Проте жоден з цих варіантів не прижився, і в літературі використовується переважно термін «гешуванняхешування».{{Sfn|Дональд Кнут. Мистецтво програмування}}
== Опис ==
ГешуванняХешування застосовується для побудови асоціативних масивів, пошуку дублікатів в серіях наборів даних, побудови унікальних ідентифікаторів для наборів даних, контрольного підсумовування з метою виявлення випадкових або навмисних помилок при зберіганні або передачі, для зберігання паролів в системах захисту (в цьому випадку доступ до області пам'яті, де знаходяться паролі, не дозволяє відновити сам пароль), при виробленні електронного підпису (на практиці часто підписується не саме повідомлення, а його гешхеш-образ).
У загальному випадку однозначної відповідності між вихідними даними і гешхеш-кодом немає в силу того, що кількість значень гешхеш-функцій менша, ніж число варіантів значень вхідного масиву. Існує безліч масивів з різним вмістом, що дають однакові гешхеш-коди — так звані колізії. Імовірність виникнення колізій відіграє важливу роль в оцінці якості гешхеш-функцій.
Існує безліч алгоритмів гешуванняхешування з різними властивостями (розрядність, обчислювальна складність, криптостійкість тощо). Вибір тієї чи іншої гешхеш-функції визначається специфікою розв'язуваної задачі. Найпростішими прикладами гешхеш-функцій можуть служити контрольна сума або CRC.
== Види гешхеш-функцій ==
Хороша гешхеш-функція повинна задовольняти двом властивостям:
* Швидко обчислюватися;
* Мінімізувати кількість [[Колізія хеш-функції | колізій]]
Припустимо, для визначеності, що <math>K</math> — кількість ключів, а гешхеш-функція <math> h(k)</math> має не більше <math>M</math> різних значень:
<math> \forall k \ 0 \leqslant h (k) < M </math>
Як приклад «поганої» гешхеш-функції можна привести функцію з <math> M = 1000 </math>, яка десятизначному [[Натуральні числа | натуральному числу]] <math> K </math> співставляє три цифри, обрані з середини двадцятизначного квадрата числа <math> K </math>. Здавалося б, значення гешхеш-кодів повинні рівномірно розподілитися між «000» і «999», але для реальних даних такий метод підходить лише у тому випадку, якщо ключі не мають великої кількості нулів зліва чи справа. {{Sfn | Дональд Кнут. Мистецтво програмування}}
Однак, існує декілька інших простих та надійних методів, на яких базується багато гешхеш-функцій.
=== ГешХеш-функції, на основі ділення ===
Перший метод полягає у тому, що ми використовуємо як гешхеш — залишок від ділення на <math> M </math>, де <math> M </math> — це кількість всіх можливих гешівхешів:
<math> h (K) = K \mod M </math>
При цьому очевидно, що при парному <math> M </math> значення [[Функція (математика)| функції]] буде парним, при парному <math> K </math>. А непарним — при непарному, що може призвести до значного зсуву даних в файлах. Також не слід використовувати як <math> M </math> базу системи числення комп'ютера, оскільки гешхеш-код буде залежати тільки від кількох цифр числа <math> K </math>, розташованих праворуч, що призведе до великої кількості колізій. На практиці зазвичай обирають [[Просте число | просте]] <math> M </math> — в більшості випадків цей вибір цілком задовільний.
Ще слід сказати про метод гешуванняхешування, в основі якого полягає ділення на поліном по модулю два. У даному методі <math> M </math> також повинна бути ступенем двійки, а бінарні ключі (<math> K = k_{n-1} k_{n-2} ... k_{0} </math>) мають вигляд поліномів. У цьому випадку як гешхеш-код беруться значення коефіцієнтів полінома, отриманого як залишок від ділення <math> K </math> на заздалегідь обраний поліном <math> P </math> ступеня <math> m </math>:
: <math> K (x) \mod P (x) = h_{m-1} x ^ {m-1} + \dots + h_{1} x + h_{0} </math>
При правильному виборі <math> P (x) </math> такий спосіб гарантує відсутність колізій між майже однаковими ключами. {{Sfn | Дональд Кнут. Мистецтво програмування}}
=== Мультиплікативна схема гешуванняхешування ===
Другий метод полягає у виборі деякої цілої константи <math> A </math>, взаємно простої з <math> w </math>, де <math> w </math> — кількість можливих варіантів значень у вигляді машинного слова (в комп'ютерах [[IBM PC-сумісний комп'ютер | IBM PC]] <math> 2 ^ {32} </math>). Тоді маємо змогу взяти гешхеш-функцію виду:
: <math> h (K) = \left [M \left \lfloor \frac {A} {w} * K \right \rfloor \right] </math>
У цьому випадку, на комп'ютері з двійковою системою числення, <math> M </math> являє собою ступінь двійки, а <math> h (K) </math> складатиметься зі старших бітів правої половини добутку <math> A * K </math>.
Серед переваг цих двох методів варто відзначити, що вони вигідно використовують те, що реальні ключі невипадкові. Наприклад, у тому випадку, якщо ключі являють собою [[Арифметична прогресія | арифметичну прогресію]] (припустимо послідовність назв «ім'я1», «ім'я2», «ім'я3»). Мультиплікативний метод відобразить арифметичну прогресію у наближену арифметичну прогресію різних гешхеш-значень, що зменшує кількість колізій у порівнянні з випадковою ситуацією.
Однією з варіацій даного методу є гешуванняхешування [[Послідовність Фібоначчі| Фібоначчі]], засноване на властивостях [[Золотий перетин | золотого перетину]]. Як <math> A </math> тут обирається найближче до <math> \varphi ^ {- 1} * w </math> ціле число, взаємно просте з <math> w </math>
=== ГешуванняХешування рядків змінної довжини ===
Вищевикладені методи застосовуються і в тому випадку, коли нам необхідно розглядати ключі, що складаються з декількох слів або ключі зі змінною довжиною. Наприклад, можна скомбінувати слова в одне за допомогою додавання за модулем <math> w </math> або операції «додавання по модулю 2». Одним з алгоритмів, що працюють за таким принципом, є гешхеш-функція Пірсона.
ГешуванняХешування Пірсона (англ. [[:en:Pearson hashing| Pearson hashing]]) — алгоритм, запропонований Пітером Пирсоном ({{lang-en | Peter Pearson}}) для [[Центральний процесор|процесорів]] з 8-бітними регістрами, завданням якого є швидке обчислення гешхеш-коду для рядка довільної довжини. На вхід функція отримує слово <math> W </math>, що складається з <math> n </math> символів, кожен розміром 1 байт, і повертає значення в діапазоні від 0 до 255. При цьому значення гешхеш-коду залежить від кожного символу вхідного слова.
Алгоритм можна описати таким псевдокодом, який отримує на вхід рядок <math> W </math> і використовує таблицю перестановок <math>T</math>
* простоту обчислення;
* не існує таких вхідних даних, для яких імовірність колізії найбільша;
* можливість модифікації в ідеальну гешхеш-функцію.
Як альтернативний спосіб гешуванняхешування <math> K </math> ключів, котрі складаються з <math> l </math> символів (<math> K = x_ {1} x_ {2} ... x_ {l} </math>), можна запропонувати обчислення
: <math> h (K) = (h_ {1} (x_ {1}) + h_ {2} (x_ {2}) + ... + h_ {l} (x_ {l})) \mod M </math>
== Застосування гешхеш-функцій ==
ГешХеш-функції широко використовуються в криптографії, а також у багатьох структурах даних — [[Хеш-таблиця|ГешХеш-таблицях]], [[фільтр Блума|фільтрах Блума]] і [[Декартове дерево|декартових деревах]].
=== Криптографічні гешхеш-функції ===
Серед безлічі існуючих гешхеш-функцій прийнято виділяти [[Криптографічна стійкість | криптографічно стійкі]], застосовувані в [[Криптографія | криптографії]], оскільки на них накладаються додаткові вимоги. Для того, щоб гешхеш-функція <math> H </math> вважалася криптографічно стійкою, вона повинна задовільняти трьом основним вимогам, на яких засновано більшість застосувань гешхеш-функцій в криптографії:
* '' Незворотність '': для заданого значення гешхеш-функції '' m '' має бути обчислювально неможливо знайти блок даних <math> X </math>, для якого <math> H (X) = m </math>.
* Стійкість ''[[Колізія хеш-функції|колізіям]] першого роду '': для заданого повідомлення '' M '' має бути обчислювально неможливо підібрати інше повідомлення '' N '', для якого <math> H (N) = H (M) </math>.
* Стійкість до ''колізій другого роду '': має бути обчислювально неможливо підібрати пару повідомлень <math> ~ (M, M ') </math>, що мають однаковий гешхеш.
Дані вимоги залежні один від одного:
* Функція, нестійка до колізій першого роду, нестійка до колізій другого роду; зворотне невірно.
Слід зазначити, що не доведене існування незворотних гешхеш-функцій, для яких обчислення будь-якого прообразу заданого значення гешхеш-функції теоретично неможливо. Зазвичай знаходження зворотного значення є лише обчислювально складним завданням.
[[Атака «днів народження»]] дозволяє знаходити колізії для гешхеш-функції з довжиною значень'' n '' бітів в середньому за приблизно <math> 2 ^ {n / 2} </math> обчислень гешхеш-функції. Тому ''n -''бітна гешхеш-функція вважається крипостійкою, якщо [[Теорія складності обчислень|обчислювальна складність]] знаходження колізій для неї близька до <math> 2 ^ {n / 2} </math>.
Для криптографічних гешхеш-функцій також важливо, щоб при щонайменшій зміні аргументу значення функції сильно змінювалося ([[Лавиновий ефект| лавинний ефект]]). Зокрема, значення гешухешу не повинно давати витоку інформації, навіть про окремі [[Біт|біти]] аргументу. Ця вимога є запорукою криптостійкості алгоритмів гешуванняхешування, гешуючиххешуючих пароль користувача для отримання [[Ключ (криптографія)| ключа]]. {{Sfn | Брюс Шнаейр | Прикладна криптографія. Протоколи, алгоритми, вихідні тексти на мові Сі}}
ГешуванняХешування часто використовується в алгоритмах електронно-цифрового підпису, де шифрується не саме повідомлення, а його гешхеш-код, що зменшує час обчислення, а також підвищує криптостійкість. Також в більшості випадків, замість паролів зберігаються значення їх гешхеш-кодів.
=== Геометричне гешуванняхешування ===
Геометричне гешуванняхешування ({{lang-en|Geometric hashing}}) — широко застосовуваний у [[комп'ютерна графіка|комп'ютерній графіці]] й [[Обчислювальна геометрія|обчислювальній геометрії]] метод для вирішення завдань на площині або в тривимірному просторі, наприклад, для знаходження найближчих пар в множині точок або для пошуку однакових зображень. ГешХеш-функція в даному методі зазвичай отримує на вхід якийсь [[метричний простір]] і розділяє його, створюючи сітку з клітин. [[Хеш-таблиця|Таблиця]] в даному випадку є масивом з двома або більше індексами і має назву файл сітки ({{lang-en|Grid file}}). Геометричне гешуванняхешування також застосовується в телекомунікаціях при роботі з багатовимірними сигналами.
=== Прискорення пошуку даних ===
[[Хеш-таблиця|Геш-таблиця]] — це структура даних, що дозволяє зберігати пари виду (ключ, гешхеш-код) і підтримує операції пошуку, вставки та видалення елементів.
Завданням гешхеш-таблиць є прискорення пошуку, наприклад, у випадку записів до текстових полів в базі даних може розраховуватися їх гешхеш код і дані можуть поміщатися у розділ, що відповідає цьому гешхеш-коду. Тоді при пошуку даних треба буде спочатку обчислити гешхеш-код тексту і відразу стане відомо, в якому розділі їх треба шукати, тобто, шукати треба буде не по всій базі, а тільки по одному її розділу (це сильно прискорює пошук).
Побутовим аналогом гешуванняхешування в даному випадку може служити розміщення слів у словнику за алфавітом. Перша літера слова є його гешхеш-кодом, і при пошуку ми переглядаємо не весь словник, а тільки потрібну літеру.
== Примітки ==
| 