Еліптична крива Диффі-Хелмана: Обмін ключами на кривій

Що таке еліптична крива насправді?

Еліптична крива, що використовується в криптографії, не є еліпсом. Це множина точок, які задовольняють рівняння виду y² дорівнює x³ плюс ax плюс b, оцінене над кінцевим полем замість того, щоб оцінюватися над звичайними реальними числами. Кінцеве поле означає, що арифметичні операції обертаються modulo деякого великого простого числа, тому крива насправді є кінцевою сіткою дискретних точок, а не гладкою безперервною формою, хоча для візуалізації спочатку корисно уявити її як гладку криву. Будь-яка комбінація координат x і y, що задовольняє це рівняння, разом із додатковою спеціальною точкою, яка називається точкою в нескінченності, формує множину точок кривої. Точка в нескінченності діє як елемент-ідентичність, виконуючи ту ж роль, що й нуль у звичайній додаванні. Криптографічні протоколи обирають конкретну стандартизовану криву, а також конкретний базисний пункт на цій кривій, який називається генератором, часто позначається як G. Популярними варіантами є криві, названі P-256, Curve25519 і secp256k1, кожна з яких визначається певними константами a, b та певною розмірністю простого поля. Безпека всього, що будується на цій кривій, залежить від розміру цього базового поля та від того, що крива не має відомих структурних слабкостей. Те, що робить ці криві корисними для криптографії, полягає в тому, що їхні точки оснащені геометричним правилом додавання, яке перетворює множину точок на математичну групу. Ця структура групи дозволяє визначати та обчислювати ефективно скалярне множення, еліптична крива еквівалентна виключно експоненційному піднесенню. Все, що слідує – від генерації пар ключів до отримання спільного секрету – ґрунтується на цій одній ідеї: точки на ретельно обраній кривій можна комбінувати за допомогою добре визначеного правила додавання, а це правило поводиться достатньо передбачувано, щоб побудувати повний криптографічний протокол на його основі, але достатньо непередбачувано, щоб повторне відтворення операцій додавання було обчислювально неможливим для стороннього спостерігача.

Додавання точок: Геометричний двигун

Додавання еліптичних кривих має елегантний геометричний опис до того, як стає чистим алгебраїчним обчисленням. Щоб додати дві різні точки P та Q на кривій, уявіть собі пряму лінію через них. Через кубічне рівняння кривої ця лінія перетинає криву в точно одному додатковому пункті. Відбиваючи цей третій перетин у горизонтальній осі, отримують результат, який називається P плюс Q. Подвоєння окремої точки P, тобто обчислення P плюс P, працює аналогічно, але використовується дотична лінія до P замість лінії через дві різні точки, знову знаходячи, де ця дотична зустрічається з кривою вдруге і відбиваючи результат. У множині дійсних чисел все це має буквальне зображення з ліній та кривих; у кінцевому полі ті ж самі алгебраїчні формули застосовуються, просто координати обчислюються за допомогою модульної арифметики замість звичайної арифметики, тому геометричне зображення стає ментальною моделлю, а не тим, що ви б насправді намалювали. Водночас, цей додавання є замкненим операцією, тобто додавання двох точок на кривій завжди дає іншу точку на кривій, і воно відповідає тим самим асоціативним та комутативним правилам, які дотримуються звичайні додавання. Це саме те, що дозволяє повторному додаванню точки до самої себе, записане як скалярне множення, поводитися послідовно незалежно від того, як групуються або розташовуються ці додавання. Особливі випадки завершують визначення: додавання точки до точки на нескінченності повертає ту ж саму точку без змін, а додавання точки до її відображення через горизонтальну вісь, яке називається її оберненою, дає точку на нескінченності. Ці правила разом роблять множину точок на кривій, поєднану з цією операцією додавання, математичною групою, таким самим типом структури, як і цілі числа за модулем відносно простого числа під множенням у класичному Diffie-Hellman, але побудована з геометрії замість експоненційного обчислення.

Скалярне множення та подвійне-додавання

Скалярне множення приймає точку P та ціле число k і обчислює точку, досягнуту шляхом додавання P до себе k разів, що позначається як k разів P. Виконання цього шляхом додавання P по одному копію після іншого було б неймовірно повільно для великих значень k, які можуть бути сотнями біт завдовжки, в криптографії. Практичне рішення – алгоритм подвійного-додавання, прямий аналог техніки «піднесення до степеня та множення» (square-and-multiply), яка використовується для швидкого модульного піднесення до степеня у класичному Diffie-Hellman. Алгоритм розглядає бітове представлення k і обробляє його побітно, повторно подвоюючи прогінну точку та додаючи базову точку P за умови, що поточна біт дорівнює одиниці. Оскільки подвоєння точки займає приблизно таку ж кількість зусиль, як і додавання двох різних точок, і оскільки кількість бітів у k зростає лише логарифмічно з його розміром, алгоритм подвійного-додавання обчислює k разів P, використовуючи приблизно стільки ж операцій, скільки біт у k, а не окремих доданків. Для скаляра 256 біт це означає близько кількох сотень операцій з точками замість астрономічної кількості індивідуальних доданків, що робить скалярне множення цілком практичним навіть на відносно невеликому обладнанні. Ця ефективність є причиною того, що генерація ключів на еліптичних кривих та обмін ключами самі по собі достатньо швидкі для повсякденного використання в браузерах, мобільних додатках і мережевих протоколах. Елегантність алгоритму подвійного-додавання полягає в тому, що вона точно відображає те, як люди ефективно обчислюють великі степені шляхом повторного піднесення до степеня, просто перекладена на мову додавання точок.

