Криптографічний хеш-функція. хешування

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

Визначення хеша і його обчислення

Один з кращих способів визначити хеш-функцію від рядка S наступний:

H (S) \u003d S + S * P + S * P ^ 2 + S * P ^ 3 + ... + S [N] * P ^ N

де P - деяке число.

Розумно вибирати для P просте число, приблизно дорівнює кількості символів у вхідному алфавіті. Наприклад, якщо рядки предполаются складаються тільки з маленьких латинських літер, то хорошим вибором буде P \u003d 31. Якщо букви можуть бути і великими, і маленькими, то, наприклад, можна P \u003d 53.

У всіх шматках коду в цій статті буде використовуватися P \u003d 31.

Саме значення хеша бажано зберігати в найбільшому числовому типі - int64, він же long long. Очевидно, що при довжині рядка близько 20 символів вже буде відбуватися переповнення значення. Ключовий момент - що ми не звертаємо увагу на ці переповнення, як би беручи хеш по модулю 2 ^ 64.

Приклад обчислення хеша, якщо допустимі тільки маленькі латинські літери:

Const int p \u003d 31; long long hash \u003d 0, p_pow \u003d 1; for (size_t i \u003d 0; i

У більшості завдань має сенс спочатку обчислити всі необхідні міри P в будь-якому масиві.

Приклад завдання. Пошук однакових рядків

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

Звичайною сортуванням рядків ми б отримали алгоритм зі складністю O (N M log N), в той час як використовуючи хеші, ми отримаємо O (N M + N log N).

Алгоритм. Порахуємо хеш від кожного рядка, і відсортуємо рядки з цього хешу.

Vector s (n); // ... зчитування рядків ... // вважаємо все ступеня p, припустимо, до 10000 - максимальної довжини рядків const int p \u003d 31; vector p_pow (10000); p_pow \u003d 1; for (size_t i \u003d 1; i \u003e Hashes (n); for (int i \u003d 0; i

Хеш підрядка і його швидке обчислення

Припустимо, нам дана рядок S, і дані індекси I і J. Потрібно знайти хеш від підрядка S.

За визначенням маємо:

H \u003d S [I] + S * P + S * P ^ 2 + ... + S [J] * P ^ (J-I)

H * P [I] \u003d S [I] * P [I] + ... + S [J] * P [J], H * P [I] \u003d H - H

Отримане властивість є дуже важливим.

Дійсно, виходить, що, знаючи тільки хеші від всіх префіксів рядки S, ми можемо за O (1) отримати хеш будь подстроки.

Єдина виникає проблема - це те, що потрібно вміти ділити на P [I]. Насправді, це не так просто. Оскільки ми обчислюємо хеш по модулю 2 ^ 64, то для розподілу на P [I] ми повинні знайти до нього зворотний елемент в поле (наприклад, за допомогою Розширеного алгоритму Евкліда), і виконати множення на цей зворотний елемент.

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

Припустимо, дано два хеша: один помножений на P [I], а інший - на P [J]. якщо I< J, то умножим перый хэш на P, иначе же умножим второй хэш на P. Теперь мы привели хэши к одной степени, и можем их спокойно сравнивать.

Наприклад, код, який обчислює хеші всіх префіксів, а потім за O (1) порівнює два підрядки:

String s; int i1, i2, len; // вхідні дані // вважаємо все ступеня p const int p \u003d 31; vector i2 && h1 \u003d\u003d h2 * p_pow) cout<< "equal"; else cout << "different";

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

Ось деякі типові застосування хешування:

• Визначення кількості різних подстрок за O (N ^ 2 log N) (див. Нижче)
• Визначення кількості палиндромов всередині рядка

Визначення кількості різних подстрок

Нехай дана рядок S довжиною N, що складається тільки з маленьких латинських літер. Потрібно знайти кількість різних подстрок в цьому рядку.

Для вирішення переберемо по черзі довжину підрядка: L \u003d 1 .. N.

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

Реалізація:

String s; // вхідний рядок int n \u003d (int) s.length (); // вважаємо все ступеня p const int p \u003d 31; vector p_pow (s.length ()); p_pow \u003d 1; for (size_t i \u003d 1; i H (s.length ()); for (size_t i \u003d 0; i hs (n-l + 1); for (int i \u003d 0; i

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

Що це таке?

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

Характеристики

Розглянемо ключові характеристики досліджуваних алгоритмів. У числі таких:

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

У числі інших найважливіших властивостей хеш-функції:

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

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

Вимоги до хеш-функцій

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

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

структура

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

У якій структурі може бути представлена \u200b\u200bвикористовувана в подібних цілях хеш-функція? Приклад її складання може бути таким: H (hash, тобто, хеш) \u003d f (T (текст), H1), де H1 - алгоритм обробки тексту T. Ця функція хешірует T таким чином, що без знання H1 відкрити його як повноцінний файл буде практично неможливо.

Використання хеш-функцій на практиці: скачування файлів

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

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

Хеш-функція і ЕЦП

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

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

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

Перевірка паролів

Ще одна можлива область застосування хешування - організація алгоритмів перевірки паролів, встановлених для розмежування доступу до тих чи інших файлових ресурсів. Яким чином при вирішенні подібних завдань можуть бути задіяні ті чи інші види хеш-функцій? Дуже просто.

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

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

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

Колізії хеш-функцій

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

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

Історія появи

Основоположниками теорії хеш-функцій можна вважати дослідників Картера, Вегмана, Симонсона, Біербрауера. У перших версіях відповідні алгоритми були задіяні в якості інструментарію для формування унікальних образів послідовностей символів довільної довжини з подальшою метою їх ідентифікації та перевірки на предмет достовірності. У свою чергу, хеш, відповідно до заданих критеріїв, повинен був володіти довжиною 30-512 біт. Як особливо корисного властивості відповідних функцій розглядалася її пристосованість для задіяння в якості ресурсу швидкого пошуку файлів, або їх сортування.

Популярні стандарти хеширования

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

У свою чергу, при шифруванні досить широке застосування знаходять стандарти MD4 і MD5. Ще один популярний криптографічний алгоритм - SHA-1. Зокрема, він характеризується розміром хеша 160 біт, що більше, ніж у MD5 - даний стандарт підтримує 128 біт. Є російські стандарти, що регулюють використання хеш-функцій, - ГОСТ Р 34.11-94, а також замінив його ГОСТ Р 34.11-2012. Можна відзначити, що величина хеша, передбачена алгоритмами, прийнятими в РФ, становить 256 біт.

Стандарти, про які йде мова, можуть бути класифіковані за різними підставами. Наприклад, є ті, що задіюють алгоритми блокові і спеціалізовані. Простота обчислень на основі стандартів першого типу часто супроводжується їх невисокою швидкістю. Тому в якості альтернативи блоковим алгоритмам можуть бути задіяні ті, що припускають менший обсяг необхідних обчислювальних операцій. До швидкодіючим стандартам прийнято відносити, зокрема, зазначені вище MD4, MD5, а також SHA. Розглянемо специфіку спеціальних алгоритмів хешування на прикладі SHA докладніше.

Особливості алгоритму SHA

Застосування хеш-функцій, що базуються на стандарті SHA, найчастіше здійснюється в області розробки засобів цифрового підпису документів DSA. Як ми зазначили вище, алгоритм SHA підтримує хеш 160 біт (забезпечуючи так званий «дайджест» послідовності символів). Спочатку розглядається стандарт ділить масив даних на блоки по 512 біт. При необхідності, якщо довжина останнього блоку не дотягує до зазначеної цифри, структура файлу доповнюється 1 і необхідною кількістю нулів. Також в кінці відповідного блоку вписується код, що фіксує довжину повідомлення. Розглянутий алгоритм задіє 80 логічних функцій, за допомогою яких обробляється 3 слова, представлені в 32 розрядах. Також в стандарті SHA передбачено використання 4 констант.

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

Вивчимо то, як співвідносяться властивості хеш-функцій, що відносяться до різних стандартів, на прикладі зіставлення характеристик російського стандарту ГОСТ Р 34.11-94 і американського SHA, який ми розглянули вище. Перш за все, слід відзначити те, що алгоритм, розроблений в РФ, передбачає здійснення 4 операцій щодо шифрування в розрахунку на 1 цикл. Це відповідає 128 раундів. У свою чергу, протягом 1 раунду при залученні SHA передбачається обчислення близько 20 команд, при тому що всього раундів 80. Таким чином, використання SHA дозволяє протягом 1 циклу обробити 512 біт вихідних даних. У той час як російський стандарт здатний здійснити операції за цикл в 256 біт даних.

Специфіка новітнього російського алгоритму

Вище ми відзначили, що стандарт ГОСТ Р 34.11-94 був замінений більш новим - ГОСТ Р 34.11-2012 «Стрибог». Досліджуємо його специфіку докладніше.

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

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

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

Специфіка криптографічних хеш-функцій

Розглянемо більш докладно, яким чином досліджувані нами типи алгоритмів можуть бути задіяні в сфері криптографії. Ключова вимога до відповідних функцій - стійкість до колізій, про які ми сказали вище. Тобто не повинні формуватися повторювані значення хеш-функції, якщо значення ці вже присутні в структурі є сусідами алгоритму. Іншим зазначеним вище критеріям криптографічні функції також повинні відповідати. Зрозуміло, що завжди є якась теоретична можливість відновлення вихідного файлу на основі хеша, особливо якщо в доступі є потужний обчислювальний інструмент. Однак подібний сценарій передбачається звести до мінімуму, завдяки надійним алгоритмам шифрування. Так, обчислити хеш-функцію буде дуже складно, якщо її обчислювальна стійкість відповідає формулі 2 ^ (n / 2).

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

ітеративні схеми

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

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

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

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

блоковий алгоритм

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

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

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

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

контрольні суми

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

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

Платою за таку високу швидкість є відсутність криптостойкости - легка можливість підігнати повідомлення під заздалегідь відому суму. Також зазвичай розрядність контрольних сум (типове число: 32 біта) нижче, ніж криптографічних хеш-кодувань (типові числа: 128, 160 і 256 біт), що означає можливість виникнення ненавмисних колізій.

Найпростішим випадком такого алгоритму є розподіл повідомлення на 32- або 16- бітні слова і їх підсумовування, що застосовується, наприклад, в TCP / IP.

Як правило, до такого алгоритму пред'являються вимоги відстеження типових апаратних помилок, таких, як кілька поспіль помилкових біт до заданої довжини. Сімейство алгоритмів т. Н. «Циклічний надлишкових кодів» задовольняє цим вимогам. До них відноситься, наприклад, CRC32, застосовуваний в апаратурі ZIP.

Криптографічні хеш-функції

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

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

Хеш-функції також використовуються в деяких структурах даних - хеш-табліцаx і декартових деревах. Вимоги до хеш-функції в цьому випадку інші:

• хороша перемешіваемость даних
• швидкий алгоритм обчислення

звірка даних

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

Перевірка на наявність помилок

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

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

Перевірка парольної фрази

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

Прикладом в даному випадку можуть служити ОС GNU / Linux і Microsoft Windows XP. У них зберігаються лише хеш-значення пральних фраз з облікових записів користувачів.

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

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

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

список алгоритмів

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tiger (Whirlpool
• IP Internet Checksum (RFC 1071)

посилання

Wikimedia Foundation. 2010 року.

• Хешан Мохеянь
• хеш код

Дивитися що таке "Хеш-функція" в інших словниках:

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

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

Одностороння хеш-функція - хеш функція, яка є обчислювально незворотною функцією. За англійськи: One way hash function Див. Також: Криптографічні алгоритми Фінансовий словник Фінам ... Фінансовий словник

TIGER - хеш-функція - TIGER хеш функція, розроблена Росом Андерсоном і Елі Біхамом в 1996 році. Хеш функція TIGER є новою швидкої хеш функцією, яка покликана бути дуже швидкою на сучасних комп'ютерах, зокрема, на 64 розрядних комп'ютерах. TIGER ... ... Вікіпедія

одностороння хеш-функція - Для односторонньої функції обчислювально неможливо знайти два різних аргументу, для яких її значення збігаються. [] Тематики захист інформації EN one way hash function ... Довідник технічного перекладача

Tiger (хеш-функція) - Tiger хеш функція, розроблена Росом Андерсоном і Елі Біхамом в 1995 році. Tiger був призначений для особливо швидкого виконання на 64 розрядних комп'ютерах. Tiger не має патентних обмежень, може використовуватися вільно як з ... ... Вікіпедія

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

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

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

Колізія хеш-функції - колізії хеш функції H називається два різних вхідних блоку даних x та y таких, що H (x) \u003d H (y). Колізії існують для більшості хеш функцій, але для «хороших» хеш функцій частота їх виникнення близька до теоретичного мінімуму. В ... ... Вікіпедія

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

Мета лекції: познайомитися з поняттям "хеш-функція", а також з принципами роботи таких функцій.

Поняття хеш-функції

Хеш-функцією (hash function) називається математична чи інша функція, яка для рядки довільної довжини обчислює деяке ціле значення або деяку іншу рядок фіксованої довжини. Математично це можна записати так:

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

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

Хеш-функції широко застосовуються в сучасній криптографії.

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

Наприклад, нехай вихідне повідомлення, перекладене в цифровий вигляд, було наступним (у шістнадцятковому форматі):

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

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Результат (0110 0101 (2) або 65 (16)) і буде значенням хеш-функції.

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

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

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

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

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

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

h i \u003d H (M i, h i-1),

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

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

Використання блокових алгоритмів шифрування для формування хеш-функції

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

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

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

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

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

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

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

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

Основним недоліком хеш-функцій, спроектованих на основі блокових алгоритмів, є відносно низька швидкість роботи. Необхідну криптостойкость можна забезпечити і за меншу кількість операцій над вхідними даними. Існують більш швидкі алгоритми хешування, спроектованих самостійно, з нуля, виходячи з вимог криптостойкости (найбільш поширені з них - MD5, SHA-1, SHA-2 і ГОСТ Р 34.11-94).

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

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

· Криптографічні хеші;

· Програмістські хеші.

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

m - вихідні дані,

h (m) - хеш-функція від них.

Незворотність означає, що якщо відомо число h0, то важко підібрати m таке, що h (m) \u003d h0.

Вільність від колізій означає, що важко підібрати такі m1 і m2, що m1 не дорівнює m2, але h (m1) \u003d h (m2).

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

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

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

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

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

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

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

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

4. для будь-якого фіксованого x обчислювально неможливо знайти інший x "≠ x, такий що h (x") \u003d h (x).

Пара x "≠ x, коли h (x") \u003d h (x) називається колізією хеш-функції.

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

