Хеш-функція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Хеш-функція ставить у відповідність іменам ціле число від 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). Геометричне хешування також застосовується в телекомунікаціях при роботі з багатовимірними сигналами.

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

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

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

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

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

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

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


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