Що таке Хеш чи Хешування? Хеш-функції: поняття та основи Види хешів

Як приклад «поганий» хеш-функції можна навести функцію з M = 1000 (\displaystyle M = 1000)яка десятизначного натурального числа K (\displaystyle K)зіставляє трицифри, вибрані із середини двадцятизначного квадрата числа K (\displaystyle K). Здавалося б, значення «хеш-кодів» мають рівномірнорозподілятися між « 000 » та « 999 ", але для " реальнихданих це справедливо лише в тому випадку, якщо ключіне мають «великої» кількості нулів, ліворуч або праворуч.

Розглянемо кілька простих та надійних реалізацій «хеш-функцій».

«Хеш-функції», засновані на розподілі

1. «Хеш-код» як залишок від поділу на число всіх можливих «хешів»

Хеш-функція може обчислювати «хеш» як залишок від поділу вхідних даних на M (\displaystyle M):

де M (\displaystyle M)- кількість всіх можливих "хешів" (вихідних даних).

При цьому очевидно, що при парному M (\displaystyle M)значення функції буде парним при парному k (\displaystyle k)і непарним - при непарному k (\displaystyle k). Також не слід використовувати як M (\displaystyle M)ступінь заснування системи, обчислення комп'ютера, так як «хеш-код» залежатиме лише від кількохцифр числа k (\displaystyle k), розташованих праворуч, що призведе до великої кількості колізій. На практиці зазвичай вибирають просте M (\displaystyle M); здебільшого цей вибір цілком задовільний.

2. «Хеш-код» як набір коефіцієнтів одержуваного полінома

Хеш-функція може виконувати поділ вхідних даних на поліном за модулем два. У цьому методі M (\displaystyle M)має бути ступенем двійки, а бінарні ключі ( K = k n − 1 k n − 2 .. . k 0 (\displaystyle K=k_(n-1)k_(n-2)...k_(0)) ) подаються у виглядіполіномів K (\displaystyle K), як «хеш-код» «беруться» значення коефіцієнтів поліномаотриманого як залишок від поділу вхідних даних на заздалегідь обраний поліном:

m (\displaystyle m) K(x) mod P(x) = h m − 1 x m − 1 + ⋯ + h 1 x + h 0 (\displaystyle 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 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0))При правильному виборі P(x) (\displaystyle P(x)).

гарантується відсутність колізій між майже однаковими ключами. "Хеш-функції", засновані на множенніПозначимо символом "Хеш-функції", засновані на множенні w (\displaystyle w) h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0))кількість чисел, представлених машинним словом . Наприклад, для 32-розрядних комп'ютерів, сумісних з IBM, PC,

Виберемо якусь константу M (\displaystyle M) A (\displaystyle A) так щоббула взаємно простою з . Тоді хеш-функція, що використовує множення, може мати такий вигляд:.

h (K) = [ M ⌊ A w ∗ K ⌋ ] (\displaystyle h(K)=\left)

Однією з хеш-функцій, що використовують множення, є хеш-функція, що використовує хешування Фібоначчі. Хешування Фібоначчі засноване на властивостях золотого січення. Як константа "Хеш-функції", засновані на множеннітут вибирається ціле число, найближче до φ − 1 ∗ w (\displaystyle \varphi ^(-1)*w)і взаємно просте з h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0)), де φ (\displaystyle \varphi)- Це золотий перетин.

Хешування рядків змінної довжини

Вищевикладені методи можна застосувати і в тому випадку, якщо необхідно розглядати ключі, що складаються з декількох слів, або ключі змінної довжини. Наприклад, можна скомбінувати слова за допомогою додавання по модулю h 1 h 0 (\displaystyle h(x)=h_(m-1)...h_(1)h_(0))або операції «що виключає». Одним із алгоритмів, що працюють за таким принципом, є хеш-функція Пірсона.

Універсальне хешування

Методи боротьби з колізіями

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

Методи боротьби з колізіями у хеш-таблицях

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