5. обчислювально неможливо знайти будь-яку пару x "≠ x, таку, що h (x") \u003d h (x).
Оскільки з властивостей 1-2 випливає, що безліч визначення хеш-функції значно ширше безлічі значень, то колізії повинні існувати. Властивість 4 вимагає, щоб знайти їх для заданого значення х було практично неможливо. Вимога 5 говорить про те, що у сильної хеш-функції обчислювально неможливо взагалі знайти будь-яку колізію.

Існують різні алгоритми обчислення хеш-функцій

MD2 (Message Digest) - алгоритм криптографічного згортки. Породжує блок довжиною 128 біт від повідомлення довільної довжини. Загальна схема роботи MD2:

a. доповнення тексту повідомлень до довжини, кратної 128 біт;

b. обчислення 16-бітної контрольної суми, старші розряди відкидаються;

c. додавання контрольної суми до тексту;

d. повторне обчислення контрольної суми.

Алгоритм MD2 дуже повільний, тому частіше застосовуються MD4, MD5, SHA (Secure Hash Algorithm). Результуючий хеш має довжину 160 біт.

ГОСТ Р34.11-94. Російський алгоритм. Довжина згортки - 256 біт (дуже зручно для формування по паролю ключа для ГОСТ 28147-89).

Національний інститут стандартів і технологій (ність) США на своєму веб-сайті http://www.nist.gov/sha/ опублікував специфікації нових алгоритмів хешування SHA-256, SHA-384 і SHA-512, мета яких - забезпечити рівень криптостійкості хеша , відповідний довжинах ключів нового стандарту шифрування DES.

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

До теперішнього часу найбільш популярними хеш-функціями були створені Райвістом MD4 і MD5, генеруючі хеш-коди довжиною n \u003d 128, і алгоритм SHA-1, розроблений в АНБ США і породжує хеш-код довжиною n \u003d 160.

ГОСТ Р34.10-94 «Процедури вироблення і перевірки електронного цифрового підпису на базі асиметричного криптографічного алгоритму».