Як працює обмін ключами Діффі-Геллмана
Аліса та Боб ніколи не зустрічалися. Вони спілкуються каналом, який Єва бачить повністю. Проте після короткого обміну числами Аліса та Боб мають спільний секрет, який Єва не може визначити — навіть знаючи кожне надіслане ними повідомлення. Це обмін ключами Діффі-Геллмана, рушій під капотом HTTPS.
Проблема розподілу ключів
Класичне симетричне шифрування (як-от AES) швидке й безпечне — але воно вимагає, щоб обидві сторони знали один і той самий ключ. До епохи інтернету обмін ключами означав особисту зустріч, дипломатичного кур'єра або фізичний носій. Для мільйонів вебсерверів, що одночасно спілкуються з мільярдами браузерів, це неможливо.
У 1976 році Вітфілд Діффі та Мартін Геллман опублікували знакову працю: «Нові напрями в криптографії». Їхній протокол дозволяє двом сторонам вивести ідентичний секретний ключ, обмінюючись лише публічною інформацією — ніколи не передаючи сам ключ. Це розв'язало проблему, яка тисячоліттями вважалася нерозв'язною.
Аналогія зі змішуванням фарб
Канонічний спосіб зрозуміти ДГ — через кольори фарб. Змішувати фарби легко; «розмішати» їх назад — важко. Це відображає однонаправлену математичну функцію в основі ДГ.
Єва бачить жовтий, помаранчевий і бірюзовий — публічні кольори. Відновлення окремих червоного та синього зі сумішей — це проблема «розмішування». У математиці це відповідає задачі дискретного логарифма.
Математика: модульне піднесення до степеня
Аналогія з фарбами має точну математичну версію. Аліса та Боб
домовляються про два публічні числа: велике просте число p та
генератор g
(обидва можна опублікувати на весь світ — їх знають усі).
Математична тотожність, завдяки якій це працює:
Аліса обчислює (gᵇ)ᵃ, а Боб обчислює (gᵃ)ᵇ —
вони доходять до одного й того самого значення, бо піднесення до степеня в модульній
арифметиці комутативне.
Чому це важко обернути
Єва знає p, g, A = gᵃ mod p та
B = gᵇ mod p. Щоб зламати обмін, їй потрібно відновити
або a, або b — розв'язати рівняння:
Для цілих чисел без «mod» це тривіально: якщо 5ᵃ = 3125, то очевидно a = 5. У модульній арифметиці закономірність руйнується — значення «обгортаються» у спосіб, що здається хаотичним. Невідомо жодного алгоритму, який ефективно розв'язує DLP для великих простих чисел.
a, перебравши всі 23 варіанти за
мілісекунди. Справжній ДГ використовує прості числа з 2048–4096 бітами. Найкращий відомий
алгоритм, загальне решето числового поля (GNFS), вимагав би більше
обчислень, ніж усі коли-небудь побудовані комп'ютери, що працювали б мільйони
років.
Аліса та Боб крок за кроком
| Крок | Аліса | Канал (бачить Єва) | Боб |
|---|---|---|---|
| 1 — Узгодження параметрів | Знає p=23, g=5 | p=23, g=5 опубліковано | Знає p=23, g=5 |
| 2 — Приватні ключі | Обирає a=6 (секрет) | — | Обирає b=15 (секрет) |
| 3 — Публічні значення | Надсилає A=8 | A=8, B=19 видно | Надсилає B=19 |
| 4 — Спільний секрет | s = 19⁶ mod 23 = 2 | s=2 ніколи не передавалося | s = 8¹⁵ mod 23 = 2 |
| 5 — Шифрування | Обидва використовують s=2 (на практиці хешоване/розтягнуте) як ключ AES для сеансу | ||
Проблема «людини посередині»
Простий Діффі-Геллман має одну критичну слабкість: він не забезпечує автентифікації. Якщо Єва перехопить з'єднання на початку, вона може провести два окремі обміни ДГ — один з Алісою, видаючи себе за Боба, і один з Бобом, видаючи себе за Алісу. Обидва «захищені» канали насправді проходять через Єву.
Саме тому справжній HTTPS поєднує Діффі-Геллман із сертифікатом: цифровим підписом від довіреного центру сертифікації (CA), що підтверджує, що публічний ключ сервера справді належить, скажімо, bank.com, а не самозванцю.
Діффі-Геллман на еліптичних кривих (ECDH)
Сучасний TLS майже завжди використовує ECDH замість класичного ДГ. Відбувається той самий концептуальний обмін, але замість модульного піднесення до степеня на цілих числах він використовує множення точок на еліптичній кривій: гладкій кривій, заданій y² = x³ + ax + b над скінченним полем.
«Складною задачею» для ECDH є задача дискретного логарифма на еліптичній кривій (ECDLP): маючи точку P та Q = k·P на кривій, знайти k. Вважається, що ECDLP значно складніша за класичну DLP, що означає:
- 256-бітний ключ ECDH забезпечує безпеку, порівнянну з 3072-бітним класичним ключем ДГ.
- Менші ключі → швидші рукостискання → нижче навантаження на ЦП як на сервері, так і на клієнті.
- Curve25519 (використовується в TLS 1.3 та Signal) спеціально розроблена, щоб протистояти атакам за часом на рівні реалізації.
Діффі-Геллман у TLS/HTTPS
Щоразу, коли ви відвідуєте сайт https://, рукостискання TLS виконує
Діффі-Геллман (або ECDH) за мілісекунди. TLS 1.3 (2018) вимагає
лише набори шифрів на основі Діффі-Геллмана, відкидаючи всі інші,
бо ДГ забезпечує пряму секретність:
Типовий обмін ключами TLS 1.3 з використанням X25519 (ECDH з Curve25519):
Постквантова загроза
Алгоритм Шора, що працює на достатньо великому квантовому комп'ютері, може розв'язати як задачу факторизації цілих чисел (RSA), так і задачу дискретного логарифма (ДГ/ECDH) за поліноміальний час — роблячи обидва протоколи небезпечними.
Криптографічно значущого квантового комп'ютера поки не існує (експерти оцінюють, що до нього 10–20 років за нинішнього прогресу), але загроза достатньо реальна, щоб NIST у 2024 році стандартизував чотири постквантові криптографічні алгоритми, зокрема CRYSTALS-Kyber для інкапсуляції ключів — заміну Діффі-Геллмана на основі ґраткових задач, які, як вважається, стійкі до квантових атак.
Google, Apple та Signal вже впровадили гібридні постквантові рукостискання у своїх продуктах, поєднуючи класичний ECDH з постквантовим алгоритмом.