Русская Википедия:Протокол Диффи — Хеллмана на эллиптических кривых
Протокол Ди́ффи-Хе́ллмана на эллиптических кривых (Шаблон:Lang-en, ECDH) — криптографический протокол, позволяющий двум сторонам, имеющим пары открытый/закрытый ключ на эллиптических кривых, получить общий секретный ключ, используя незащищённый от прослушивания канал связиШаблон:Sfn Шаблон:Sfn. Этот секретный ключ может быть использован как для шифрования дальнейшего обмена, так и для формирования нового ключа, который затем может использоваться для последующего обмена информацией с помощью алгоритмов симметричного шифрования. Это вариация протокола Диффи-Хеллмана с использованием эллиптической криптографииШаблон:Sfn.
Описание алгоритма
Пусть существуют два абонента: Алиса и Боб. Предположим, Алиса хочет создать общий секретный ключ с Бобом, но единственный доступный между ними канал может быть подслушан третьей стороной. Изначально должен быть согласован набор параметров (<math>(p,a,b,G,n,h)</math> для общего случая и <math>(m,f(x),a,b,G,n,h)</math> для поля характеристики <math>2</math>). Так же у каждой стороны должна иметься пара ключей, состоящая из закрытого ключа <math>d</math> (случайно выбранное целое число из интервала <math>[1,n-1]</math>) и открытого ключа <math>Q</math> (где <math>Q=d \cdot G</math> — это результат проделывания <math>d</math> раз операции суммирования элемента <math>G</math>). Пусть тогда пара ключей Алисы будет <math>(d_A, Q_A)</math>, а пара Боба <math>(d_B, Q_B)</math>. Перед исполнением протокола стороны должны обменяться открытыми ключами.
Алиса вычисляет <math>(x_k, y_k) = d_A \cdot Q_B </math>. Боб вычисляет <math>(x_k, y_k) = d_B \cdot Q_A </math>. [[|en]] (Shared secret) — <math>x_k</math> (x-координата получившейся точки). Большинство стандартных протоколов, базирующихся на ECDH, используют функции формирования ключа для получения симметричного ключа из значения <math>x_k</math>Шаблон:SfnШаблон:Sfn.
Вычисленные участниками значения равны, так как <math>d_A \cdot Q_B = d_A \cdot d_B \cdot G = d_B \cdot d_A \cdot G = d_B \cdot Q_A </math>. Из всей информации, связанной со своим закрытым ключом, Алиса сообщает только свой открытый ключ. Таким образом никто, кроме Алисы, не может определить её закрытый ключ, кроме участника, способного решить задачу дискретного логарифмирования на эллиптической кривой. Закрытый ключ Боба аналогично защищён. Никто, кроме Алисы или Боба, не может вычислить их общий секрет, кроме участника, способного разрешить проблему Диффи — ХеллманаШаблон:Sfn.
Открытые ключи бывают либо статичными (и подтверждённые сертификатом) либо эфемерные (сокращённо ECDHE). Эфемерные ключи используются временно и не обязательно аутентифицируют отправителя, таким образом, если требуется аутентификация, подтверждение подлинности должно быть получено иным способомШаблон:Sfn. Аутентификация необходима для исключения возможности атаки посредника. Если Алиса либо Боб используют статичный ключ, опасность атаки посредника исключается, но не может быть обеспечена ни прямая секретность, ни устойчивость к подмене при компрометации ключа, как и некоторые другие свойства устойчивости к атакам. Пользователи статических закрытых ключей вынуждены проверять чужой открытый ключ и использовать функцию формирования ключа на общий секрет, чтобы предотвратить утечку информации о статично закрытом ключеШаблон:Sfn. Для шифрования с другими свойствами часто используется протокол MQV.
При использовании общего секрета в качестве ключа зачастую желательно хешировать секрет, чтобы избавиться от уязвимостей, возникших после применения протоколаШаблон:Sfn.
ПримерШаблон:Sfn
Эллиптическая кривая E над полем <math> GF(2^{163})</math> имеет порядок <math>2 \cdot P49</math>, где P49 — простое число, состоящее из 49 цифр в десятичной записи.
- <math>E:\quad Y^2 + XY = X^3 + X^2 + 1</math>
Выберем неприводимый многочлен
- <math>1 + X + X^2 + X^8 + X^{163}</math>
И возьмём точку эллиптической кривой
- <math>P = (d42149e09429df4563ec1816488c92de89f93a9b2,~ ccd18d6cc3042c4c17a213506345c80965ac19476)\ne 0</math>.
Проверим, что её порядок не равен 2
- <math>2P = (ccd18d6cc3042c4c17a213506345c809b5ac1d476,~ 835a2f56b88d6a249b4bd2a7550a4375e531d8a37)</math>.
Значит, её порядок равен порядку группы <math>2\cdot P49</math>, а именно числу <math>P49</math>, и её можно использовать для построения ключа. Пусть <math>k_A = 12</math>, <math>k_b = 123</math>. Тогда открытые ключи участников протокола вычисляются как
- <math>k_A\cdot P = 12\cdot P = (bd9776bbe87a8b1024be2e415952f527eee928b43,~ c67a28ed7b137e756c37654f186a71bf64e5ac546)</math>.
- <math>k_B\cdot P = 123\cdot P = (a5684e246044fc126e9832d17513387e474290547,~ 568b4137f09f5f79a8a6b0fe44cdf41d8e68ae2c6)</math>.
А общий секрет будет равен:
- <math>k_B\cdot k_A\cdot P = k_A\cdot k_B\cdot P = 12\cdot 123\cdot P = (bb7856cece13c71919534878bcb6f3a887d613c92,~ f661ffdfe1ba8cb1b2ad17b6550c65aa6d4f07f41)</math>.
В качестве ключа симметричной системы используется значение (или его часть) <math>x = bb7856cece13c71919534878bcb6f3a887d613c92</math>.
Программное обеспечение
- Curve25519 — набор эллиптических параметров и ссылок, реализованный Daniel J. Bernstein на языке Си.
См. также
Примечания
Литература
Шаблон:Криптосистемы с открытым ключом
