Розглянуті нами алгоритми пошуку зазвичай ґрунтуються на абстрактній операції порівняння. З цього ряду суттєво виділяється метод розподільного пошуку, описаний у "Таблиці символів та дерева бінарного пошуку", при якому елемент з ключем i зберігається в i-ій позиції таблиці, що дозволяє звернутися до нього безпосередньо. При розподільному пошуку значення ключів використовуються як індекси масиву, а не операнди операції порівняння; сам метод заснований на тому, що ключі є різними цілими числами того ж діапазону, що і індекси таблиці. У цьому розділі ми розглянемо хешування (hashing) - розширений варіант розподільного пошуку, що застосовується в більш типових додатках пошуку, де ключі не мають настільки зручні властивості. Кінцевий результат застосування даного підходу зовсім не схожий на методи, засновані на порівнянні - замість переміщення структурами даних словника за допомогою порівняння ключів пошуку з ключами в елементах, ми намагаємося звернутися до елементів в таблиці безпосередньо, виконуючи арифметичне перетворення ключів на адреси таблиці.

Алгоритми пошуку, що використовують хешування, складаються з двох окремих елементів. Перший крок - обчислення хеш-функції (hash function), яка перетворює ключ пошуку на адресу таблиці. В ідеалі різні ключі повинні були б відображатися на різні адреси, але часто два або більше різних ключі можуть дати ту саму адресу в таблиці. Тому друга частина пошуку методом хешування - процес вирішення колізій (collision resolution), який обробляє такі ключі. В одному з методів вирішення конфліктів, який ми розглянемо в цьому розділі, використовуються зв'язкові списки, тому він знаходить безпосереднє застосування динамічних ситуаціях, коли важко заздалегідь передбачити кількість ключів пошуку. В інших двох методах вирішення колізій досягається висока продуктивністьпошуку, оскільки елементи зберігаються у фіксованому масиві. Ми розглянемо спосіб удосконалення цих методів, що дозволяє використовувати їх у тих випадках, коли не можна заздалегідь передбачити розміри таблиці.

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

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

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

Хеш-функції

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

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

Ймовірно, найпростіша ситуація, коли ключами є числа з плаваючою точкою з фіксованого діапазону. Наприклад, якщо ключі - числа, більші 0 та менші 1, їх можна просто помножити на M, округлити результат до меншого цілого числа та отримати адресу в діапазоні між 0 та M - 1; такий приклад показано на рис. 14.1. Якщо ключі більше s і менше t, їх можна масштабувати, віднімаючи s і розділивши на t-s , внаслідок чого вони потраплять у діапазон значень між 0 та 1, а потім помножити на M та отримати адресу у таблиці.

Рис. 14.1.

Для перетворення чисел з плаваючою точкою в діапазоні між 0 і 1 індекси таблиці, розмір якої дорівнює 97, виконується множення цих чисел на 97. даному прикладівідбулося три колізії: для індексів, рівних 17, 53 і 76. Хеш-значення визначаються старшими розрядами ключа, молодші розряди не відіграють жодної ролі. Однією з цілей розробки хеш-функції є усунення такого дисбалансу, щоб під час обчислення враховувався кожен розряд.

Якщо ключі є w-розрядними цілими числами, їх можна перетворити на числа з плаваючою точкою і розділити на 2 w для отримання чисел з плаваючою точкою в діапазоні між 0 та 1, а потім помножити на M, як у попередньому абзаці. Якщо операції з плаваючою точкою займають багато часу, а числа не настільки великі, щоб привести до переповнення, цей же результат може бути отриманий за допомогою цілих арифметичних операцій: потрібно помножити ключ на M, а потім виконати зсув вправо на w розрядів для поділу на 2 w (або якщо множення призводить до переповнення, виконати зсув, а потім множення). Такі методи марні для хешування, якщо ключі не розподілені по діапазону рівномірно, оскільки хеш-значення визначається тільки провідними цифрами ключа.

Найбільш простий і ефективний метод для w-розрядних цілих чисел - один з, мабуть, найбільш часто використовуваних методів хешування - вибір як розміру M таблиці простого числа і обчислення залишку від поділу на M, тобто. h(k) = k mod M для будь-якого цілого ключа k. Така функція називається модульною хеш-функцією. Її дуже просто обчислити (k % M у мові C++), і вона ефективна задля досягнення рівномірного розподілу значень ключів між значеннями, меншими M. Невеликий приклад показано на рис. 14.2.

