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

Протокол Ди́ффи-Хе́ллмана на эллиптических кривых (англ. Elliptic curve Diffie–Hellman, ECDH) — криптографический протокол, позволяющий двум сторонам, имеющим пары открытый/закрытый ключ на эллиптических кривых, получить общий секретный ключ, используя не защищённый от прослушивания канал связи[1] [2]. Этот секретный ключ может быть использован как для шифрования дальнейшего обмена, так и для формирования нового ключа, который затем может использоваться для последующего обмена информацией с помощью алгоритмов симметричного шифрования. Это вариация протокола Диффи-Хеллмана с использованием эллиптической криптографии[3].

Описание алгоритма

Пусть существуют два абонента: Алиса и Боб. Предположим, Алиса хочет создать общий секретный ключ с Бобом, но единственный доступный между ними канал может быть подслушан третьей стороной. Изначально должен быть согласован набор параметров (${\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].

Пример[8]

Эллиптическая кривая 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
• Эллиптическая криптография
• Протокол Диффи — Хеллмана

Примечания

1. An Efficient Protocol for Authenticated Key Agreement, 2003, p. 119.
2. Barker et al., 2013, p. 11.
3. Suite B Implementer’s Guide to NIST SP 800-56A, 2009, p. 8.
4. SEC 1: Elliptic Curve Cryptography, 2009, p. 63.
5. Barker et al., 2013, p. 40.
6. Barker et al., 2013, p. 20.
7. SEC 1: Elliptic Curve Cryptography, 2009, p. 30.
8. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых, 2006, p. 85.

Литература

• 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.