Однобічна функція, шифр Діфі-Хелмана

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

Вперше ідея застосування односпрямованих функцій була запропонована американськими дослідниками Уітфілдом Діффі і Мартіном Хелманом. Ці функції характеризуються наступною властивістю. Односпрямовану функцію з секретом y = f_t(x): D ® R легко обчислити для усіх x Î D, але дуже важко обчислити зворотну функцію x = f_t^-1(y): R ® D майже для усіх y Î R. Однак, якщо використовується секретна інформація t, для всіх значень y Î R легко обчислюється x = f_t^-1(y).

Протокол обміну ключами Діфі-Хелмана

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

Для початку Аліса і Боб домовляються користуватись скінченим полем F_p, де p – достатньо велике просте число. Крім того, вони домовляються про застосування примітивного елементу g Î F_p, (" a Î F_p, a = g^i(a), де 0 £ i(a) < p. Числа p і g – не секретні.

Протокол Діфі-Хелмана має такий вигляд.

Спільні вихідні дані:

(p, g): p – велике просте число, g – примітивний елемент F^*_p, (F^*_p - мультиплікативна група поля F_p).

Результат: Число k Î F^*_p, відоме тільки Алісі і Бобу, і більш нікому. Аліса вибирає довільне число a Î (1, p-1), обчислює g^a mod p і посилає результат Бобу. Боб вибирає довільне число b Î (1, p-1), обчислює g^b mod p і посилає результат Алісі. Аліса обчислює k = (g^b)^a mod p. Боб обчислює k = (g^a)^b mod p. В цьому протоколі Аліса і Боб обчислюють одне і теж саме значення k = g^ba mod p = g^ab mod p.

Таким чином, Аліса і Боб отримують ключ, не передаючи його по каналу зв’язку. Єва може перехопити g^a або g^b. Але визначення g^ab за відомими g^a та g^b є відомою складною задачею Діфі-Хелмана, яка тісно пов’язана з іншою складною задачею обчислення дискретного логарифму a = log_g(g^a), b = log_g(g^b).

Приклад застосування протоколу. Нехай, p = 11, g = 7. Число g є примітивним елементом поля F, оскільки g⁰ mod 11 = 1, g¹ mod 11 = 7, g² mod 11 = 5, g³ mod 11 = 2, g⁴ mod 11 = 3, g⁵ mod 11 = 10, g⁶ mod 11 = 4, g⁷ mod 11 = 6, g⁸ mod 11 = 9, g⁹ mod 11 = 8, g¹⁰ mod 11 =1. Аліса вибирає a = 6, обчислює g⁶ mod 11 = 4 і посилає Бобу число 4. Боб вибирає b = 9, обчислює g⁹ mod 11 = 8 і посилає Алісі число 8. Аліса обчислює (8⁶ mod 11 = 8² mod 11 x 8² mod 11 x 8² mod 11) mod 11 = ((9 x 9) mod 11 x 9) mod 11 = (4 x 9) mod 11 = 3.

Боб обчислює 4⁹ mod 11 = 4³ mod 11 x 4³ mod 11 x 4³ mod 11) mod 11 = ((9 x 9) mod 11 x 9) mod 11 = (4 x 9) mod 11 = 3.

 

Атака «людина посередині»

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

1. Єва перехоплює перше повідомлення від Аліси до Боба, замінює g^a на g^e і відправляє Бобу від імені Аліси.

2. Боб відправляє g^b, яке перехоплює Єва. В результаті встановлюється ключ g^eb між Бобом і Євою.

3. Аналогічно Єва може відправити Алісі від імені Боба g^e і таким чином встановити ключ g^ae між Алісою і Євою.

Надалі Єва має змогу читати і змінювати секретні повідомлення між Євою та Бобом.

Для запобігання атаці «людина посередині» застосовуються протоколи на основі використання центрів сертифікації.

 

Криптосистема RSA

Один з найбільш популярних алгоритмів шифрування цієї групи є алгоритм Рівеста-Шаміра-Адлемана (Rivest-Shamir-Adleman – RSA). Алгоритм RSA ґрунтується на застосуванні однобічної функції піднесення до степеня за відомим модулем. При відкритих значеннях n та e для поданого повідомлення m легко обчислити m^e (mod n) – шифр повідомлення. При цьому за відомим шифром відновити повідомлення без додаткової інформації практично неможливо. В той же час, якщо відомо розкладання n на множники, остання задача стає розв’язною.

Криптосистема RSA передбачає наступну послідовність дій.

Обрати два великих випадкових простих числа p і q, таких, що |p| ≈ |q|, де |p | - кількість бітів необхідна для представлення числа p (|p| = élog₂(p+1)ù). Обчислити n = pq. Обчислити F(n) = НСК(p-1, q-1). Обрати випадкове ціле число e < F(n), таке, що НСД(e, F(n)) = 1 mod F(n), і знайти ціле число d, таке, що ed = 1 mod F(n). Таке d існує, і його можна знайти за допомогою розширеного алгоритму Евкліда. Скористатися парою (n, e) як відкритим ключем, знищивши числа p, q і F(n), і запам’ятати d як закритий ключ.

Шифрування. Для того, щоб надіслати Алісі секретне повідомлення m, що, як число, менше n, Боб створює зашифрований текст c = m^e mod n. (З точки зору Боба, простір вихідних повідомлень представляє собою множину всіх додатних чисел, що менше n, хоча насправді цим простором є група Z_n^*.)

Розшифрування. m = c^d mod n.

Слід відзначити, що нерівність m < n практично завжди означає, що m Î Z_n^* (тобто майже всі числа, що менше n належать мультиплікативній групі цілих чисел, взаємно простих з n). Умова m Î Z_n^* порушується, якщо m = up або m = vq, де u < q і v < p. В цих умовах Боб може розкласти число n на прості множники, обчисливши значення НСД (m, n Приклад. Припустимо, Аліса обрала числа p = 11, q = 13. Тоді n = 143, F(n) = НСК(p-1, q-1)= НСК(10, 12) = 60. Нехай, e = 7. За допомогою розширеного алгоритму Евкліда визначаємо, що d = 43. Кроки визначення показані у табл. 6.1. Припустимо, Боб бажає передати Алісі повідомлення, відкритий текст якого є число 3. Він шифрує це повідомлення за допомогою відкритого ключа Аліси e = 7 і відправляє 3⁷ mod 143 = 42.

Аліса отримує повідомлення 42 і за допомогою секретного ключа d = 43 розшифровує прийняте повідомлення 42⁴³ mod 143 =((((42² mod 143)² mod 143)² mod 143) ² mod 143) ² mod 143 х 42⁸ mod 143 х 42² mod 143 х 42 mod 143 = (((48² mod 143)² mod 143) ² mod 143) ² mod 143 х 42⁸ mod 143 х 48 х 42 mod 143 = ((16² mod 143) ² mod 143) ² mod 143 х 42⁸ mod 143 х 48 х 42 mod 143 = (113² mod 143) ² mod 143 х 113 х 48 х 42 mod 143 = 42 ² mod 143 х 113 х 48 х 42 mod 143 = 42 ² mod 143 х 113 х 48 х 42 mod 143 = (48 х 113) mod 143 х 48 х 42 mod 143 = (133 х 48) mod 143 х 42 mod 143= (92 х 42) mod 143 = 3.