Протокол Діффі — Геллмана на еліптичних кривих

Протокол Діффі-Хеллмана на еліптичних кривих (англ. Elliptic curve Diffie–Hellman, ECDH) — криптографічний протокол, що дозволяє двом сторонам, які мають пари відкритий/закритий ключ на еліптичних кривих, отримати загальний секретний ключ, використовуючи незахищений від прослуховування канал зв'язку. Цей секретний ключ може бути використаний як для шифрування подальшого обміну, так і для формування нового ключа, який потім може використовуватися для подальшого обміну інформацією за допомогою алгоритмів симетричного шифрування. Це варіація протоколу Діффі — Геллмана з використанням еліптичної криптографії.

Опис алгоритму

Нехай існують два абоненти: Аліса і Боб. Припустимо, Аліса хоче створити спільний секретний ключ з Бобом, але єдиний доступний між ними канал може підслухати третя сторона. Спочатку повинен бути узгоджений набір параметрів ($(p,a,b,G,n,h)$ для загального випадку і $(m,f(x),a,b,G,n,h)$ для поля характеристики $2$). Відповідно у кожної сторони повинна бути пара ключів, що складається з закритого ключа $d$, (випадково обраного ціле число з інтервалу $[1,n-1]$) і відкритого ключа $Q$ (де $Q=d\cdot G$ - це результат того, що проробляє $d$ раз операції підсумовування елемента $G$). Нехай тоді пара ключів Аліси буде $(d_{A},Q_{A})$, а пара Боба $(d_{B},Q_{B})$. Перед виконанням протоколу сторони повинні обмінятися відкритими ключами.

Аліса обчислює $(x_{k},y_{k})=d_{A}\cdot Q_{B}$. Боб обчислює $(x_{k},y_{k})=d_{B}\cdot Q_{A}$. Загальний секрет — $x_{k}$ (x-координата цієї точки). Більшість стандартних протоколів, що базуються на ECDH, використовують функції формування ключа для отримання симетричного ключа значення $x_{k}$.

Обчислені значення учасниками рівні, так як $d_{A}\cdot Q_{B}=d_{A}\cdot d_{B}\cdot G=d_{B}\cdot d_{A}\cdot G=d_{B}\cdot Q_{A}$. З усієї інформації, пов'язаної зі своїм закритим ключем, повідомляє Аліса тільки свій відкритий ключ. Таким чином ніхто крім Аліси не може визначити її закритий ключ, крім учасника здатного вирішити задачу дискретного логарифмування на еліптичній кривій. Закритий ключ Боба аналогічно захищений. Ніхто крім Аліси або Боба не може обчислити їх загальний секрет, крім учасника здатного розв'язати проблему Діффі — Геллмана.

Відкриті ключі бувають або статичними (і підтверджені сертифікатом) або ефемерні (скорочено ECDHE). Ефемерні ключі використовуються тимчасово й не обов'язково аутентифікують відправника, таким чином, якщо потрібна автентифікація, підтвердження автентичності повинно бути отримано іншим способом. Автентифікація необхідна для виключення можливості атаки посередника. Якщо Аліса або Боб використовують статичний ключ, небезпека атаки посередника виключається, але не може бути забезпечена ні пряма секретність, ні стійкість до підміни при компрометації ключа, як і деякі інші властивості стійкості до атак. Користувачі статичних закритих ключів змушені перевіряти чужий відкритий ключ і використовувати функцію формування ключа на загальний секрет, щоб запобігти витоку інформації про статично закритий ключ. Для шифрування з іншими властивостями часто використовується протокол MQV.

При використанні загального секрету як ключа, часто бажано гешувать секрет, щоб позбутися від вразливостей, що виникли після застосування протоколу.

Приклад

Еліптична крива E над полем $GF(2^{163})$ має порядок $2\cdot P49$, де P49 — просте число складається з 49 цифр у десятковому записі.

$E:\quad Y^{2}+XY=X^{3}+X^{2}+1$

Виберемо Незвідний многочлен

$1+X+X^{2}+X^{8}+X^{163}$

І візьмемо точку еліптичної кривої

$P=(d42149e09429df4563ec1816488c92de89f93a9b2,~ccd18d6cc3042c4c17a213506345c80965ac19476)\neq 0$.

Перевіримо, що її порядок не дорівнює 2

$2P=(ccd18d6cc3042c4c17a213506345c809b5ac1d476,~835a2f56b88d6a249b4bd2a7550a4375e531d8a37)$.

Значить, її порядок дорівнює порядку групи $2\cdot P49$, а саме числу $P49$ і її можна використовувати для побудови ключа. Нехай $k_{A}=12$, $k_{b}=123$.. Тоді відкриті ключі учасників протоколу обчислюються як,

$k_{A}\cdot P=12\cdot P=(bd9776bbe87a8b1024be2e415952f527eee928b43,~c67a28ed7b137e756c37654f186a71bf64e5ac546)$.

$k_{B}\cdot P=123\cdot P=(a5684e246044fc126e9832d17513387e474290547,~568b4137f09f5f79a8a6b0fe44cdf41d8e68ae2c6)$.

А загальний секрет буде дорівнювати:

$k_{B}\cdot k_{A}\cdot P=k_{A}\cdot k_{B}\cdot P=12\cdot 123\cdot P=(bb7856cece13c71919534878bcb6f3a887d613c92,~f661ffdfe1ba8cb1b2ad17b6550c65aa6d4f07f41)$

В якості ключа симетричної системи використовується значення (або його частина) $x=bb7856cece13c71919534878bcb6f3a887d613c92$.

Програмне забезпечення

• Curve25519 — набір параметрів еліптичних і посилань, реалізований Даніелем Бернстайном на мові Сі.

Див. також

• MQV
• Еліптична криптографія
• Протокол Діффі — Геллмана

Література

• Elaine Barker, Lily Chen, Allen Roginsky, Miles Smid. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (англ.) // http://nvlpubs.nist.gov/ [Архівовано 10 березня 2018 у Wayback Machine.]. — National Institute of Standards and Technology, 2013. — ISBN 1495447502.
• Standards for Efficient Cryptography Group (SECG). SEC 1: Elliptic Curve Cryptography: [англ.]. — http://www.secg.org [Архівовано 24 березня 2022 у Wayback Machine.]. — Certicom Corp, 2009. — P. 15—28, 56—58.
• National Institute of Standards and Technology (NIST). Suite B Implementer's Guide to NIST SP 800-56A: [англ.]. — https://www.nsa.gov [Архівовано 9 грудня 2020 у Wayback Machine.]. — 2009.
• Laurie Law. An Efficient Protocol for Authenticated Key Agreement: [англ.] / Laurie Law, Alfred Menezes, Minghua Qu … [et al.]. — Designs, Codes and Cryptography. — Kluwer Academic Publishers, 2003. — Vol. 28, no. 2. — P. 119—134. — ISSN 0925-1022. — DOI:10.1023/A:1022595222606.
• Болотов А. А., Гашков С. Б., Фролов А. Б. Глава 2. Протоколы на эллиптических кривых // Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. — М.: КомКнига, 2006. — С. 83—86. — ISBN 5-484-00444-6, ББК 32.81, УДК 512.8.