Рис. 14.2.

У трьох правих стовпцях показаний результат хешування 16-розрядних ключів, наведених зліва, за допомогою таких функцій:

v % 97 (ліворуч)

v % 100 (в центрі) та

(int) (a * v) % 100 (праворуч),

де a = .618033. Розміри таблиці цих функцій відповідно дорівнюють 97, 100 і 100. Значення виглядають випадковими (оскільки випадкові ключі). Друга функція (v % 100 ) використовує лише дві крайні праві цифри ключів і тому для невипадкових ключів може бути низька продуктивність.

Модульне хешування застосовується і до ключів з плаваючою точкою. Якщо ключі належать невеликому діапазону, можна масштабувати їх числа з діапазону між 0 і 1, 2 w для отримання w-розрядних цілих значень, а потім використовувати модульну хеш-функцію. Інший варіант - просто використовувати як операнд модульної хеш-функції двійкове уявлення ключа (якщо воно доступне).

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

Основна причина вибору як розмір M хеш-таблиці простого числа для модульного хешування показана на рис. 14.3. У цьому прикладі символьних даних з 7-розрядним кодуванням ключ трактується як число з основою 128 - по одній цифрі кожного символу в ключі. Слово now відповідає числу 1816567, яке може бути записано як

оскільки в ASCII-коді символи n, o і w відповідають числа 1568 = 110 , 1578 = 111 і 1678 = 119 . Вибір розміру таблиці M = 64 для цього типу ключа невдалий, оскільки додавання до х значень, кратних 64 (або 128), не змінює значення х mod 64 – для будь-якого ключа значенням хеш-функції є значення останніх 6 розрядів цього ключа. Безперечно, хороша хеш-функція повинна враховувати всі розряди ключа, особливо для символьних ключів. Аналогічні ситуації можуть бути, коли M містить множник, що є ступенем 2. Найпростіший спосібуникнути цього - вибрати як M просте число.

Рис. 14.3.

У кожному рядку цієї таблиці наведено: 3-літерне слово, представлення цього слова в ASCII-коді як 21-бітове число у вісімковій та десятковій формах та стандартні модульні хеш-функції для розмірів таблиць 64 та 31 (два крайні справа стовпця). Розмір таблиці 64 призводить до небажаних результатів, оскільки для отримання хеш-значення використовуються тільки праві розряди ключа, а літери в словах звичайної мови розподілені нерівномірно. Наприклад, всім словам, що закінчуються на букву у, відповідає хеш-значення 57. І, навпаки, просте значення 31 викликає менше колізій у таблиці більш ніж удвічі меншого розміру.

