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

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

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

Прикладом хешувальної функції може бути функція h, збудована на базі системи RSA. Якщо довжина тексту X не перевищує довжини повідомлень, які можна шифру-вати цією системою, то h(X) - RSA(X). Довші повідомлення спочатку розбивають на блоки X = X1.. Хl-1Xl відповідної довжини, а тоді обчислюють значення хешувальної функції:

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

Узагальнена схема обчислення хешувальної функції показана на рис. 5.1.

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

Алгоритм MD5

Сім'я алгоритмів обчислення хешувальної функції MD (Massage Digest Algorithm; кроковий узагальнений алгоритм) була розроблена Р.Райвестом. Вона охоплює алгоритми MD2, MD4, MD5, які незначно відрізняються один від одного. Найширше використовують сьогодні алгоритм MD5, запропонований 1991 р. Його детально опи-сано далі.

Алгоритм перетворює вхідне повідомлення довільної довжини в стиснутий образ довжиною 128 бітів.

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

Для обчислення хешувальної функції вхідне повідомлення розбивають на блоки по 512 бітів кожний. Кожен блок М, відповідно, розбивають на шістнадцять 32-бітових блоків Mj, (j = 0, 1, ..., 15).

Опрацювання одного блока М відбувається за чотири цикли, кожен з яких охоплює 16 кроків. Кожен цикл використовує такі побітові операції: сума за модулем 2 (по-значають знаком ), диз'юнкція (знак v), кон'юнкція (позначають крапкою або відсут-ністю знака між змінними), інверсія (позначають рискою зверху над змінною).

Ці операції виконують над відповідними бітами 32-бітових блоків X, Y, Z і визна-чають функції:

За допомогою функції F визначають процедуру FF:

де Mj означає j 32-бітовий блок вхідної послідовності; "+" - додавання за модулем 232 відповідних 32-бітових чисел; Shs - операцію циклічного зсуву праворуч на s позицій; ti, дорівнює цілій частині числа 232 |sin і|, наведеного у двійковому розвиненні.

Для задания процедур GG, НН, II функцію F заміняють, відповідно, на функції G, Н,І.

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

а = 67452301, b = efcdab89, с = 98badcfe, d = 10325476.

Цикл 1. Послідовно виконують такі 16 кроків:

Кожен раз порядок регістрів a, b, c, d зсувається циклічно на одну позицію пра-воруч. Крім того, аргументи .у (кількість позицій циклічного зсуву) утворюють таку послідовність: 7, 12, 17, 22, 7, 12,...

Цикл 2. Відбувається подібно до циклу 1. Однак замість процедури FF виконують процедуру GG; замість послідовності 7,12,17,22 використовують послідовність 5, 9, 14, 20. Крім того, i-й виклик 0=1,2, ..., 16) процедури GG використовує t16+,- за-мість ti, та М1+5i mod 16 замість Mi.

Цикл 3. Відбувається з аналогічними змінами: використовують процедуру НН; послідовність 4, 11, 16, 23, а також t32+i та M5+3i mod 16 під час і-го (і - 1, 2,..., 16) виклику процедури НН.

Цикл 4. Використовують процедуру //; послідовність 6, 10, 15, 21, а також f48+i та M3+7imod16 під час i-го (і =1,2,..., 16) виклику процедури //.

Остаточним значенням хешувальної функції є послідовність із 128 бітів, яку отримують об'єднанням (конкатенацією) вмісту регістрів a b c d.

Алгоритм SHA-1

Алгоритм SHA-1 (Secure Hash Algorithm; безпечний хешувальний алгоритм) прийнятий 1992 р. як стандарт у США. Він ґрунтується на тих самих принципах, що й сім'я алгоритмів MD. Алгоритм SHA-1 перетворює послідовності довжини, кратної 512 бітам, у стиснуту 160-бітову послідовність. У цьому разі вхідні тексти перетворюються в послідовності, довжина яких кратна 512 бітам. Це виконується так само, як і в алгоритмі MD5, додаванням одиниці, потрібної кількості нулів та 64-бітової довжини повідомлення. Вхідний текст має вигляд M = M1,M2, ...,МN (N 512-бітових блоків), де кожен блок Mi, має шістнадцять (Wo, W1 ..., Wl5) 32-бітових слів.

Алгоритм використовує регістри a, b, c, d,