Хеш-функція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Дональд Кнут відносить першу систематичну ідею хешування до співробітника 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», але для реальних даних такий метод підходить лише у тому випадку, якщо ключі не мають великої кількості нулів зліва чи справа. [4]

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

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

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

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

Другий метод полягає у виборі деякої цілої константи  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} .

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

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

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

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

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

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

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

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

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

Список алгоритмів[ред.ред. код]


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