Перегляд вихідного коду сторінки Хеш-функція

[[Файл:Hash table 4 1 1 0 0 1 0 LL.svg|thumb|240px|Хеш-функція ставить у відповідність іменам ціле число від 0 до 15. Є суперечність (колізія) між «John Smith» та «Sandra Dee», яким відповідає однакове значення.]]
'''Хеш-фу́нкція'''<ref>{{Словники України on-line|хеш-функція}}</ref>, або '''геш-фу́нкція'''<ref>{{cite web 2  |title=Геш-функція. Картка даних терміну
 |url=http://uas.org.ua/ua/bank-danih/natsionalniy-bank-terminiv/znachennya-termina/?term-id=38741
 |work= Українське агентство зі стандартизації |accessdate=23.09.2017
 |archiveurl=https://archive.today/20170923124019/http://uas.org.ua/ua/bank-danih/natsionalniy-bank-terminiv/znachennya-termina/?term-id=38741 |archivedate=  23.09.2017
}}</ref><ref>Аналогічно до {{Англійсько-український словник з математики та інформатики Мейнаровича та Кратка|геш-таблиця}}</ref>&nbsp;— [[Підпрограма|функція]], що перетворює вхідні дані будь-якого (як правило великого) розміру в дані фіксованого розміру.

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

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

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

== Історія ==
[[Дональд Кнут]] приписує першу систематичну ідею гешування співробітнику IBM {{не перекладено|треба=Ханс Петер Лун|текст=Ханса Петера Луна|мова=en|є=Hans Peter Luhn}}, який запропонував геш-кодування у січні 1953 року.

У 1956 році {{не перекладено|треба=Арнольд Думи||мова=en|є=Arnold Dumey}} у своїй роботі «Computers and automation» першим представив концепцію гешування такою, якою її знає більшість програмістів у наш час. Думи розглядав гешування, як рішення «Проблеми словника», а також запропонував використовувати як геш-адресу залишок від ділення на просте число.<ref>{{Wirth.Algorithms and Data Structures}}</ref>

Першою значною роботою, яка була пов'язана з пошуком у великих файлах, була стаття {{не перекладено|Уеслі Пітерсон|Уеслі Пітерсона|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 у науці|1968]] році {{не перекладено|Роберт Морріс (кріптограф)|Роберт Морріс|en|Robert Morris (cryptographer)}} опублікував у ''Communications of the ACM'' великий огляд про гешування. Ця робота вважається публікацією, що вводить поняття про гешуванні в науковий обіг і остаточно закріпляє серед фахівців термін «геш».

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

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

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

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

== Види геш-функцій ==
Хороша геш-функція повинна задовольняти двом властивостям:
* Швидко обчислюватися;
* Мінімізувати кількість [[Колізія хеш-функції|колізій]]

Припустимо, для визначеності, що <math>K</math>&nbsp;— кількість ключів, а геш-функція <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 | Дональд Кнут. Мистецтво програмування}}

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

=== Геш-функції на основі ділення ===
Перший метод полягає у тому, що ми використовуємо як геш&nbsp;— залишок від ділення на <math> M </math>, де <math> M </math>&nbsp;— це кількість всіх можливих гешів:

<math> h (K) = K \mod M </math>

При цьому очевидно, що при парному <math> M </math> значення [[Функція (математика)|функції]] буде парним, при парному <math> K </math>. А непарним&nbsp;— при непарному, що може призвести до значного зсуву даних в файлах. Також не слід використовувати як <math> M </math> базу системи числення комп'ютера, оскільки геш-код буде залежати тільки від кількох цифр числа <math> K </math>, розташованих праворуч, що призведе до великої кількості колізій. На практиці зазвичай обирають [[Просте число|просте]] <math> M </math>&nbsp;— в більшості випадків цей вибір цілком задовільний.

Ще слід сказати про метод гешування, в основі якого полягає ділення на поліном по модулю два. У даному методі <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> h (x) = h_{m-1} ... h_{1} h_{0} </math>

При правильному виборі <math> P (x) </math> такий спосіб гарантує відсутність колізій між майже однаковими ключами. {{Sfn | Дональд Кнут. Мистецтво програмування}}

=== Мультиплікативна схема гешування ===
Другий метод полягає у виборі деякої цілої константи <math> A </math>, взаємно простої з <math> w </math>, де <math> w </math>&nbsp;— кількість можливих варіантів значень у вигляді машинного слова (в комп'ютерах [[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}}&nbsp;— алгоритм, запропонований Пітером Пірсоном ({{lang-en | Peter Pearson}}) для [[Центральний процесор|процесорів]] з 8-бітними регістрами, завданням якого є швидке обчислення геш-коду для рядка довільної довжини. На вхід функція отримує слово <math> W </math>, що складається з <math> n </math> символів, кожен розміром 1 байт, і повертає значення в діапазоні від 0 до 255. При цьому значення геш-коду залежить від кожного символу вхідного слова.

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

<syntaxhighlight lang = "pseudo">
h := 0
For each  c  in  W  loop
    index := h xor c
    h := T [index]
End loop'
Return  h
</syntaxhighlight>

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

Як альтернативний спосіб гешування <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>

== Застосування геш-функцій ==
Геш-функції широко використовуються в криптографії, а також у багатьох структурах даних&nbsp;— [[Хеш-таблиця|Геш-таблицях]], [[фільтр Блума|фільтрах Блума]] і [[Декартове дерево|декартових деревах]].

=== Криптографічні геш-функції ===
{{main|Криптографічна геш-функція}}
Серед великої кількості геш-функцій прийнято виділяти [[Криптографічна стійкість|криптографічно стійкі]], застосовувані в [[Криптографія|криптографії]], оскільки на них накладаються додаткові вимоги. Для того, щоб геш-функція <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}})&nbsp;— широко застосовуваний у [[комп'ютерна графіка|комп'ютерній графіці]] й [[Обчислювальна геометрія|обчислювальній геометрії]] метод для вирішення завдань на площині або в тривимірному просторі, наприклад, для знаходження найближчих пар в множині точок або для пошуку однакових зображень. Геш-функція в даному методі зазвичай отримує на вхід якийсь [[метричний простір]] і розділяє його, створюючи сітку з клітин. [[Хеш-таблиця|Таблиця]] у цьому випадку є масивом з двома або більше індексами і має назву файл сітки ({{lang-en|Grid file}}). Геометричне гешування також застосовується в телекомунікаціях при роботі з багатовимірними сигналами.

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

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

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

== Див. також ==
* [[Список алгоритмів#Криптографічні алгоритми|Список криптографічних алгоритмів]]
* [[Фільтр Блума]]&nbsp;— інтенсивно використовує геш-функції

''Деякі алгоритми гешування''
{{multicol}}
* [[HAVAL]]
* [[MD2]]
* [[MD4]]
* [[MD5]]
* [[N-Hash]]
{{multicol-break}}
* [[RIPEMD-160]]
* [[SHA]]
* [[Snefru]]
* [[Tiger (хеш-функція)|Tiger]]
* [[Whirlpool]]
{{multicol-end}}

== Примітки ==
{{reflist}}

== Джерела ==
* {{CLRS|chapter=11.3 Геш-функції}}
* {{TAOCP.v3}}

{{Compu-stub}}
{{Крипто навігація}}
{{Геш-функції та коди аутентифікації повідомлення}}

[[Категорія:Криптографія]]
[[Категорія:Геш-функції]]
[[Категорія:Виявлення та виправлення помилок]]
[[Категорія:Алгоритми пошуку]]
[[Категорія:Статті з прикладами коду]]