Модульне хешування дуже просто реалізувати, за винятком того, що розмір таблиці має бути простим числом. Для деяких програм можна задовольнятися невеликим відомим простим числом або пошукати в списку відомих простих чисел таке, що близьке до необхідного розміру таблиці. Наприклад, числа рівні 2 t - 1 є простими при t = 2, 3, 5, 7, 13, 17, 19 та 31(і ні при яких інших значеннях t< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.

Рис. 14.4.

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

Інший варіант обробки цілих ключів - об'єднання мультиплікативного та модульного методів: потрібно помножити ключ на константу в діапазоні між 0 і 1, а потім виконати поділ за модулем M. Іншими словами, необхідно використовувати функцію . Між значеннями , M та ефективною основою системи числення ключа існує взаємозв'язок, який теоретично міг би призвести до аномальної поведінки, але якщо використовувати довільне значення a, у реальному додатку навряд чи виникне будь-яка проблема. Часто як a вибирають значення ф = 0,618033... (золотий переріз).

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

У багатьох додатках, у яких використовуються таблиці символів, ключі є числами і обов'язково є короткими; Найчастіше це алфавітно-цифрові рядки, які можуть бути дуже довгими. Ну і як обчислити хеш-функцію для такого слова, як averylongkey?

У 7-розрядному ASCII-коді цьому слову відповідає 84-розрядне число \begin(align*) 97 \cdot 128^(11) &+ 118 \cdot 128^(10) + 101 \cdot 128^(9) + 114 \ cdot 128^(8) + 121 \cdot 128^(7)\\ &+ 108 \cdot 128^(6) + 111 \cdot 128^(5) + 110 \cdot 128^(4) + 103 \cdot 128 ^(3)\\ &+ 107 \cdot 128^(2) + 101 \cdot 128^(1) + 121 \cdot 128^(0), \end(align*),

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

Щоб обчислити модульну хеш-функцію для довгих ключів, вони перетворюються на фрагмент за фрагментом. Можна скористатися арифметичними властивостями функції модуля та використовувати алгоритм Горнера (див. розділ 4.9 "Абстрактні типи даних"). Цей метод ґрунтується на ще одному способі запису чисел, що відповідають ключам. Для прикладу, що розглядається, запишемо наступне вираз: \begin(align*) ((((((((((((97 \cdot 128^(11) &+ 118) \cdot 128^(10) + 101) \cdot 128^( 9) + 114) \cdot 128^(8) + 121) \cdot 128^(7)\\ &+ 108) \cdot 128^(6) + 111) \cdot 128^(5) + 110) \cdot 128^(4) + 103) \cdot 128^(3)\\ &+ 107) \cdot 128^(2) + 101) \cdot 128^(1) + 121. \end(align*)

Тобто десяткове число, яке відповідає символьному кодуванню рядка, можна обчислити при перегляді його зліва направо, помножуючи накопичене значення на 128, а потім додаючи кодове значення наступного символу. У разі довгого рядка цей спосіб обчислення врешті-решт приведе до числа, більшого за те, яке взагалі можна представити в комп'ютері. Однак це число і не потрібно, оскільки потрібно лише (невеликий) залишок від його поділу на M. Результат можна отримати, навіть не зберігаючи велике накопичене значення, т.к. у будь-який момент обчислення можна відкинути число, кратне M - при кожному виконанні множення і додавання потрібно зберігати лише залишок від розподілу по модулю M. Результат буде таким же, як у нас була можливість обчислити довге число, а потім виконувати поділ (див. вправа 14.10). Це спостереження веде до безпосереднього арифметичного способу обчислення модульних хеш-функцій довгих рядків– див. програму 14.1. У цій програмі використовується ще одне, останнє хитрощі: замість основи 128 у ній використовується просте число 127. Причина цієї зміни розглядається в наступному абзаці.

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

M = 96 та a = 128 (вгорі),

M = 97 та a = 128 (в центрі) та

M = 96 та a = 127 (внизу)

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

У програмі 14.1 показаний один із способів зробити це: використання простої основи замість ступеня 2 та цілого числа, що відповідає ASCII-подання рядка. На рис. 14.5 рис. 14.5 показано, як ця зміна покращує розподіл для типових рядкових ключів. Теоретично хеш-значення, створені програмою 14.1, можуть давати погані результати для розмірів таблиці, які є кратними 127 (хоча на практиці це, швидше за все, буде майже непомітно); для створення рандомізованого алгоритму можна було б вибрати значення множника навмання. Ще ефективніший підхід - використання випадкових значень коефіцієнтів у обчисленні та різних випадкових значень для кожної цифри ключа. Такий підхід дає рандомізований алгоритм, що називається універсальним хешуванням (universal hashing).

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

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

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

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

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

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

Що таке Хеш чи Хешування?

Почну із термінів.

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

Хешування- це процес перетворення вихідних текстів.

Хеш, Хеш-код, Значення Хеш, Хеш-сума- це вихідне значення Хеш-функції, тобто отриманий фіксований блок довжини.

Як бачите, терміни мають дещо образний опис, з якого складно зрозуміти для чого це все потрібно. Тому відразу наведу невеликий приклад (про інші застосування розповім трохи пізніше). Допустимо, у вас є 2 файли розміром 10 Гб. Як можна швидко дізнатися який із них потрібний? Можна використовувати ім'я файлу, але його можна легко перейменувати. Можна дивитися дати, але після копіювання файлів дати можуть бути однаковими або в іншій послідовності. Розмір, як самі розумієте, мало чим може допомогти (особливо якщо розміри збігаються або ви не дивилися точні значення байтів).

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

Примітка: У зв'язку з тим, що Хеш у комп'ютерному світі та в інтернеті дуже відоме поняття, то нерідко все те, що має відношення до Хеш, скорочують до цього самого слова Наприклад, фраза "у мене використовується хеш MD5" в перекладі означає, що на сайті або десь ще використовується алгоритм хешування стандарту MD5.

Властивості Хеш-функцій

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

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

А тепер до самих властивостей Хеш-функцій:

1. На вхід може подаватися текст будь-якого розміру, а виході виходить блок даних фіксованої довжини. Це випливає з визначення.

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

3. Хороша функціязгортки повинен мати хороший розподіл. Погодьтеся, що якщо розмір вихідного Хеша, наприклад, 16 байт, то якщо функція повертає всього 3 різних значення для будь-яких текстів, то користі від такої функції і цих 16 байт ніякого (16 байт це 2^128 варіантів, що приблизно дорівнює 3, 4 * 10 ^ 38 ступеня).

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

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

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

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

8. Відкрито або закрито вихідний код такої функції. Якщо код не є відкритим, складність відновлення даних, а саме криптостійкість, залишається під питанням. Почасти, це проблема як із шифруванням.

Ось тепер можна переходити до питання "а навіщо це все?"

Навіщо потрібний Хеш?

Основні цілі у Хеш-функцій лише три (вірніше їх призначення).

1. Перевірка цілісності даних. В даному випадку все просто, така функція повинна обчислюватися швидко і дозволяти так само швидко перевірити, що, наприклад, завантажений з інтернету файл не пошкоджено під час передачі.

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

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

Де і як застосовується хеш?

Як ви, мабуть, вже здогадалися Хеш застосовується при вирішенні багатьох завдань. Ось кілька із них:

1. Паролі зазвичай зберігаються не у відкритому вигляді, а у вигляді Хеш-сум, що дозволяє забезпечити більш високий рівень безпеки. Адже навіть якщо зловмисник отримає доступ до такої БД, йому ще доведеться витратити чимало часу, щоб підібрати до цих Хеш-кодів відповідні тексти. Ось тут і важливою є характеристика "складність відновлення вихідних даних із значень Хеша".

Примітка: Раджу ознайомитися зі статтею пари порад для підвищення рівня безпеки паролів

2. У програмуванні, включаючи бази даних. Звичайно ж, найчастіше йдеться про структури даних, що дозволяють здійснювати швидкий пошук. Суто технічний аспект.

3. Під час передачі даних через мережу (включаючи Інтернет). Багато протоколів, таких як TCP/IP, включають спеціальні перевірочні поля, що містять Хеш-суму вихідного повідомлення, щоб якщо десь стався збій, то це не вплинуло на передачу даних.

4. Для різних алгоритмів, пов'язаних із безпекою. Наприклад, Хеш застосовується в цифрових електронних підписах.

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

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

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

Відомі Хеш-функції

Найвідомішими вважаються наступні три хеш-функції.

Хеш-функція- це функція, що перетворює дані (файл або документ) на короткий цифровий код.

Наприклад, перетворює текст
"Північна філія РГУІТП"
у код
745

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

Елементи хешу не стоять у якомусь конкретному порядку. Можете розглядати їх як стопку бібліографічних карток. Верхня половина кожної картки – це ключ, а нижня – значення. Щоразу, коли ви поміщаєте в хеш значення, створюється нова картка. Коли потрібно змінити значення, ви вказуєте ключ і Perl знаходить необхідну картку. Тому порядок карток, насправді, ролі не грає. Perl зберігає всі картки (тобто пари ключ-значення) в особливому внутрішньому порядку, який полегшує пошук конкретної картки, тому при пошуку не доводиться переглядати всі пари. Порядок зберігання карток змінювати не можна, тому навіть не намагайтеся.

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

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

хеш-функція має бути чутливою до всіляких змін у тексті М, таким як вставки, викиди, перестановки тощо;

хеш-функція повинна мати властивість незворотності, тобто завдання підбору документа М", який мав би необхідним значенням хеш-функції, повинна бути обчислювально нерозв'язна;

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

Наприклад,сума значень ASCII-кодів символів - 65(A)+66(B)+67(С)=198. У ідеалі значення хеш-функції має бути унікальним, тобто. число 198 має повертатися лише ABC. На практиці це досягається далеко не завжди (випадок, коли дві різні послідовності символів мають один і той же хеш, звуться колізією). Іноді на хеш-функцію накладають умова незворотності: тобто. за значенням не можна відновити вихідний рядок. Класичний приклад такої функції: MD5, яку використовують для перевірки цілісності завантажених ISO-образів. Для MD5 і подібних колізії - явище дуже негативне: воно знижує "ступінь незворотності" хеш-функції та дозволяє, наприклад, підібрати пароль, знаючи його MD5-хеш.
Криптографічні хеш-функції поділяються на два класи:

Хеш-функції без ключа (MDC (Modification (Manipulation) Detect Code) - коди),

- хеш- функціїcключем(MAC (Message Authentication Code) - коди).

Хеш-функції без ключа поділяються на два підкласи:

Слабкі хеш-функції,

Сильні хеш-функції.

Слабкою хеш-функцією називається одностороння функція H(x), що задовольняє наступним умовам:

1) аргумент х може бути рядком біт довільної довжини;

2) значення H(x) має бути рядком біт фіксованої довжини;

3) значення H(x) легко обчислити;