Еліптична крива Диффі-Хелмана: Обмін ключами на кривій

Ця безпека в цілому ґрунтується на одній асиметрії: якщо відомо базову точку G та скаляр k, то швидке обчислення результатної точки Q дорівнює k * G, але якщо відомі лише G та Q, відновлення скаляра k вважається обчислювально неможливим для добре підібраних кривих і достатніх розмірів поля. Це називається проблемою дискретного логарифмування на еліптичній кривій, часто скорочено ECDLP, і вона відіграє ту ж структурну роль, що й класична проблема дискретного логарифмування в традиційному Diffie-Hellman над полем, що складається з простих чисел. Ключова різниця полягає в тому, наскільки важко кожна задача у порівнянні з розміром використовуваних чисел. Найкращі відомі алгоритми для розв’язування класичної проблеми дискретного логарифмування в простому полі працюють за допомогою підвиродженого часу, тобто вони швидші за грубу силу, але все ще повільні, що змушує класичний Diffie-Hellman використовувати дуже великі прості числа, зазвичай близько трьох тисяч семисот двох біт, щоб залишатися безпечним. Найкращі відомі загальні алгоритми для розв’язування еліптичної кривої дискретного логарифмування, навпаки, працюють у повністю експоненційному часі відносно розміру поля, без відомих скорочень, аналогічних підвиродженим атакам, які працюють проти класичної проблеми. Це сильніше гарантія складності означає значно менший розмір еліптичної кривої поля, зазвичай близько двохсот п'ятдесяти шість біт, який забезпечує порівнянний рівень захисту від атак. Спостерігач, який перехоплює обидва обмінені публічні точки, бачить G та публічні точки обох сторін, по суті бачачи Q1 і Q2, але відновлення будь-якого з приватних скалярів з цієї інформації потребуватиме розв’язання ECDLP, проблеми, для якої невідомий ефективний алгоритм навіть із значними обчислювальними ресурсами. Ця прогалина між швидким вперед-обчисленням і важкою реверсією є тим, що перетворює просте арифметичне обчислення точок на надійний криптографічний примітив.

Зв’язок і чому менші ключі важливі

Об'єднуючи всі частини, розгортається ECDH handshake у кількох чітких кроках. Обидва учасники заздалегідь погоджуються на спільну криву та спільний базовий пункт G, які є публічними та стандартизованими. Кожен учасник потім приватно обирає випадковий скаляр, виконуючи роль приватного ключа, назвемо його скаляр A для першого учасника та скаляр B для другого. Кожен обчислює свою публічну точку шляхом множення базового пункту на свій власний скаляр, що дає публічну точку A дорівнює скаляр A помножений на G, і публічну точку B дорівнює скаляр B помножений на G. Обидві сторони обмінюються цими публічними точками відкрито, навіть через канал, який може спостерігати зловмышленник. Нарешті, кожна сторона множить публічну точку іншої сторони на свій власний приватний скаляр. Перша сторона обчислює скаляр A помножений на публічну точку B, а друга сторона обчислює скаляр B помножений на публічну точку A. Оскільки множення скалярів асоціативний і комутативний в основній групі, обидва обчислення дорівнюють скаляр A помножений на скаляр B помножений на G, що означає, що обидві сторони потрапляють у один і той же спільний секретний пункт без необхідності передавати свої приватні скаляри. Цей спільний пункт або значення, отримане з його координат за допомогою функції виведення ключа, стає симетричним ключем, який використовується для подальшого шифрування комунікації. Практична вигода від вибору кривих замість полів із простим множенням поля полягає в розмірі: 256-бітова крива Еліптичного ключа забезпечує рівень безпеки, приблизно порівнянний з 3072-бітним кінцевим полем Diffie-Hellman ключем, що означає менші повідомлення, швидше генерування ключів, менше використання пам'яті та ЦП і нижле енергоспоживання. Ця перевага в ефективності є точно тому, чому ECDH, а не класичний Diffie-Hellman лежить в основі обміну ключами у сучасних з’єднаннях TLS та HTTPS, протоколі Signal, що використовується в безпечних додатках для обміну повідомленнями, і віртуальній приватній мережі WireGuard протоколі, всі з яких залежать від швидкого, легкого та повторюваного узгодження ключів.

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Elliptic Curve Diffie-Hellman: Key Exchange on a Curve і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.