Протокол Діффі — Геллмана (англ. Diffie–Hellman key exchange (D–H)) — це метод обміну криптографічними ключами. Один з перших практичних прикладів узгодження ключа, що дозволяє двом учасникам, що не мають жодних попередніх даних один про одного, отримати спільний секретний ключ із використанням незахищеного каналу зв'язку. Цей ключ можна використати для шифрування наступних сеансів зв'язку, що використовують шифр з симетричним ключем.
Схематична ілюстрація протоколу на прикладі змішування фарб | |
Клас | Протокол узгодження ключів |
---|---|
Структура даних | Швидкодія та криптографічна стійкість залежать від обраного простору (циклічної групи) |
Схему вперше оприлюднили Вітфілд Діффі і Мартін Геллман у 1976, хоча пізніше стверджувалось, що її кількома роками раніше винайшов Малколм Вільямсон у GCHQ, британській розвідувальній агенції. 2002 року Геллман запропонував називати алгоритм Обмін ключами Діффі — Геллмана — Меркле у визнання внеску Ральфа Меркле в винайденні криптосистем із відкритим ключем.
Хоча протокол Діффі — Геллмана є анонімним (без автентифікації) протоколом встановлення ключа, він забезпечує базу для різноманітних протоколів з автентифікацією, і використовується для забезпечення цілковитої прямої секретності в недовговічних режимах Transport Layer Security (відомих як EDH або DHE залежно від комплектації шифру).
U.S. Patent 4,200,770, термін дії якого наразі вибіг, описує алгоритм і заявляє Геллмана, Діффі і Меркле як винахідників.
Історія
Діффі й Геллман запропонували у 1976 році алгоритм для створення криптографічних систем з відкритим ключем, який так само, як і алгоритм Ель–Гамаля, базується на складності обчислення дискретного логарифма. Алгоритм Діффі — Геллмана може бути використаний для розподілу ключів (генерування секретного ключа), але його не можна використовувати для шифрування повідомлення.
Алгоритм узгодження ключа Діффі — Геллмана запатентовано у США та Канаді. Ліцензію на цей патент разом з іншими патентами в області криптографії з відкритим ключем отримала група (PKP). Термін дії патенту США вибіг у 1997 році.
Алгоритм Діффі — Геллмана також працює в комутативних кільцях. Шмулі та Кевін МакКерлі запропонували варіант алгоритму, в якому модуль є складеним числом. Міллер і Ніл Кобліц розширили цей алгоритм для використання з еліптичними кривими. Ель–Гамаль використовував основоположну ідею алгоритму Діффі — Геллмана для створення алгоритму шифрування та цифрового підпису. Також є варіант алгоритму для роботи в полі Галуа. У низці реалізацій використаний цей підхід, оскільки обчислення виконуються набагато швидше, але важливо ретельно вибирати поле досить великим, аби забезпечити необхідну стійкість.
Криптографічна стійкість алгоритму Діффі — Геллмана заснована на передбачуваній складності задачі дискретного логарифмування (англ. discrete logarithm problem). Однак, хоча вміння розв'язувати задачу дискретного логарифмування дозволить зламати алгоритм Діффі — Геллмана, зворотне твердження ще не доведене.
Необхідно відзначити, що простий алгоритм Діффі — Геллмана працює тільки на лініях зв'язку, надійно захищених від модифікації. Тоді, коли в каналі можлива модифікація даних, з'являється можливість атаки «людина посередині».
Опис алгоритму
Узгодження спільного таємного ключа відбувається таким чином.
Нехай G — скінченна циклічна група потужністю |G| породжена g.
Аліса і Боб таємно обирають два випадкових цілих числа sA та sB, в інтервалі [0, |G| − 1]. Потім вони таємно обчислють числа aA = gsA та aB = gsB відповідно, та обмінюються ними через незахищений канал передачі даних. Нарешті, Аліса та Боб обчислюють aBA = aBsA = gsBsA та aAB = aAsB = gsAsB відповідно. Слід зазначити, що aAB = aBA, і тому це число може служити спільним таємним ключем K Аліси та Боба.
Точніше, тепер Аліса та Боб можуть скористатись відображенням елементів множини G у простір іншої криптосистеми. Наприклад, вони можуть використати блок даних необхідного розміру (зокрема, молодші біти) значення aAB як ключ звичайної блокової криптосистеми.
Запропоновано варіанти протоколу Діффі — Геллмана для різних множин. Зокрема: мультиплікативні групи над великими скінченними полями (поля простих чисел або розширення), мультиплікативна група залишків за модулем складеного числа, еліптичні криві над скінченними полями, якобіан гіпереліптичних кривих над скінченним полем, та факторгрупи уявних квадратичних полів.
Однак, базовий варіант протоколу узгодження ключа анонімний, тут відсутня можливість автентифікації абонентів. Таким чином, протокол вразливий для атаки «людина посередині». Припустімо, що зловмисник C здатен здійснювати підміну повідомлень, якими обмінюються Аліса та Боб. Тоді він може згенерувати числа s*A та s*B, і відповідно, отримати два узгоджених ключа: gsAs*B та gs*AsB. В результаті зловмисник отримує можливість повністю контролювати обмін повідомленнями між Алісою та Бобом. При цьому вони не здатні виявити підміну та вважатимуть, що зв'язуються один з одним.
Для розв'язання цієї проблеми були запропоновані підсилені варіанти протоколу. Зокрема:
- Попереднє поширення сертифікатів (англ. static DH),
- Протоколи MTI (за прізвищами авторів англ. Matsumoto, Takashima, Imai),
- Відкритий розподіл ключів із використанням автопідписаних ключів,
- Протокол KEA (англ. Key Exchange Algorithm),
- Протокол «уніфікована модель» (англ. unified model),
- Протокол MQV (автори: англ. Law, Menezes, Qu, Solinas, Vanstone).
З автентифікацією абонентів:
- Протокол STS (англ. station-to-station),
- Протокол DHKE.
Приклад
Єва — криптоаналітик, прослуховувач. Вона читає листування Боба і Аліси, але не може змінити вмісту повідомлень.
- 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
|
|
|
Складність зламу
Постає питання: «Наскільки складно обчислити DH-функцію за умови великого ?» Припустимо, що має біт завдовжки, тоді найліпший з відомих на сьогодні алгоритмів GNFS має час виконання , підекспоненційний час виконання.
Приблизна порівняльна таблиця між складністю злому шифру з різними довжинами ключів і обчисленням функції Діффі — Геллмана в первинному варіанті і в варіанті, коли замість обчислень за модулем використовується інший алгебраїчний об'єкт:
Розмір ключа шифру | розмір модуля | розмір еліптичної кривої |
---|---|---|
80 | 1024 | 160 |
128 | 3072 | 256 |
256 | 15360 | 512 |
Обчислити функцію Діффі — Геллмана можна через обчислення з і з . Це є проблема дискретного логарифма, яка обчислювальна нерозв'язна при достатньо великих . Обчислення дискретного алгоритму за модулем потребує приблизно стільки ж часу як факторизація добутку двох простих чисел розміру як і , саме на це покладається безпека криптосистем RSA. Отже протокол Діффі — Геллмана приблизно так само безпечний як безпечний RSA.
Більше двох учасників
Протокол Діффі — Геллмана не обмежується можливістю узгодження ключа між двома учасниками. Будь-яка кількість учасників може узяти участь в узгоджені ключа через ітеративне виконання протоколу узгодження і обмін проміжними даними (які не мають бути засекреченими). Наприклад, Аліса, Боб і Керол можуть узяти участь в узгоджені так (всі дії відбуваються за модулем ):
- Учасники домовляються про параметри алгоритму і .
- Учасники генерують власні ключі, названі , і .
- Аліса обчислює і відправляє Бобу.
- Боб обчислює і відправляє Керол.
- Керол обчислює і використовує як свій секрет.
- Боб обчислює і відправляє Керол.
- Керол обчислює і відправляє Алісі.
- Аліса обчислює і використовує як свій секрет.
- Керол обчислює і відправляє Алісі.
- Аліса обчислює і відправляє Боб.
- Боб обчислює і використовує як свій секрет.
Підслуховувач може бачити , , , , і , але не здатен використати яку-небудь з комбінацій для відтворення .
Для розширення механізму на більші групи, треба дотримуватись двох засад:
- Починаючи з простого ключа , секрет утворюється піднесенням поточного значення до приватного показника один раз, в будь-якому порядку (перше таке піднесення до степеня дає нам відкритий ключ учасника).
- Будь-яке проміжне значення (яке має до виконаних піднесень до приватних показників, де є число учасників у групі) можна показувати, але кінцеве значення (із застосованими всіма показниками) містить спільний секрет і не може бути оприлюднене. Отже, кожен користувач повинен отримати свою копію спільного секрету застосуванням власного приватного ключа останнім.
Ці принципи залишають відкритими варіанти обрання порядку в якому учасники подають ключі. Найпростіший і найочевидніший розв'язок полягає у впорядкуванні учасників по колу і обійти коло для кожного з них, доки кожен з учасників не зробить внеску в кожен з ключів (з його останнім). Однак, це вимагає від кожного учасника виконати піднесень за модулем.
Через обрання оптимальнішого порядку, і покладання на те, що ключі можуть повторюватись, можливо зменшити кількість піднесень у степінь за модулем виконаних кожним учасником до , через використання підходу розділяй і володарюй, наведеному тут для восьми учасників:
- Кожен з учасників A, B, C і D виконують одне піднесення, породжуючи ; це значення посилається до E, F, G і H. В свою чергу. учасники A, B, C і D отримують .
- Учасники A і B виконують одне піднесення, породжуючи , яке посилається до C і D, а C і D роблять це саме, породжуючи , яке вони посилають до A і B.,
- Учасник A виконує піднесення, породжуючи , яке він посилає B; подібно, B посилає A. C і D чинять подібно.
- Учасник A здійснює одне завершальне піднесення, і отримує секрет , тоді як B робить те саме для отримання ; знову, C і D роблять подібним чином.
- Учасник від E до H одночасно виконують ті самі операції, використовуючи як початкове значення.
По завершені алгоритму, всі учасники володітимуть секретом , але кожен з них виконає лише чотири модульні піднесення, а не вісім, як того потребує просте впорядкування по колу.
Неінтерактивність протоколу
У випадку включення свого внеску до протоколу Діффі — Геллмана до свого відкритого фейсбук-профіля, користувачі не потребують спілкування для узгодження секретного ключа. Одразу по прочитанні відкритого профілю користувача, з ним можна починати безпечний зв'язок. Цю властивість іноді називають властивість неінтерактивності протоколу Діффі — Геллмана.
Чи можемо ми це зробити, також неінтерактивно, для більш ніж двох учасників? Тобто, чи може Андрій прочитати і одразу отримати спільний секретний ключ з Богданом, Сергієм і Дмитром — ? На сьогодні відомо, що це можна зробити для трьох учасників, протокол називається Joux і використовує дуже складну математику. Для більш ніж трьох учасників ця проблема відкрита.
Припущення Діффі — Геллмана
— скінченна циклічна група порядку . — випадковий породжувач групи. — довільні показники.
CDH
Обчислювальне припущення Діффі — Геллмана (англ. computational Diffie–Hellman assumption):
- — нехтовна мала.
HDH
Геш припущення Діффі — Геллмана (англ. hash Diffie–Hellman assumption), сильніше від CDH:
Примітки
- В англомовній літературі зустрічаються такі синоніми:
- Diffie–Hellman key agreement
- Diffie–Hellman key establishment
- Diffie–Hellman key negotiation
- Exponential key exchange
- Diffie–Hellman protocol
- Diffie–Hellman handshake
- W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, Vol. 22, No. 6 (1976) pp. 644—654.
- М. В. Захарченко, О. В. Онацький, Л. Г. Йона, Т. М. Шинкарчук (2011). 2.11 Алгоритм Діффі–Хеллмана. Асиметричні методи шифрування в телекомунікаціях. ОНАЗ ім. О. С. Попова. ISBN .
- Ueli M. Maurer та Stefan Wolf (2000). The Diffie-Hellman Protocol. Des. Codes Cryptography. 19 (2/3): 147--171. doi:10.1023/A:1008302122286.
- А.В. Черемушкин (2009). 8.2. Протокол Диффи-Хеллмана и его усиления. Криптографические протоколы. Основные свойства и уязвимости. Академия. с. 173--. ISBN .
- Насправді ніхто не використовує такі великі ключі, використовується значення 2048.
- Weisstein, Eric W. Протокол Діффі — Геллмана(англ.) на сайті Wolfram MathWorld.
Посилання
- Пояснення протоколу Діффі — Геллмана за 5 хвилин на YouTube (англ.)
- RFC 2631 – Метод узгодження ключів Діффі–Геллмана E. Rescorla липень 1999. (англ.)
- Державна служба спеціального зв'язку та захисту інформації України, Наказ № 112: ТЕХНІЧНІ СПЕЦИФІКАЦІЇ форматів криптографічних повідомлень. Захищені дані [ 12 березня 2017 у Wayback Machine.]
Це незавершена стаття з криптографії. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Protokol Diffi Gellmana angl Diffie Hellman key exchange D H ce metod obminu kriptografichnimi klyuchami Odin z pershih praktichnih prikladiv uzgodzhennya klyucha sho dozvolyaye dvom uchasnikam sho ne mayut zhodnih poperednih danih odin pro odnogo otrimati spilnij sekretnij klyuch iz vikoristannyam nezahishenogo kanalu zv yazku Cej klyuch mozhna vikoristati dlya shifruvannya nastupnih seansiv zv yazku sho vikoristovuyut shifr z simetrichnim klyuchem Protokol Diffi GellmanaShematichna ilyustraciya protokolu na prikladi zmishuvannya farbKlasProtokol uzgodzhennya klyuchivStruktura danihShvidkodiya ta kriptografichna stijkist zalezhat vid obranogo prostoru ciklichnoyi grupi Shemu vpershe oprilyudnili Vitfild Diffi i Martin Gellman u 1976 hocha piznishe stverdzhuvalos sho yiyi kilkoma rokami ranishe vinajshov Malkolm Vilyamson u GCHQ britanskij rozviduvalnij agenciyi 2002 roku Gellman zaproponuvav nazivati algoritm Obmin klyuchami Diffi Gellmana Merkle u viznannya vnesku Ralfa Merkle v vinajdenni kriptosistem iz vidkritim klyuchem Hocha protokol Diffi Gellmana ye anonimnim bez avtentifikaciyi protokolom vstanovlennya klyucha vin zabezpechuye bazu dlya riznomanitnih protokoliv z avtentifikaciyeyu i vikoristovuyetsya dlya zabezpechennya cilkovitoyi pryamoyi sekretnosti v nedovgovichnih rezhimah Transport Layer Security vidomih yak EDH abo DHE zalezhno vid komplektaciyi shifru U S Patent 4 200 770 termin diyi yakogo narazi vibig opisuye algoritm i zayavlyaye Gellmana Diffi i Merkle yak vinahidnikiv IstoriyaDiffi j Gellman zaproponuvali u 1976 roci algoritm dlya stvorennya kriptografichnih sistem z vidkritim klyuchem yakij tak samo yak i algoritm El Gamalya bazuyetsya na skladnosti obchislennya diskretnogo logarifma Algoritm Diffi Gellmana mozhe buti vikoristanij dlya rozpodilu klyuchiv generuvannya sekretnogo klyucha ale jogo ne mozhna vikoristovuvati dlya shifruvannya povidomlennya Algoritm uzgodzhennya klyucha Diffi Gellmana zapatentovano u SShA ta Kanadi Licenziyu na cej patent razom z inshimi patentami v oblasti kriptografiyi z vidkritim klyuchem otrimala grupa PKP Termin diyi patentu SShA vibig u 1997 roci Algoritm Diffi Gellmana takozh pracyuye v komutativnih kilcyah Shmuli ta Kevin MakKerli zaproponuvali variant algoritmu v yakomu modul ye skladenim chislom Miller i Nil Koblic rozshirili cej algoritm dlya vikoristannya z eliptichnimi krivimi El Gamal vikoristovuvav osnovopolozhnu ideyu algoritmu Diffi Gellmana dlya stvorennya algoritmu shifruvannya ta cifrovogo pidpisu Takozh ye variant algoritmu dlya roboti v poli Galua U nizci realizacij vikoristanij cej pidhid oskilki obchislennya vikonuyutsya nabagato shvidshe ale vazhlivo retelno vibirati pole dosit velikim abi zabezpechiti neobhidnu stijkist Kriptografichna stijkist algoritmu Diffi Gellmana zasnovana na peredbachuvanij skladnosti zadachi diskretnogo logarifmuvannya angl discrete logarithm problem Odnak hocha vminnya rozv yazuvati zadachu diskretnogo logarifmuvannya dozvolit zlamati algoritm Diffi Gellmana zvorotne tverdzhennya she ne dovedene Neobhidno vidznachiti sho prostij algoritm Diffi Gellmana pracyuye tilki na liniyah zv yazku nadijno zahishenih vid modifikaciyi Todi koli v kanali mozhliva modifikaciya danih z yavlyayetsya mozhlivist ataki lyudina poseredini Opis algoritmuAlgoritm Diffi Gellmana de K pidsumkovij spilnij sekret klyuch Uzgodzhennya spilnogo tayemnogo klyucha vidbuvayetsya takim chinom Nehaj G skinchenna ciklichna grupa potuzhnistyu G porodzhena g Alisa i Bob tayemno obirayut dva vipadkovih cilih chisla sA ta sB v intervali 0 G 1 Potim voni tayemno obchislyut chisla aA gsA ta aB gsB vidpovidno ta obminyuyutsya nimi cherez nezahishenij kanal peredachi danih Nareshti Alisa ta Bob obchislyuyut aBA aBsA gsBsA ta aAB aAsB gsAsB vidpovidno Slid zaznachiti sho aAB aBA i tomu ce chislo mozhe sluzhiti spilnim tayemnim klyuchem K Alisi ta Boba Tochnishe teper Alisa ta Bob mozhut skoristatis vidobrazhennyam elementiv mnozhini G u prostir inshoyi kriptosistemi Napriklad voni mozhut vikoristati blok danih neobhidnogo rozmiru zokrema molodshi biti znachennya aAB yak klyuch zvichajnoyi blokovoyi kriptosistemi Zaproponovano varianti protokolu Diffi Gellmana dlya riznih mnozhin Zokrema multiplikativni grupi nad velikimi skinchennimi polyami polya prostih chisel abo rozshirennya multiplikativna grupa zalishkiv za modulem skladenogo chisla eliptichni krivi nad skinchennimi polyami yakobian gipereliptichnih krivih nad skinchennim polem ta faktorgrupi uyavnih kvadratichnih poliv Odnak bazovij variant protokolu uzgodzhennya klyucha anonimnij tut vidsutnya mozhlivist avtentifikaciyi abonentiv Takim chinom protokol vrazlivij dlya ataki lyudina poseredini Pripustimo sho zlovmisnik C zdaten zdijsnyuvati pidminu povidomlen yakimi obminyuyutsya Alisa ta Bob Todi vin mozhe zgeneruvati chisla s A ta s B i vidpovidno otrimati dva uzgodzhenih klyucha gsAs B ta gs AsB V rezultati zlovmisnik otrimuye mozhlivist povnistyu kontrolyuvati obmin povidomlennyami mizh Alisoyu ta Bobom Pri comu voni ne zdatni viyaviti pidminu ta vvazhatimut sho zv yazuyutsya odin z odnim Dlya rozv yazannya ciyeyi problemi buli zaproponovani pidsileni varianti protokolu Zokrema Poperednye poshirennya sertifikativ angl static DH Protokoli MTI za prizvishami avtoriv angl Matsumoto Takashima Imai Vidkritij rozpodil klyuchiv iz vikoristannyam avtopidpisanih klyuchiv Protokol KEA angl Key Exchange Algorithm Protokol unifikovana model angl unified model Protokol MQV avtori angl Law Menezes Qu Solinas Vanstone Z avtentifikaciyeyu abonentiv Protokol STS angl station to station Protokol DHKE PrikladYeva kriptoanalitik prosluhovuvach Vona chitaye listuvannya Boba i Alisi ale ne mozhe zminiti vmistu povidomlen s sekretnij klyuch s 2 g vidkrite proste chislo g 5 p vidkrite proste chislo p 23 a sekretnij klyuch Alisi a 6 A vidkritij klyuch Alisi A ga mod p 8 b sekretnij klyuch Boba b 15 B vidkritij klyuch Boba B gb mod p 19 Alisa znaye ne znaye 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 Bob znaye ne znaye 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 Yeva znaye ne znaye 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 23Skladnist zlamuPostaye pitannya Naskilki skladno obchisliti DH funkciyu za umovi velikogo p displaystyle p Pripustimo sho p displaystyle p maye n displaystyle n bit zavdovzhki todi najlipshij z vidomih na sogodni algoritmiv GNFS maye chas vikonannya e x p O n 3 displaystyle exp tilde O sqrt 3 n pideksponencijnij chas vikonannya Priblizna porivnyalna tablicya mizh skladnistyu zlomu shifru z riznimi dovzhinami klyuchiv i obchislennyam funkciyi Diffi Gellmana v pervinnomu varianti i v varianti koli zamist obchislen za modulem vikoristovuyetsya inshij algebrayichnij ob yekt Rozmir klyucha shifru rozmir modulya rozmir eliptichnoyi krivoyi 80 1024 160 128 3072 256 256 15360 512 Obchisliti funkciyu Diffi Gellmana mozhna cherez obchislennya a displaystyle a z A g a mod p displaystyle A g a operatorname mod p i b displaystyle b z B g b mod p displaystyle B g b operatorname mod p Ce ye problema diskretnogo logarifma yaka obchislyuvalna nerozv yazna pri dostatno velikih p displaystyle p Obchislennya diskretnogo algoritmu za modulem p displaystyle p potrebuye priblizno stilki zh chasu yak faktorizaciya dobutku dvoh prostih chisel rozmiru yak i p displaystyle p same na ce pokladayetsya bezpeka kriptosistem RSA Otzhe protokol Diffi Gellmana priblizno tak samo bezpechnij yak bezpechnij RSA Bilshe dvoh uchasnikivProtokol Diffi Gellmana ne obmezhuyetsya mozhlivistyu uzgodzhennya klyucha mizh dvoma uchasnikami Bud yaka kilkist uchasnikiv mozhe uzyati uchast v uzgodzheni klyucha cherez iterativne vikonannya protokolu uzgodzhennya i obmin promizhnimi danimi yaki ne mayut buti zasekrechenimi Napriklad Alisa Bob i Kerol mozhut uzyati uchast v uzgodzheni tak vsi diyi vidbuvayutsya za modulem p displaystyle p Uchasniki domovlyayutsya pro parametri algoritmu p displaystyle p i g displaystyle g Uchasniki generuyut vlasni klyuchi nazvani a displaystyle a b displaystyle b i c displaystyle c Alisa obchislyuye g a displaystyle g a i vidpravlyaye Bobu Bob obchislyuye g a b g a b displaystyle g a b g ab i vidpravlyaye Kerol Kerol obchislyuye g a b c g a b c displaystyle g ab c g abc i vikoristovuye yak svij sekret Bob obchislyuye g b displaystyle g b i vidpravlyaye Kerol Kerol obchislyuye g b c g b c displaystyle g b c g bc i vidpravlyaye Alisi Alisa obchislyuye g b c a g b c a g a b c displaystyle g bc a g bca g abc i vikoristovuye yak svij sekret Kerol obchislyuye g c displaystyle g c i vidpravlyaye Alisi Alisa obchislyuye g c a g c a displaystyle g c a g ca i vidpravlyaye Bob Bob obchislyuye g c a b g c a b g a b c displaystyle g ca b g cab g abc i vikoristovuye yak svij sekret Pidsluhovuvach mozhe bachiti g a displaystyle g a g b displaystyle g b g c displaystyle g c g a b displaystyle g ab g a c displaystyle g ac i g b c displaystyle g bc ale ne zdaten vikoristati yaku nebud z kombinacij dlya vidtvorennya g a b c displaystyle g abc Dlya rozshirennya mehanizmu na bilshi grupi treba dotrimuvatis dvoh zasad Pochinayuchi z prostogo klyucha g displaystyle g sekret utvoryuyetsya pidnesennyam potochnogo znachennya do privatnogo pokaznika odin raz v bud yakomu poryadku pershe take pidnesennya do stepenya daye nam vidkritij klyuch uchasnika Bud yake promizhne znachennya yake maye do N 1 displaystyle N 1 vikonanih pidnesen do privatnih pokaznikiv de N displaystyle N ye chislo uchasnikiv u grupi mozhna pokazuvati ale kinceve znachennya iz zastosovanimi vsima N displaystyle N pokaznikami mistit spilnij sekret i ne mozhe buti oprilyudnene Otzhe kozhen koristuvach povinen otrimati svoyu kopiyu spilnogo sekretu zastosuvannyam vlasnogo privatnogo klyucha ostannim Ci principi zalishayut vidkritimi varianti obrannya poryadku v yakomu uchasniki podayut klyuchi Najprostishij i najochevidnishij rozv yazok polyagaye u vporyadkuvanni N displaystyle N uchasnikiv po kolu i obijti kolo dlya kozhnogo z nih doki kozhen z uchasnikiv ne zrobit vnesku v kozhen z N displaystyle N klyuchiv z jogo ostannim Odnak ce vimagaye vid kozhnogo uchasnika vikonati N displaystyle N pidnesen za modulem Cherez obrannya optimalnishogo poryadku i pokladannya na te sho klyuchi mozhut povtoryuvatis mozhlivo zmenshiti kilkist pidnesen u stepin za modulem vikonanih kozhnim uchasnikom do log 2 N 1 displaystyle log 2 N 1 cherez vikoristannya pidhodu rozdilyaj i volodaryuj navedenomu tut dlya vosmi uchasnikiv Kozhen z uchasnikiv A B C i D vikonuyut odne pidnesennya porodzhuyuchi g a b c d displaystyle g abcd ce znachennya posilayetsya do E F G i H V svoyu chergu uchasniki A B C i D otrimuyut g e f g h displaystyle g efgh Uchasniki A i B vikonuyut odne pidnesennya porodzhuyuchi g e f g h a b displaystyle g efghab yake posilayetsya do C i D a C i D roblyat ce same porodzhuyuchi g e f g h c d displaystyle g efghcd yake voni posilayut do A i B Uchasnik A vikonuye pidnesennya porodzhuyuchi g e f g h c d a displaystyle g efghcda yake vin posilaye B podibno B posilaye g e f g h c d b displaystyle g efghcdb A C i D chinyat podibno Uchasnik A zdijsnyuye odne zavershalne pidnesennya i otrimuye sekret g e f g h c d b a g a b c d e f g h displaystyle g efghcdba g abcdefgh todi yak B robit te same dlya otrimannya g e f g h c d a b g a b c d e f g h displaystyle g efghcdab g abcdefgh znovu C i D roblyat podibnim chinom Uchasnik vid E do H odnochasno vikonuyut ti sami operaciyi vikoristovuyuchi g a b c d displaystyle g abcd yak pochatkove znachennya Po zaversheni algoritmu vsi uchasniki voloditimut sekretom g a b c d e f g h displaystyle g abcdefgh ale kozhen z nih vikonaye lishe chotiri modulni pidnesennya a ne visim yak togo potrebuye proste vporyadkuvannya po kolu Neinteraktivnist protokoluVidkriti profili koristuvachiv u Fejsbuci mozhut stati v prigodi dlya avtonomnogo otrimannya sekretnogo klyucha Andriyu dlya otrimannya spilnogo klyucha z Sergiyem potribno prochitati g c displaystyle g c i pidnesti do stepenya a displaystyle a Sergiyu analogichno U vipadku vklyuchennya svogo vnesku do protokolu Diffi Gellmana do svogo vidkritogo fejsbuk profilya koristuvachi ne potrebuyut spilkuvannya dlya uzgodzhennya sekretnogo klyucha Odrazu po prochitanni vidkritogo profilyu koristuvacha z nim mozhna pochinati bezpechnij zv yazok Cyu vlastivist inodi nazivayut vlastivist neinteraktivnosti protokolu Diffi Gellmana Chi mozhemo mi ce zrobiti takozh neinteraktivno dlya bilsh nizh dvoh uchasnikiv Tobto chi mozhe Andrij prochitati g b g c g d displaystyle g b g c g d i odrazu otrimati spilnij sekretnij klyuch z Bogdanom Sergiyem i Dmitrom K A B C D displaystyle K ABCD Na sogodni vidomo sho ce mozhna zrobiti dlya troh uchasnikiv protokol nazivayetsya Joux i vikoristovuye duzhe skladnu matematiku Dlya bilsh nizh troh uchasnikiv cya problema vidkrita Pripushennya Diffi GellmanaG displaystyle G skinchenna ciklichna grupa poryadku n displaystyle n g displaystyle g vipadkovij porodzhuvach grupi a b displaystyle a b dovilni pokazniki CDH Obchislyuvalne pripushennya Diffi Gellmana angl computational Diffie Hellman assumption P r A g g a g b g a b displaystyle Pr A g g a g b Rightarrow g ab nehtovna mala HDH Gesh pripushennya Diffi Gellmana angl hash Diffie Hellman assumption silnishe vid CDH g g a g b H g b g a b p g g a g b R R r K displaystyle 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 PrimitkiV anglomovnij literaturi zustrichayutsya taki sinonimi Diffie Hellman key agreement Diffie Hellman key establishment Diffie Hellman key negotiation Exponential key exchange Diffie Hellman protocol Diffie Hellman handshake W Diffie and M E Hellman New directions in cryptography IEEE Transactions on Information Theory Vol 22 No 6 1976 pp 644 654 M V Zaharchenko O V Onackij L G Jona T M Shinkarchuk 2011 2 11 Algoritm Diffi Hellmana Asimetrichni metodi shifruvannya v telekomunikaciyah ONAZ im O S Popova ISBN 978 966 7598 71 6 Ueli M Maurer ta Stefan Wolf 2000 The Diffie Hellman Protocol Des Codes Cryptography 19 2 3 147 171 doi 10 1023 A 1008302122286 A V Cheremushkin 2009 8 2 Protokol Diffi Hellmana i ego usileniya Kriptograficheskie protokoly Osnovnye svojstva i uyazvimosti Akademiya s 173 ISBN 978 5 7695 5748 4 Naspravdi nihto ne vikoristovuye taki veliki klyuchi vikoristovuyetsya znachennya 2048 Weisstein Eric W Protokol Diffi Gellmana angl na sajti Wolfram MathWorld PosilannyaPoyasnennya protokolu Diffi Gellmana za 5 hvilin na YouTube angl RFC 2631 Metod uzgodzhennya klyuchiv Diffi Gellmana E Rescorla lipen 1999 angl Derzhavna sluzhba specialnogo zv yazku ta zahistu informaciyi Ukrayini Nakaz 112 TEHNIChNI SPECIFIKACIYi formativ kriptografichnih povidomlen Zahisheni dani 12 bereznya 2017 u Wayback Machine Ce nezavershena stattya z kriptografiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi