Хеш функція

{{{img}}}
Імя	Наталя
Прізвище	Бойко
По-батькові	Богданівна
Факультет	ФІС
Група	СН-41
Залікова книжка	ПК-06-ХХХ

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

Хеш функція

Колізія — це ситуація, коли h(K1) = h(K2). У цьому випадку, очевидно, необхідно знайти нове місце для зберігання даних. Очевидно, що кількість колізій необхідно мінімізувати. Хеш-функція повинна задовольняти двом вимогам: • її обчислення повинно виконуватися дуже швидко; • вона повинна мінімізувати число колізій. Отже, перша властивість хеш-функції залежить від комп'ютера, а друга — від даних. Якщо б всі дані були випадковими, то хеш-функції були б дуже прості (кілька бітів ключа, наприклад). Однак на практиці випадкові дані зустрічаються вкрай рідко, і доводиться створювати функцію, яка залежала б від усього ключа. Теоретично неможливо визначити хеш-функцію так, щоб вона створювала випадкові дані з реальних невипадкових файлів. Однак на практиці реально створити достатньо хорошу імітацію за допомогою простих арифметичних дій. Більш того, часто можна використовувати особливості даних для створення хеш-функцій з мінімальним числом колізій (меншим, ніж при істинно випадкових даних). Можливо, одним з найбільш очевидних і простих способів хешування є метод середини квадрата, коли ключ піднімається до квадрату і береться декілька цифр у середині. Тут і далі передбачається, що ключ спочатку заокруглюється до цілого числа, для здійснення з ним арифметичних операцій. Однак такий спосіб добре працює до моменту, коли немає великої кількості нулів зліва або справа. Численні тести показали хорошу роботу двох основних типів хешування, один з яких заснований на розподілі, а інший на множенні. Втім, це не єдині методи, які існують, більш того, вони не завжди є оптимальними.

Метод ділення

Метод ділення досить простий – використовується залишок від ділення на M:

h (K) = K mod M

Слід ретельно вибирати цю константу. Якщо взяти її рівною 100, а ключем буде рік народження, то розподіл буде дуже нерівномірним для ряду задач (ідентифікація гравців юнацької бейсбольної ліги, наприклад). Більш того, при парній константі значення функції буде парним при парній K і непарним - при непарному, що призведе до небажаного результату. Ще гірша ситуація, якщо M – це степінь числення комп'ютера, оскільки при цьому результат буде залежати тільки від декількох цифр ключа справа. Також можна показати, що M не повинно бути кратне трьом, оскільки при буквених ключах два з них, що відрізняються тільки перестановкою літер, можуть давати числові значення з різницею, кратній трьом. Наведені міркування приводять до думки, що краще використовувати просте число. У більшості випадків подібний вибір цілком задовільний. Інший приклад – ключ, що є символьним рядком С + +. Хеш-функція відображає цей рядок в ціле число за допомогою підсумовування першого і останнього символів і подальшого обчислення залишку від ділення на розмір таблиці. Ця хеш-функція призводить до колізії при однакових першому і останньому символах рядка. Наприклад, рядки «start» і «slant» будуть відображатися в індекс 29. Так само поводиться хеш-функція, підсумовує всі символи рядка. Рядки «bad» і «dab» перетворюються в один і той же індекс. Кращі результати дає хеш-функція, що виробляє перемішування бітів в символах. На практиці метод ділення – найпоширеніший.

Метод множення

Для мультиплікативного хешування використовується наступна формула [3]:

h (K) = [M * ((C * K) mod 1)]

Тут відбувається множення ключа на константу С, що лежить в інтервалі [0 .. 1]. Після цього береться дробова частина цього виразу і множиться на деяку константу M, обрану таким чином, щоб результат не вийшов за межі хеш-таблиці. Оператор [] повертає найбільше ціле, яке менше аргументу. Якщо константа С вибрана вірно, то можна досягти дуже хороших результатів, однак, цей вибір складно зробити. Дональд Кнут відзначає, що множення може іноді виконуватись швидше поділу. Мультиплікативний метод добре використовує те, що реальні файли невипадкові. Наприклад, часто безліч ключів представляють собою арифметичні прогресії, коли у файлі містяться ключі (K, K + d, K + 2d, ..., K + td). Мультиплікативний метод перетворює арифметичну прогресію у наближенні арифметичну прогресію h(K), h(K + d), h(K + 2d), ... різних хеш-значень, зменшуючи кількість колізій в порівнянні з випадковою ситуацією. Але, потрібно зауважити, що метод ділення володіє тією ж властивістю.

Динамічне хешування

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

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

