Протокол Діффі-Геллмана

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Протокол Діффі-Геллмана (англ. Diffie–Hellman key exchange (D–H)[nb 1]) — це метод обміну криптографічними ключами. Один з перших практичних прикладів обміну ключами, що дозволяє двом учасникам, що не мають жодних попередніх даних один про одного, отримати спільний секретний ключ із використанням незахищеного каналу зв'язку. Цей ключ можна використати для шифрування наступних сеансів зв'язку, що використовують шифр з симетричним ключем.

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

Хоча протокол Діффі-Геллмана є анонімним (без автентифікації) протоколом встановлення ключа, він забезпечує базу для різноманітних протоколів з автентифікацією, і використовується для забезпечення цілковитої прямої секретності в недовговічних режимах Transport Layer Security (відомих як EDH або DHE залежно від комплектації шифру).

U.S. Patent 4 200 770, наразі термін дії вибіг, описує алгоритм і заявляє Геллмана, Діффі і Меркла як винахідників.

Опис алгоритму[ред.ред. код]

Алгоритм Діффі — Геллмана, де K — підсумковий спільний секрет (ключ)

Припустимо, обом абонентам відомі деякі два числа: велике просте p (наприклад, 600 цифр) і g\in\{1,...,p\} (як варіант, вони можуть бути «зашиті» в програмне забезпечення), які не є секретними та можуть бути відомі й іншим зацікавленим особам. Для того, щоб створити не відомий нікому іншому секретний ключ, обидва учасники генерують великі випадкові числа: перший — число a\in\{1,...,p-1\}, другий — b\in\{1,...,p-1\}. Потім перший учасник обчислює значення A=g^a \bmod p і відправляє його другому, а той обчислює B=g^b \bmod p і відправляє першому. Вважається, зловмисник може отримати ці повідомлення, але не змінити їх.

На другому етапі, перший користувач на основі свого a і отриманого мережею B обчислює значення B^a\bmod p=g^{ab}\bmod p, а другий користувач з b і A обчислює значення A^b\bmod p=g^{ab}\bmod p. Як неважко бачити, в обох користувачів виходить те саме число: K=g^{ab}\bmod p. Його вони і можуть використовувати як секретний ключ, оскільки зловмисник тут зтикається з необхідністю обчислити функцію DH_g(g^a, g^b) = g^{ab}\bmod p.

Приклад[ред.ред. код]

Єва — криптоаналітик, прослуховувач. Вона читає листування Боба і Аліси, але не може змінити вмісту повідомлень.

  • s = секретний ключ. s = 2
  • g = відкрите просте число. g = 5
  • p = відкрите просте число. p = 23
  • a = секретний ключ Аліси. a = 6
  • A = відкритий ключ Аліси. A = ga mod p = 8
  • b = секретний ключ Боба. b = 15
  • B = відкритий ключ Боба. B = gb mod p = 19
Аліса
знає не знає
p = 23 b = ?
g = 5
a = 6
A = 56 mod 23 = 8
B = 5b mod 23 = 19
s = 196 mod 23 = 2
s = 8b mod 23 = 2
s = 196 mod 23 = 8b mod 23
s = 2
Боб
знає не знає
p = 23 a = ?
g = 5
b = 15
B = 515 mod 23 = 19
A = 5a mod 23 = 8
s = 815 mod 23 = 2
s = 19a mod 23 = 2
s = 815 mod 23 = 19a mod 23
s = 2
Єва
знає не знає
p = 23 a = ?
g = 5 b = ?
s = ?
A = 5a mod 23 = 8
B = 5b mod 23 = 19
s = 19a mod 23
s = 8b mod 23
s = 19a mod 23 = 8b mod 23

Складність зламу[ред.ред. код]

Постає питання: «Наскільки складно обчислити DH-функцію за умови великого p?» Припустимо, що p має n біт завдовжки, тоді найліпший з відомих на сьогодні алгоритмів GNFS має час виконання exp(\tilde O(\sqrt[3]n)), підекспоненційний час виконання.

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

Розмір ключа шифру розмір модуля розмір еліптичної кривої
80 1024 160
128 3072 [1] 256
256 15360 512

Обчислити функцію Діффі-Геллмана можна через обчислення a з A=g^a (mod p) і b з B=g^b (mod p). Це є проблема дискретного логарифму, яка обчислювальна нерозв'язна при достатньо великих p. Обчислення дискретного алгоритму за модулем p потребує приблизно стільки ж часу як факторизація добутку двох простих чисел розміру як і p, саме на це покладається безпека криптосистем RSA. Отже протокол Діффі-Геллмана приблизно так само безпечний як безпечний RSA[2].

Більш як два учасники[ред.ред. код]

Протокол Діффі-Геллмана не обмежується можливістю узгодження ключа між двома учасниками. Будь-яка кількість учасників може узяти участь в узгоджені ключа через ітеративне виконання протоколу узгодження і обмін проміжними даними (які не мають бути засекреченими). Наприклад, Аліса, Боб і Керол можуть узяти участь в узгоджені так (всі дії відбуваються за модулем p):

  1. Учасники домовляються про параметри алгоритму p і g.
  2. Учасники генерують власні ключі, названі a, b і c.
  3. Аліса обчислює g^a і відправляє Бобу.
  4. Боб обчислює (g^a)^b = g^{ab} і відправляє Керол.
  5. Керол обчислює (g^{ab})^c = g^{abc} і використовує як свій секрет.
  6. Боб обчислює g^b і відправляє Керол.
  7. Керол обчислює (g^b)^c = g^{bc} і відправляє Алісі.
  8. Аліса обчислює (g^{bc})^a = g^{bca} = g^{abc} і використовує як свій секрет.
  9. Керол обчислює g^c і відправляє Алісі.
  10. Аліса обчислює (g^c)^a = g^{ca} і відправляє Боб.
  11. Боб обчислює (g^{ca})^b = g^{cab} = g^{abc} і використовує як свій секрет.