4) для будь-якого фіксованого x обчислювально неможливо знайти інший

Для дуже великої кількості технологій безпеки (наприклад, аутентифікації, ЕЦП) застосовуються односторонні функції шифрування, також хеш-функціями. Основне призначення подібних функцій – отримання повідомлення довільного розміру його дайджеста – значення фіксованого розміру. Дайджест може бути використаний як контрольної сумивихідного повідомлення, забезпечуючи в такий спосіб (при використанні відповідного протоколу) контроль цілісності інформації. Основні властивості хеш-функції:

1. на вхід хеш-функції подається повідомлення довільної довжини;
2. на виході хеш-функції формується блок даних фіксованої довжини;
3. значення на виході хеш-функції розподілені за рівномірним законом;
4. при зміні одного біта на вході хеш-функції суттєво змінюється вихід.

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

1. якщо ми знаємо значення хеш-функції h, то задача знаходження повідомлення M такого, що Н(М) = h, має бути обчислювально складною;
2. при заданому повідомленні M завдання знаходження іншого повідомлення M', такого, що Н(М) = H(M'), має бути обчислювально важким.

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

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

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

Якщо згадати, наскільки рандомізують вхідне повідомлення блокові шифри, можна як функцію хеш-перетворення використовувати якийсь блоковий шифр. Те, що блокові шифри є оборотними перетвореннями, не суперечить властивостям хеш-функції, оскільки блоковий шифр необоротний за ключом шифрування, і, якщо в якості ключа шифрування використовувати вихід попереднього кроку хеш-перетворення, а в якості повідомлення, що шифрується, черговий блок повідомлення (або навпаки ), можна отримати хеш-функцію з хорошими криптографическими характеристиками. Такий підхід використаний, наприклад, у російському стандарті хешування - ГОСТ Р 34.11-94. Ця хеш-функція формує 256-бітне вихідне значення, використовуючи як перетворюючу операцію блоковий шифр ГОСТ 28147-89 (рис.2.17). Функція хешування H отримує вхід хеш, отриманий на попередньому кроці (значення h 0довільне початкове число), а також черговий блок повідомлення m i. Її внутрішня структура представлена ​​рис.2.18. Тут у блоці шифруючого перетворення для модифікації h iв s iвикористовується блоковий шифр ГОСТ 28147-89. Перемішує перетворення являє собою модифіковану перестановку Фейштеля. Для останнього блоку m N(N – загальна кількість блоків повідомлення) виконується набивання до розміру 256 біт з додаванням істинної довжини повідомлення.

