Протокол Диффи — Хеллмана на эллиптических кривых

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

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

Вычисленные участниками значения равны, так как ${\displaystyle d_{A}\cdot Q_{B}=d_{A}\cdot d_{B}\cdot G=d_{B}\cdot d_{A}\cdot G=d_{B}\cdot Q_{A}}$. Из всей информации, связанной со своим закрытым ключом, Алиса сообщает только свой открытый ключ. Таким образом никто, кроме Алисы, не может определить её закрытый ключ, кроме участника, способного решить задачу дискретного логарифмирования на эллиптической кривой. Закрытый ключ Боба аналогично защищён. Никто, кроме Алисы или Боба, не может вычислить их общий секрет, кроме участника, способного разрешить проблему Диффи — Хеллмана[6].

Открытые ключи бывают либо статичными (и подтверждённые сертификатом) либо эфемерные (сокращённо ECDHE). Эфемерные ключи используются временно и не обязательно аутентифицируют отправителя, таким образом, если требуется аутентификация, подтверждение подлинности должно быть получено иным способом[3]. Аутентификация необходима для исключения возможности атаки посредника. Если Алиса либо Боб используют статичный ключ, опасность атаки посредника исключается, но не может быть обеспечена ни прямая секретность, ни устойчивость к подмене при компрометации ключа, как и некоторые другие свойства устойчивости к атакам. Пользователи статических закрытых ключей вынуждены проверять чужой открытый ключ и использовать функцию формирования ключа на общий секрет, чтобы предотвратить утечку информации о статично закрытом ключе[7]. Для шифрования с другими свойствами часто используется протокол MQV.

При использовании общего секрета в качестве ключа зачастую желательно хешировать секрет, чтобы избавиться от уязвимостей, возникших после применения протокола[7].

Эллиптическая кривая E над полем ${\displaystyle GF(2^{163})}$ имеет порядок ${\displaystyle 2\cdot P49}$, где P49 — простое число, состоящее из 49 цифр в десятичной записи.

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

Выберем неприводимый многочлен

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

И возьмём точку эллиптической кривой

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

Проверим, что её порядок не равен 2

${\displaystyle 2P=(ccd18d6cc3042c4c17a213506345c809b5ac1d476,~835a2f56b88d6a249b4bd2a7550a4375e531d8a37)}$.

Значит, её порядок равен порядку группы ${\displaystyle 2\cdot P49}$, а именно числу ${\displaystyle P49}$, и её можно использовать для построения ключа. Пусть ${\displaystyle k_{A}=12}$, ${\displaystyle k_{b}=123}$. Тогда открытые ключи участников протокола вычисляются как

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

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

А общий секрет будет равен:

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

В качестве ключа симметричной системы используется значение (или его часть) ${\displaystyle x=bb7856cece13c71919534878bcb6f3a887d613c92}$.

• Curve25519 — набор эллиптических параметров и ссылок, реализованный Daniel J. Bernstein на языке Си.

• MQV
• Эллиптическая криптография
• Протокол Диффи — Хеллмана

• Elaine Barker, Lily Chen, Allen Roginsky, Miles Smid. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography (англ.) // http://nvlpubs.nist.gov/. — National Institute of Standards and Technology, 2013. — ISBN 1495447502.
• Standards for Efficient Cryptography Group (SECG). SEC 1: Elliptic Curve Cryptography : [англ.]. — http://www.secg.org. — 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. — 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.