Це забирає дуже багато ресурсів і виводить з ладу базу на деякий час. Існує техніка, що дозволяє динамічно змінювати розмір хеш-структури [5]. Це – динамічне хешування. Хеш-функція генерує так званий псевдоключ, який використовується лише частково для доступу до елементу. Іншими словами, генерується досить довга бітова послідовність, яка має бути достатньою для адресації всіх потенційно можливих елементів. У той час, як при статичному хешуванні потрібна була б дуже велика таблиця (яка зазвичай зберігається в оперативній пам'яті для прискорення доступу), тут розмір використаної пам'яті прямо пропорційний кількості елементів в базі даних. Кожен запис в таблиці зберігається не окремо, а в якомусь блоці. Ці блоки збігаються з фізичними блоками на пристрої зберігання даних. Якщо в блоці немає більше місця, щоб вмістити запис, то блок ділиться на два, а на його місце ставиться покажчик на два нові блоки. Завдання полягає в тому, щоб побудувати бінарне дерево, на кінцях гілок якого були б покажчики на блоки, а навігація здійснювалася б на основі псевдоключа. Вузли дерева можуть бути двох видів: вузли, які показують на інші вузли або вузли, які показують на блоки. Наприклад, нехай вузол має такий вигляд, якщо він показує на блок: | Zero | Null | | Bucket | Покажчик | | One | Null | Якщо ж він буде показувати на два інших вузла, то він буде мати такий вигляд:

| Zero | Адреса a | | Bucket | Null | | One | Адреса b |

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

Розширене хешування

Розширене хешування близьке до динамічного. Цей метод також передбачає зміну розмірів блоків у міру зростання бази даних, але це компенсується оптимальним використанням місця. Оскільки за один раз розбивається не більше одного блоку, накладні витрати достатньо малі [4]. Замість бінарного дерева розширене хешування передбачає список, елементи якого посилаються на блоки. Самі ж елементи адресуються по деякій кількості i бітів псевдоключа. При пошуку береться i бітів псевдоключа і через список знаходиться адреса шуканого блоку. Додавання елементів проводиться складніше. Спочатку виконується процедура, аналогічна пошуку. Якщо блок неповний, додається запис у нього і в базу даних. Якщо блок заповнений, він розбивається на два, записи перерозподіляються за описаним вище алгоритмом. У цьому випадку можливе збільшення числа біт, необхідних для адресації. Розмір списку подвоюється і кожному новоствореному елементу присвоюється покажчик. Таким чином, можлива ситуація, коли кілька елементів показують на один і той самий блок. Слід помітити, що за одну операцію вставки перераховуються значення не більше, ніж одного блоку. Видалення проводиться за таким же алгоритмом, тільки навпаки. Блоки, відповідно, можуть бути склеєні, а список – зменшений у два рази. Отже, основною перевагою розширеного хешування є висока ефективність, яка не падає при збільшенні розміру бази даних. Крім цього, розумно витрачається місце на пристрої зберігання даних, оскільки блоки виділяються тільки під реально існуючі дані, а список покажчиків на блоки має розміри, мінімально необхідні для адресації даної кількості блоків. За ці переваги розробник розплачується додатковим ускладненням програмного коду.

Застосування хешування

Одне з побічних застосувань хешування полягає в тому, що воно створює свого роду копію, “відбиток пальця” для повідомлення, текстового рядка, області пам'яті і т. п. Такий “відбиток пальця” може прагнути як до “унікальності”, так і до “схожості” (яскравий приклад – контрольна сума CRC). У цій якості однією з найважливіших галузей застосування є криптографія. Тут вимоги до хеш-функцій мають свої особливості. Крім швидкості обчислення хеш-функції потрібно значно ускладнити відновлення повідомлення (ключа) за хеш-адресою. Відповідно необхідно ускладнити находження повідомлення з тією ж хеш-адресою. При побудові хеш-функції односпрямованого характеру зазвичай використовують функцію стиснення (видає значення довжини n при вхідних даних більше довжини m і працює з кількома вхідними блоками). При хешуванні враховується довжина повідомлення, щоб виключити проблему появи однакових хеш-адрес для повідомлень різної довжини. Найбільшу популярність мають такі хеш-функції [1]: MD4, MD5, RIPEMD-128 (128 біт), RIPEMD-160, SHA (160 біт). У українському стандарті цифрового підпису використовується розроблена вітчизняними криптографами хеш-функція (256 біт) стандарту ГОСТ 34.311-95.

Хешування паролів

Хешування паролів – метод, що дозволяє користувачам запам`ятовувати ,наприклад, не 128 байт, тобто 256 шестнадцатірічний цифр ключа, а деяке осмислений вираз, слово чи послідовність символів, що називається паролем. Дійсно, при розробці будь-якого криптоалгоритмами слід враховувати, що в половині випадків кінцевим користувачем системи є людина, а не автоматична система. Це ставить питання про те, зручно, і взагалі чи реально людині запам'ятати 128-бітний ключ. Насправді межа запам'ятовуваності лежить на кордоні 8-12 подібних символів, а, отже, якщо ми будемо примушувати користувача оперувати саме ключем, тим самим ми практично змусимо його до запису ключа на будь-якому листку паперу або електронному носії, наприклад, в текстовому файлі. Це, звичайно, різко знижує захищеність системи. Для вирішення цієї проблеми були розроблені методи, які перетворюють осмислений рядок довільної довжини – пароль, у вказаний ключ заздалегідь заданої довжини. У переважній більшості випадків для цієї операції використовуються так звані хеш-функції. Хеш-функцією в даному випадку називається таке математичне або алгоритмічне перетворення заданого блоку даних, яке володіє наступними властивостями:

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

Ці властивості дозволяють подавати на вхід хеш-функції паролі, тобто текстові рядки довільної довжини на будь-якою національною мовою і, обмеживши область значень функції діапазоном 0 .. 2N-1, де N - довжина ключа в бітах, отримувати на виході досить рівномірно розподілені по області значення блоки інформації – ключі.

Список літературних джерел

• Чмора А., Современная прикладная криптография., М.: Гелиос АРВ, 2001.
• Ершов А.П., Избранные труды., Новосибирск: «Наука», 1994.
• http://www.optim.ru/cs/2000/4/bintree_htm/hash.asp
• http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Chapter11/node20.html
• http://planetmath.org/encyclopedia/Hashing.html
• http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html