1. метод ланцюжків (метод прямого зв'язування);
2. метод відкритої адресації.

При використанні методу ланцюжків у хеш-таблиці зберігаються пари «зв'язковий список ключів» - «хеш-код». Для кожного ключа хеш-функцією обчислюється хеш-код; якщо хеш-код був отриманий раніше (для іншого ключа), ключ додається до існуючого списку ключів, парний хеш-коду; інакше, створюється нова пара "список ключів" - "хеш-код", і ключ додається до створеного списку. У випадку, якщо є N (\displaystyle N)ключів та M (\displaystyle M)списків, середній розмір хеш-таблиці складе N M (\displaystyle (\frac (N)(M))). У цьому випадку при пошуку по таблиці в порівнянні з випадком, в якому пошук виконується послідовно, середній обсяг робіт зменшиться приблизно в M (\displaystyle M)разів.

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

Криптографічна сіль

Застосування хеш-функцій

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

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

Серед безлічі існуючих хеш-функцій прийнято виділяти

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

Завдання хешування

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

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

Найпоширеніші алгоритми: MD5 (MD4, MD2), SHA1.

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

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

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

Для перевірки пакета на наявність помилок часто використовується контрольна сума, яка передається разом із повідомленням.

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

Обчислення електронного цифрового підпису

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

Вимоги до алгоритму хешування

Хеш-функція може бути використана до аргументу будь-якого розміру.

Вихідне значення має фіксований розмір.

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

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

АлгоритмMD5

MD5(Message Digest 5) – алгоритм хешування, розроблений Р. Рівестом з Массачусетського технологічного інституту (MIT) у 1991 році

Детальний опис алгоритму можна знайти в RFC 1321.

На виході алгоритм видає 128-бітний дайджест повідомлення. Довжина вихідного повідомлення може бути будь-якою.

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

АлгоритмSHA-1

Алгоритм безпечного хешування SHA (Secure Hash Algorithm) прийнятий як стандарт США в 1992 році.

Описаний у RFC 3174.

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

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

Відмінності алгоритмів SHA та MD5 полягають у наступному:

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

2. Стискаюча функція SHA включає 80 раундів, а не 64 як у MD5.

3. Ускладнено процес перемішування.

Алгоритми сімействаSHA-2

Алгоритми підродини SHA-2 , так само як і алгоритм SHA-1 , були розроблені Агентством національної безпеки США та опубліковані Національним інститутом стандартів та технологій (NIST) у федеральному стандарті обробки інформації FIPS PUB 180–2 у серпні 2002 року.

Алгоритми сімейства SHA-2 використовуються в SSL, SSH, S/ MIME, DNSSEC, X.509 , PGP, IPSec, під час передачі файлів через мережу ( BitTorrent).

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

MD5 md5 = новий MD5CryptoServiceProvider();

string stringToHash = "З'їж ще цих м'яких французьких булок та випий чаю";

byte hash = md5.ComputeHash(Encoding.Unicode.GetBytes(stringToHash));

Console.WriteLine(ByteHelper.ByteArrayToHexString(hash));

string anotherStringToHash = "The quick brown fox jumps over the lazy dog";

HashAlgorithm sha512 = HashAlgorithm.Create("SHA512");

Console.WriteLine(

ByteHelper.ByteArrayToHexString(

sha512.ComputeHash(

Encoding.Unicode.GetBytes(

Хешування

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

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

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

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

Історія

Першою серйозною роботою, пов'язаною з пошуком у великих файлах, була стаття Уеслі Пітерсона (англ. W. Wesley Peterson ) в IBM Journal of Research and Development 1957 року, де він визначив відкриту адресацію, і навіть вказав на погіршення продуктивності при видаленні. Через шість років було опубліковано роботу Вернера Бухгольця (нім. Werner Buchholz ), у якій проведено широке дослідження хеш-функцій. Протягом кількох наступних років хешування широко використовувалося, проте не було опубліковано жодних значних робіт.

У 1967 році хешування в сучасному значенні згадано в книзі Херберта Хеллермана "Принципи цифрових обчислювальних систем". У 1968 році Роберт Морріс (англ. Robert Morris ) опублікував у Communications of the ACM великий огляд з хешування, ця робота вважається ключовою публікацією, що вводить поняття про хешування в науковий обіг і закріпила термін, що раніше застосовувався тільки в жаргоні фахівців, «хеш».

До початку 1990-х років у російськомовній літературі як еквівалент терміну «хешування» завдяки роботам Андрія Єршова використовувалося слово «розстановка», а для колізій використовувався термін "конфлікт" (Єршов використовував "розстановку" з 1956 року, в російськомовному виданні книги Вірта "Алгоритми та структури даних" 1989 року також використовується термін "розстановка"). Пропонувалося також назвати метод російським словом «окрошка». Однак жоден із цих варіантів не прижився, і в російськомовній літературі використовується переважно термін «хешування».

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

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

1. швидко обчислюватися;
2. Мінімізувати кількість колізій

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

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

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

Хеш-функції засновані на розподілі

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

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

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

За правильного вибору такий спосіб гарантує відсутність колізій між майже однаковими ключами.

Мультиплікативна схема хешування

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

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

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

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

Хешування рядків змінної довжини

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

Універсальне хешування

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

Опис

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

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

Методи боротьби з колізіями

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

У хеш-таблицях

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

1. Метод ланцюжків (метод прямого зв'язування)
2. Метод відкритої адресації

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

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

Криптографічна сіль

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

Застосування хеш-функцій

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

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

Ці вимоги не є незалежними:

• Оборотна функція нестійка до колізій першого та другого роду.
• Функція, нестійка до колізій першого роду; нестійка до колізій другого роду; зворотне неправильне.

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

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

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

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

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

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

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

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

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

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

Геометричне хешування

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

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

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

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

Примітки

Література

• Брюс Шнайєр"Прикладна криптографія. Протоколи, алгоритми, вихідні тексти мовою Сі". – М.: Тріумф, 2002. –

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

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

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

Якими характеристиками має хеш-функція?

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

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

• CRC – циклічний надлишковий код чи контрольна сума. Алгоритм дуже простий, має велику кількість варіацій залежно від необхідної довжини вихідної. Чи не є криптографічним!
• MD 5 – дуже популярний алгоритм. Як і попередня версія MD 4 є криптографічної функцією. Розмір хешу 128 біт.
• SHA -1 - також дуже популярна криптографічна функція. Розмір хешу 160 біт.
• ГОСТ Р 34.11-94 - російський криптографічний стандарт обчислення хеш-функції. Розмір хешу 256 біт.

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

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

Що є російської?Як було сказано вище, в Росії є стандарт хешування ГОСТ Р 34.11-94, який повсюдно використовується багатьма виробниками засобів захисту інформації. Одним із таких засобів є програма фіксації та контролю вихідного стану програмного комплексу «ФІКС». Ця програма є засобом для контролю ефективності застосування СЗІ.

ФІКС (версія 2.0.1) для Windows 9x/NT/2000/XP

• Обчислення контрольних сум заданих файлів за одним із 5 реалізованих алгоритмів.
• Фіксація та подальший контроль вихідного стану програмного комплексу.
• Порівняння версій програмного комплексу
• Фіксація та контроль каталогів.
• Контролює зміни у заданих файлах (каталогах).
• Формування звітів форматах TXT, HTML, SV.
• Виріб має сертифікат ФСТЕК з ПДВ 3 № 913 до 01 червня 2013 р.

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

В даний час багато програм електронної комерції дозволяють зберігати секретний ключ користувача в закритій області токена (ruToken, eToken) без технічної можливості вилучення його звідти. Сам токен має дуже обмежену область пам'яті, що вимірюється в кілобайтах. Для підписання документа немає жодної можливості передати документ у сам токен, а ось передати хеш документа в токен і на виході отримати ЕЦП дуже просто.

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

Багато завдань у галузі інформаційних технологій дуже критичні до обсягів даних. Наприклад, якщо потрібно порівняти між собою два файли розміром по 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. Іноді Хеш-функції застосовуються для створення унікальних ідентифікаторів (як частина). Наприклад, при збереженні картинок або просто файлів зазвичай використовують Хеш в іменах спільно з датою і часом. Це дозволяє перезаписувати файли з однаковими іменами.

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

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

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