Основним недоліком хеш-функцій на основі блокових шифрів є невисока швидкість їхньої роботи. Тому було спроектовано ряд спеціалізованих алгоритмів, які, забезпечуючи аналогічну стійкість до атак, виконують набагато меншу кількість операцій над вхідними даними та забезпечують більшу швидкість роботи. Прикладами таких алгоритмів є: MD2, MD4, MD5, RIPEMD – 160, SHA. Розглянемо докладніше структуру алгоритму хешування SHA (Secure Hash Algorithm), який описаний у стандарті SHS та забезпечує безпеку електронної цифрового підпису DSA, формуючи 160-бітний дайджест повідомлення.

Спочатку повідомлення розбивається на блоки завдовжки 512 біт. Якщо довжина повідомлення кратна 512, до останнього блоку приписується праворуч 1, після чого він доповнюється нулями до 512 біт. В кінці останнього блоку записується код довжини повідомлення. В результаті повідомлення набуває вигляду n 512-розрядних блоків M 1 , M 2 ..., M n .

Алгоритм SHAвикористовує 80 логічних функцій f 0 , f 1 , …, f 79 , які здійснюють операції над трьома 32-розрядними словами (B, C, D):

В алгоритмі використовуються також спеціальним чином ініціалізовані 4 константи K i і 5 початкових значень H i.

