Як працює обмін ключами Діффі-Хелмана

Проблема розподілу ключів

Симетричне шифрування, таке як AES, швидке та безпечне, але вимагає від обох сторін вже спільного ключа. До появи інтернету обмін ключами означав особисті зустрічі або довіру поштового кур’єра – неможливо для мільйонів серверів, що спілкуються з мільярдами браузерів. У 1976 році Вітфелд Діффі та Мартин Хелман опублікували "New Directions in Cryptography", протокол, який дозволяє двом сторонам отримати однаковий секрет, обмінюючись лише публічною інформацією, не передаючи ключ безпосередньо.

Поєднання фарб, здійснене точно

Канонічна інтуїція: змішування фарб легко, а "розчинення" їх – важко. Аліса та Боб погоджуються на публічний простий p і генератор g. Аліса обирає секретний a, Боб обирає секретний b, і кожен обчислює публічну величину за допомогою модульної експоненціації:

p = 23, g = 5 (публічно — Єві відомі ці значення) Аліса: a = 6 (секрет) → A = 5⁶ mod 23 = 8 (відправляє A) Боб: b = 15 (секрет) → B = 5¹⁵ mod 23 = 19 (відправляє B) Аліса обчислює: s = B^a mod p = 19⁶ mod 23 = 2 Боб обчислює: s = A^b mod p = 8¹⁵ mod 23 = 2 ← однаковий секрет! (g^a)^b mod p = (g^b)^a mod p = g^(ab) mod p Обидві сторони досягають однієї і тієї ж величини, оскільки експоненціювання над модульною арифметикою комутативне — Аліса обчислює (gᵇ)ᵃ, Боб обчислює (gᵃ)ᵇ, і вони однакові. Реальний DH використовує прості з 2048-4096 бітами, а не іграшкові значення, як 23.

p = 23, g = 5   (public — Eve knows these too)
Alice: a = 6 (secret)  → A = 5⁶ mod 23 = 8   (sends A)
Bob:   b = 15 (secret) → B = 5¹⁵ mod 23 = 19 (sends B)

Alice computes: s = B^a mod p = 19⁶  mod 23 = 2
Bob computes:   s = A^b mod p = 8¹⁵ mod 23 = 2   ← same secret!

(g^a)^b mod p = (g^b)^a mod p = g^(ab) mod p

жива демонстрація · пов'язана симуляція● LIVE

Чому так важко розшифрувати: задача обчислення дискретного логарифма

Еві відомі p, g, A та B. Щоб зламати обмін, їй потрібно знайти таке a, що gᵃ ≡ A (mod p) – це задача обчислення дискретного логарифма (DLP). Звичайними цілими числами це тривіально (якщо 5⁵ = 3125, то очевидно a = 5), але модульне "переповнення" руйнує закономірність, і відомо жодного ефективного класичного алгоритму для розв’язування її з великими простими числами. З p = 23, Ева може перебрати значення a за мілісекунди; з реальним простим числом 2048 біт найкращий відомий метод – Загальний сітовий метод чисел – займе більше часу, ніж вік Всесвіту.

Уловка: отсутствие аутентификации

Простой Diffie-Hellman имеет одну критическую слабость — он обеспечивает секретность, но не аутентификацию. Если Иви перехватить соединение с самого начала, она сможет провести два отдельных обмена DH, выдавая себя за Боба к Алисе и Алисе к Бобу, причем оба "безопасных" канала фактически будут проходить через нее. Именно поэтому HTTPS сочетает DH с сертификатом: подпись от доверенного Центр Сертификации подтверждает, что публичный ключ действительно принадлежит домену, который вы посещаете. Современный TLS 1.3 требует использования обменно-криптографических (обычно эллиптической кривой ECDH) схем шифрования, поскольку они обеспечивают переносимость вперед — каждый канал генерирует новую, эфемерную пару ключей, поэтому запись сегодняшнего трафика и последующий кража долгосрочного ключа сервера не могут расшифровать старые сеансы.

Часті запитання

Як Діффі-Геллман дозволяє двом сторонам домовитися про секрет без його передачі?

Обидві сторони комбінують спільне публічне значення з їхнім власним приватним числом за допомогою модульної експоненціації, обмінюються лише результатами та потім кожен підносить інший публічний результат до власної приватної степені. Оскільки (g^a)^b mod p дорівнює (g^b)^a mod p, обидва отримують однакову величину gab mod p без необхідності передавати її через канал.

Чому Діффі-Геллман важко зламати?

Зловсник, який знає g, p та обидва публічні значення A і B, повинен вирішити задачу розкладу логарифма, тобто знайти a таке, що g^a ≡ A (mod p) — щоб відновити приватний ключ. Не існує відомих ефективних класичних алгоритмів для цього з великими простими числами; найкращий відомий метод, Загальний Сieve полів чисел, займе більше часу, ніж вік Всесвіту для простих чисел довжиною 2048 біт.

Чи захищає Діффі-Геллман сам по собі від атак типу "зіпсовий посередник"?

Ні. Просте Діффі-Геллман забезпечує конфіденційність, але не аутентифікацію — зловмисник, який перехоплює з’єднання на початку, може провести два окремі обміни, видаючи себе за кожну сторону для іншої сторони. Реальний HTTPS поєднує Діффі-Геллман із сертифікатом, підписаним довіреною Центровою Атестацією Сертифікатів, щоб перевірити особу.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію the simulation