Геш-функція

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

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

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

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

Історія[ред.ред. код]

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

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

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

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

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

Опис[ред.ред. код]

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

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

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

Види геш-функцій[ред.ред. код]

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

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

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

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

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

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

Геш-функції, на основі ділення[ред.ред. код]

Перший метод полягає у тому, що ми використовуємо у якості геша — залишок від ділення на  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) такий спосіб гарантує відсутність колізій між майже однаковими ключами. [3]

Мультиплікативна схема гешування[ред.ред. код]

Другий метод полягає у виборі деякої цілої константи  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». Одним з алгоритмів, що працюють за таким принципом, є геш-функція Пірсона.

Гешування Пірсона (англ. Pearson hashing) — алгоритм, запропонований Пітером Пирсоном (англ. 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} .

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

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

Геометричне гешування[ред.ред. код]

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

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

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

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

Примітки[ред.ред. код]

Література[ред.ред. код]

Див. також[ред.ред. код]

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

Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.
Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.