Ділимо масив M на групи з 16 слів W 0, W 1, ..., W 15 (W 0 найлівіше слово).
Для t= 16 - 79 W t = S 1 (W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16)
S k означає операцію циклічного зсуву вліво kрозрядів.
Нехай тепер A = H 0, B = H 1, C = H 2, D = H 3, E = H 4 .
for t= 0 to 79 do
TEMP = S 5 (A) + f t(B, C, D) + E + W t + K i.
E = D; D = C; C = S 30(B); B = A; A = TEMP;
Нехай H0 = H0 + A; H1 = H1+B; H 2 = H 2 + C; H3 = H3+D; H4 = H4+E.

Графічно один цикл SHA представлений рис.2.19.

В результаті обробки масиву М буде отримано 5 слів H0, H1, H2, H3, H4 із загальною довжиною 160 біт, які і утворюють дайджест повідомлення.

З наведених даних ясно, що складність американського стандарту хешування нижче, ніж у російського. Російський стандарт передбачає виконання чотирьох шифрувань за один цикл вироблення хеша, або загалом 128 раундів. Кожен раунд шифрування вимагає приблизно півтора десятка елементарних машинних операцій, що суттєво збільшує витрати машинного часу на виконання лінійних операцій, що перемішують. Один раунд вироблення хешу SHA набагато простіше: він весь може бути реалізований приблизно за 15-20 команд, загальна кількість раундів всього 80, і за один цикл вироблення хешу обробляється вдвічі більше вихідних даних - 512 проти 256 у ГОСТ P34.ll - 94. Таким Таким чином, можна припустити, що швидкодія програмних реалізацій SHA буде приблизно в 3-6 разів швидше, ніж у вітчизняного стандарту.

Основне завдання хеш-функцій – створення дайджестів, унікальних для конкретного документа. Якщо для двох різних вхідних блоків хеш-функція дає однаковий дайджест, така ситуація називається хеш-колізією. З теореми, що має назву «парадокс днів народження», випливає, що для n-бітного хеш-значення необхідно в середньому. n/2різних вхідних повідомлень, щоб виникла колізія. Це робить практично неможливим зміна документа при його підписі за допомогою, наприклад, алгоритму SHА шляхом простого підбору, оскільки при такому підході потрібно згенерувати близько 2 80 різних повідомлень, щоб отримати аналогічне підмінюваного по дайджесту. Ця цифра є недосяжною для сучасного рівня технологій.

Нерідко при завантаженні торентів або безпосередньо самих файлів в описі стоїть щось на кшталт «ad33e486d0578a892b8vbd8b19e28754» (наприклад, ex.ua), нерідко з припискою «md5». Це хеш-код – результат, який видає хеш-функція після обробки вхідних даних. У перекладі з англійської хеш означає плутанину, марихуану, траву або страву з дрібно нарізаного м'яса та овочів. дуже і дуже складно, можна сказати, що практично неможливо. Тоді виникає питання: «Навіщо взагалі потрібні всі ці вони видають незрозумілу абракадабру, яка ще й не розшифровується?». Про це й йтиметься у цій статті.

Що таке хеш-функція і як вона діє?

Ця функція призначена для перетворення вхідних даних як завгодно великого розмірурезультат фіксованої довжини. Сам процес такого перетворення називається хешуванням, а результат – хеш або хеш-кодом. Іноді використовують слова «відбиток» або «дайджест повідомлення», але на практиці вони зустрічаються набагато рідше. Існує маса різних алгоритмів того, як можна перетворити будь-який масив даних на якусь послідовність символів певної довжини. Найбільшого поширення набув алгоритм під назвою md5, розроблений ще 1991 року. Незважаючи на те, що на сьогоднішній день md5 є дещо застарілим і до використання не рекомендується, він досі все ще в ходу і часто замість слова «хеш-код», на сайтах просто пишуть md5 і вказують код.

Навіщо потрібна хеш-функція?

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

Хеш-функції: якими вони буваютьт

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

1. Функція перевірки цілісності информации

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

2. Криптографічна функція

Використовується для захисту від НД. Вони дозволяють перевірити, чи не відбулося спотворення даних в результаті НД під час передачі файлів через мережу. Справжній хеш у разі загальнодоступний, а хеш отриманого файла можна обчислити з допомогою безлічі різних програм. Такі функції мають довгий і стабільний термін роботи, а пошук колізій (можливих збігів результату від різних вихідних даних) дуже ускладнений. Саме такі функції використовують для зберігання БД паролів (SH1, SH2, MD5) та іншої цінної інформації.

3. Функція, призначена для створення ефективної структури даних

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

Віруси