Підслуховувач може бачити g^a, g^b, g^c, g^{ab}, g^{ac} і g^{bc}, але не здатен використати яку-небудь з комбінацій для відтворення g^{abc}.

Для розширення механізму на більші групи, треба дотримуватись двох засад:

  • Починаючи з простого ключа g, секрет утворюється піднесенням поточного значення до приватного показника один раз, в будь-якому порядку (перше таке піднесення до степеня дає нам відкритий ключ учасника).
  • Будь-яке проміжне значення (яке має до N-1 виконаних піднесень до приватних показників, де N є число учасників у групі) можна показувати, але кінцеве значення (із застосованими всіма N показниками) містить спільний секрет і не може бути оприлюднене. Отже, кожен користувач повинен отримати свою копію спільного секрету застосуванням власного приватного ключа останнім.

Ці принципи залишають відкритими варіанти обрання порядку в якому учасники подають ключі. Найпростіший і найочевидніший розв'язок полягає у впорядкуванні N учасників по колу і обійти коло для кожного з них, доки кожен з учасників не зробить внеску в кожен з N ключів (з його останнім). Однак, це вимагає від кожного учасника виконати N піднесень за модулем.

Через обрання оптимальнішого порядку, і покладання на те, що ключі можуть повторюватись, можливо зменшити кількість піднесень у степінь за модулем виконаних кожним учасником до \log_2 (N) + 1, через використання підходу розділяй і володарюй, наведеному тут для восьми учасників:

  1. Кожен з учасників A, B, C і D виконують одне піднесення, породжуючи g^{abcd}; це значення посилається до E, F, G і H. В свою чергу. учасники A, B, C і D отримують g^{efgh}.
  2. Учасники A і B виконують одне піднесення, породжуючи g^{efghab}, яке посилається до C і D, а C і D роблять це саме, породжуючи g^{efghcd}, яке вони посилають до A і B.,
  3. Учасник A виконує піднесення, породжуючи g^{efghcda}, яке він посилає B; подібно, B посилає g^{efghcdb} A. C і D чинять подібно.
  4. Учасник A здійснює одне завершальне піднесення, і отримує секрет g^{efghcdba} = g^{abcdefgh}, тоді як B робить те саме для отримання g^{efghcdab} = g^{abcdefgh}; знову, C і D роблять подібним чином.
  5. Учасник від E до H одночасно виконують ті самі операції, використовуючи g^{abcd} як початкове значення.

По завершені алгоритму, всі учасники володітимуть секретом g^{abcdefgh}, але кожен з них виконає лише чотири модульні піднесення, а не вісім, як того потребує просте впорядкування по колу.

Неінтерактивність протоколу[ред.ред. код]

Відкриті профілі користувачів у Фейсбуці, можуть стати в нагоді для автономного отримання секретного ключа. Андрію для отримання спільного ключа з Сергієм потрібно прочитати g^c і піднести до степеня a, Сергію аналогічно

У випадку включення свого внеску до протоколу Діффі-Геллмана до свого відкритого фейсбук-профіля, користувачі не потребують спілкування для узгодження секретного ключа. Одразу по прочитанні відкритого профілю користувача, з ним можна починати безпечний зв'язок. Цю властивість іноді називають властивість неінтерактивності протоколу Діффі-Геллмана.

Чи можемо ми це зробити, також неінтерактивно, для більш ніж двох учасників? Тобто, чи може Андрій прочитати g^b, g^c, g^d і одразу отримати спільний секретний ключ з Богданом, Сергієм і Дмитром - K_{ABCD}? На сьогодні відомо, що це можна зробити для трьох учасників, протокол називається Joux і використовує дуже складну математику. Для більш ніж трьох учасників ця проблема відкрита.

Діффі-Геллман припущення[ред.ред. код]

G — скінченна циклічна група порядку n. g — випадковий породжувач групи. a, b — довільні показники.

CDH[ред.ред. код]

Обчислювальне припущення Діффі-Геллмана (англ. computational Diffie–Hellman assumption):

Pr[A(g,g^a,g^b)\Rightarrow g^{ab}] — нехтовна мала.

HDH[ред.ред. код]

Геш припущення Діффі-Геллмана (англ. hash Diffie–Hellman assumption), сильніше від CDH:

(g,g^a,g^b,H(g^b,g^{ab}))\approx_p(g,g^a,g^b,R), R \overset{\underset{\mathrm{r}}{}}{\leftarrow} K

Примітки[ред.ред. код]

  1. В англомовній літературі зустрічаються такі синоніми:
    • Diffie–Hellman key agreement
    • Diffie–Hellman key establishment
    • Diffie–Hellman key negotiation
    • Exponential key exchange
    • Diffie–Hellman protocol
    • Diffie–Hellman handshake
  1. Насправді ніхто не використовує такі великі ключі, використовується значення 2048.
  2. Weisstein, Eric W. Протокол Діффі-Геллмана(англ.) на сайті Wolfram MathWorld.

Посилання[ред.ред. код]