Хеш-функції, що застосовуються на практиці

Серед розповсюджених сьогодні хеш-функцій можна назвати такі: MD5, RIPEMD-160, група функцій SHA: SHA-1, SHA-256, SHA-384, SHA-512. Всі ці функції за своєю природою ітераційні, але відрізняються параметрами, серед яких в першу чергу слід вказати довжину коду на виході. Функція MD5 створює рядки довжиною 128 бітів, SHA-1 – 160 бітів, довжина вихідних кодів інших функцій вказана у назві.

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

f(u, v, w) = uv Ú uw,

g(u, v, w) = uv Ú uw Ú vw,

h(u, v, w) = u Å v Å w.

Впродовж всього алгоритму відстежується поточний хеш-стан (H₁, H₂, H₃, H₄), де H_i – 32-бітові змінні, початкові значення яких визначені наступним чином.

H₁ = ’67452301h’, H₂ = ’EFCDAB89h’, H₃ = ’98BADCFEh’, H₄ = ’ 10325476h’.

В алгоритмі використовуються константи, значення яких залежить від номера раунду і номера кроку. Раунд – це група послідовних кроків алгоритму. Алгоритм складається з трьох раундів по 16 кроків у кожному. Всі кроки алгоритму пронумеровані від 0 до 47. Кроки 0 – 15 утворюють перший раунд, 16 – 31 - другий, а 32 – 47 – третій. Якщо позначити індексом i номер раунду, а індексом j - номер кроку, то можна сказати, що в алгоритмі використовуються три групи констант y_i, i = 1, 3, z_j, s_j, j = 0, 47. Значення констант представляються наступними масивами.

y_1-3 = [0, ‘5A827999h’, ‘6ED9EBA1h’],

z_0-15 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],

z_16-31 = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15],

z_32-47 = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15],

s_0-15 = [3, 7, 11, 19, 3, 7, 11, 19, 3, 7, 11, 19, 3, 7, 11, 19],

s_16-31 = [3, 5, 9, 13, 3, 5, 9, 13, 3, 5, 9, 13, 3, 5, 9, 13],

s_32-47 = [3, 9, 11, 15, 3, 9, 11, 15, 3, 9, 11, 15, 3, 9, 11, 15].

Потік даних складається з 16 слів, що завантажуються одночасно в масив X[j] (0 ≤ j < 16). Потім виконуються перетворення кожного з завантажених слів:

(A, B, C, D) = (H₁, H₂, H₃, H₄).

Виконується перший раунд.

Виконується другий раунд.

Виконується третій раунд.

(H₁, H₂, H₃, H₄) = (H₁ + A, H₂ + B, H₃ + C, H₄ + D).

Значенням функції хешування є конкатенація H₁H₂H₃H₄.

Дії, що виконуються у кожному раунді:

- раунд 1

for i = 0 to 15 do

begin

t = A + f(B, C, D) + X[z_i] + y_i.

(A, B, C, D) = (D, t <<< s_i, B, C);

end

- раунд 2

for i = 16 to 31 do

begin

t = A + g(B, C, D) + X[z_i] + y_i.

(A, B, C, D) = (D, t <<< s_i, B, C);

end

- раунд 3

for i = 32 to 47 do

begin

t = A + h(B, C, D) + X[z_i] + y_i.

(A, B, C, D) = (D, t <<< s_i, B, C);

End

Застосування еліптичних кривих в криптографії

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

У криптографії розглядаються еліптичні криві на скінчених полях характеристики p. Еліптичною кривою називають криву, точки якої задовольняють рівнянню

ay² + bxy + cx² + dy + ex + f = gx³ + hx² + kx + l (mod p), (1)

де a, b, c, d, e, f, g, h, k, l – коефіцієнти, що є елементами поданого скінченого поля. Інакше кажучи, в лівій частині рівняння довільний поліном F(x, y) другого степеню, а в правій довільний поліном G(x) третього степеню.

Надалі будемо вважати, що точки еліптичної кривої E задовольняють рівнянню

y² = x³ + qx + r (mod p), (2)

оскільки шляхом заміни змінних завжди можна від форми (1) перейти до форми (2). Форма (2) називається канонічною формою Вейєрштрасса. Крім того, p – просте число, p > 3, q,r Î F_p.

Приклади еліптичних кривих наведені на рис. 9.1. Графік в лівій частині рисунку відповідає випадку, коли поліном G(x) має три дійсні корені: -1, 0, 1, а в правій – тільки один.

 

Операції додавання на множені точок еліптичної кривої

На множині точок еліптичної кривої означається операція таким чином, щоб утворилася група. Ця операція позначається символом «+». При визначенні операції множина точок кривої E доповнюється штучною точкою O, що віддалена на нескінченість по вісі y. Координата x точки O невизначена. Це означає, що можна вважати, що ця координата дорівнює будь-якому елементу F_p. Інакше кажучи, кожна вертикальна пряма проходить через точку O.

52 –

 

53-

 

Множення точок на число

Нехай m – ціле число, а P Î E. Уведемо наступне позначення

P + P + … + P (m доданків), m > 0,

mP = O, m = 0,

- (|m|P) m < 0.

 

Обчислення величини mP (результату m -кратного виконання операції «+» є аналогом піднесення до степеню в мультиплікативній групі. Ця операція виконується згідно з наступним алгоритмом.

Вхід: точка P Î E; ціле число m > 0.

Вихід: mP.

EC_Multiply(P, m)

if m = 0 return (O).

if m (mod 2) = 0 return (EC_Multiply(P + P, m / 2));

else return (P + EC_Multiply(P, m - 1)).

Наприклад, обчислюючи EC_Multiply(P, 14), поданий алгоритм виконує чотири рекурсивні виклики.

EC_Multiply(P, 14) = EC_Multiply(P + P, 7) = 2P + EC_Multiply(2P + 2P, 3) = 2P + 4P + EC_Multiply(4P + 4P, 1) = 2P + 4P + 8P + EC_Multiply(8P + 8P, 0) = 2P + 4P + 8P + O.

Результат дорівнює 14P.

Слід зауважити, що розглянутий алгоритм не використовує ніяких властивостей групи, якій належить точка P. Цей алгоритм являє собою реалізацію процесу множення точки на число згідно з визначенням. Часова складність його становить O((log p)³). Існують і більш ефективні алгоритми