Page 41 - 4394

3.4 Хешувальні функції

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

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

якщо виконуються такі умови:
 для кожного тексту X легко обчислити значення h(X);
 h(X) має однакову довжину для всіх текстів X (тому

довжина h(X) не дає жодної інформації про текст Х;
 практично неможливо для заданого У знайти таке X, що

h(X) = Y.
Послідовність h(X) повинна бути досить довгою для того, щоб
систематичний пошук X був практично неможливим. Наприклад,
коли значення хешувальної функції складається з 128 бітів, то
128
38
маємо 2 = 3,410 можливих варіантів, достатньо велике число.
Хешувальні функції повинні задовольняти трьом головним

вимогам:
 за відомим значенням функції h(Х) неможливо (дуже
складно в обчислювальному сенсі) знайти її аргумент X; таку
функцію називають стійкою у розумінні обернення;

 для заданого аргументу X повинно бути неможливим
знайти такий інший аргумент Х , що h(Х) = h(Х ); таку функцію
1
1
називають стійкою у розумінні обчислення колізій;
 з погляду практичного застосування алгоритми обчислення
хешувальних функцій повинні бути швидкими, а ще ліпше – бути

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

використати у разі:
 зберігання паролів (гасел);
 цифрових підписів;

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

паролях:
 користувач А подає свій пароль х;

41