Просмотр кода страницы Эллиптическая криптография

'''Эллиптическая криптография''' — раздел [[Криптография|криптографии]], который изучает [[Криптосистема с открытым ключом|асимметричные криптосистемы]], основанные на [[Эллиптическая кривая|эллиптических кривых]] над [[Конечное поле|конечными полями]]. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день неизвестны субэкспоненциальные [[алгоритмы]] [[Дискретное логарифмирование|дискретного логарифмирования]].

Использование эллиптических кривых для создания криптосистем было независимо друг от друга предложено [[Коблиц, Нил|Нилом Коблицем]] и [[Миллер, Виктор (математик)|Виктором Миллером]] в [[1985 год]]у<ref>{{книга |автор=Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman |заглавие=An introduction to mathematical cryptography |ссылка=https://books.google.ru/books?id=XLY9AnfDhsYC&lpg=PA301 |издательство=Springer |год=2008 |страница=301 |страниц=524 |серия=Undergraduate Texts in Mathematics |isbn=9780387779942}}</ref>.

== Введение ==
В 1985 году независимо Нилом Коблицем и Виктором Миллером было предложено использовать в криптографии алгебраические свойства [[Эллиптическая кривая|эллиптических кривых]]. С этого момента началось бурное развитие нового направления криптографии, для которого используется термин «криптография на эллиптических кривых». Роль основной криптографической операции выполняет операция [[Скалярное произведение|скалярного умножения]] точки на эллиптической кривой на данное целое число, определяемая через операции сложения и удвоения точек эллиптической кривой. Последние, в свою очередь, выполняются на основе операций сложения, умножения и инвертирования в конечном поле, над которыми рассматривается кривая. Особый интерес к криптографии эллиптических кривых обусловлен теми преимуществами, которые дает её применение в беспроводных коммуникациях — высокое быстродействие и небольшая длина ключа<ref>''Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А.''. Элементарное введение в эллиптическую криптографию. 11 с.</ref>. Асимметричная криптография основана на сложности решения некоторых математических задач. Ранние криптосистемы с открытым ключом, такие как алгоритм [[RSA]], криптостойки благодаря тому, что сложно разложить составное число на простые множители. При использовании алгоритмов на эллиптических кривых полагается, что не существует субэкспоненциальных [[Алгоритмы|алгоритмов]] для решения задачи дискретного логарифмирования в группах их точек. При этом [[порядок группы]] точек эллиптической кривой определяет сложность задачи. Считается, что для достижения такого же [[Уровень криптостойкости|уровня криптостойкости]], как и в RSA, требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 [[Агентство национальной безопасности]] объявило о создании «Suite B», в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации, классифицируемой до «Top Secret», используются всего лишь 384-битные ключи.

== Эллиптические кривые над конечными полями ==

{{main|Эллиптическая кривая}}

Эллиптической кривой называется множество точек <math>(x,y)</math>, удовлетворяющих уравнению:
: <math>y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6</math>
Это уравнение может рассматриваться над произвольными полями и, в частности, над [[Конечное поле|конечными полями]], представляющими для криптографии особый интерес.

В криптографии эллиптические кривые рассматриваются над двумя типами [[конечное поле|конечных полей]]: простыми полями нечётной [[Характеристика поля|характеристики]] (<math>\mathbb{Z}_p</math>, где <math>p > 3</math> — простое число) и полями характеристики 2 (<math>GF(2^m)</math>).

== Эллиптические кривые над полями нечётной характеристики ==

Над полем <math>\mathbb{Z}_p</math> характеристики <math>p>3</math> уравнение эллиптической кривой ''E'' можно привести к виду:
: <math>E:\quad y^2 = x^3 + Ax + B \pmod p,</math>
где <math>A, B \in \mathbb{Z}_p</math> — константы, удовлетворяющие <math>4A^3 + 27B^2 \not\equiv 0 \pmod p</math>.

Группой точек эллиптической кривой ''E'' над полем <math>\mathbb{Z}_p</math> называется множество пар <math>(x,y)</math>, лежащих на ''E'', объединённое с нулевым элементом <math>\mathcal{O}</math>:
: <math>E(\mathbb{Z}_p) = \mathcal{O} \cup \left\{ (x, y) \in \mathbb{Z}_p \times \mathbb{Z}_p | y^2 \equiv x^3 + Ax + B \pmod p \right\}.</math>

Следует отметить, что в <math>\mathbb{Z}_p</math> у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида <math>(x, y)</math> и <math>(x, -y)</math>.

=== Пример ===
Рассмотрим эллиптическую кривую <math>y^2 = x^3 + 3x + 2</math> над полем <math>\mathbb{Z}_5</math>. На этой кривой, в частности, лежит точка <math>(1,1)</math>, так как <math>1^2 \equiv 1^3 + 3 \cdot 1 + 2 \pmod 5</math>. Легко проверить, что точки <math>(1,\pm 1)</math>, <math>(1,\pm 4)</math>, <math>(2,\pm 1)</math>, <math>(2,\pm 4)</math> это все точки данной кривой.

== Теорема Хассе ==

{{main|Теорема Хассе}}

Теорема Хассе об эллиптических кривых утверждает, что количество  точек на эллиптической кривой близко к размеру конечного поля: 
: <math>(\sqrt p - 1)^2 \leqslant |E(\mathbb{Z}_p)| \leqslant (\sqrt p + 1)^2,</math>
что влечёт:
: <math>\left| |E(\mathbb{Z}_p)|-p\right| < 2\sqrt p + 1.</math>

== Эллиптические кривые над полями характеристики 2 ==
Над полем характеристики 2 рассматривают два вида эллиптических кривых:
* Суперсингулярная кривая
*: <math>y^2+ay=x^3+bx+c</math>
* Несуперсингулярная кривая
*: <math>y^2+axy=x^3+bx^2+c</math>

Особое удобство суперсингулярных эллиптических кривых в том, что для них легко вычислить порядок, в то время как вычисление порядка несуперсингулярных кривых вызывает трудности. Суперсингулярные кривые особенно удобны для создания самодельной ЕСС (Elliptic-curve cryptography) криптосистемы. Для их использования можно обойтись без трудоёмкой процедуры вычисления порядка.

== Проективные координаты ==

Для вычисления суммы пары точек на эллиптической кривой требуется не только несколько операций сложения и умножения в <math>\mathbb{F}_q</math>, но и операция [[обратный элемент|обращения]], то есть для заданного <math>x \in \mathbb{F}_q</math> нахождение такого <math>y \in \mathbb{F}_q</math>, что <math>xy = 1</math>, которая на один-два порядка медленнее, чем умножение. К счастью, точки на эллиптической кривой могут быть представлены  в различных [[система координат|системах координат]], которые не требуют использования обращения при сложении точек:
* в [[проективная плоскость|проективной]] системе координат каждая точка <math>(x,y)</math> представляется тремя координатами <math>(X,Y,Z)</math>, которые удовлетворяют соотношениям:
*: <math>x = \frac{X}{Z}</math>, <math>y = \frac{Y}{Z}</math>.
* в системе координат [[Якоби, Карл Густав Якоб|Якоби]] точка также представляется тремя координатами <math>(X,Y,Z)</math> с соотношениями: <math>x = \frac{X}{Z^2}</math>, <math>y = \frac{Y}{Z^3}</math>.
* в системе координат Лопес-Дахаб (洛佩斯·達哈卜 кит. / Lopez-Dahab лат.) выполняется соотношение: <math>x = \frac{X}{Z}</math>, <math>y = \frac{Y}{Z^2}</math>.
* в модифицированной системе координат Якоби используются 4 координаты <math>(X,Y,Z,aZ^4)</math> с теми же соотношениями.
* в системе координат Чудновского-Якоби используется 5 координат <math>(X,Y,Z,Z^2,Z^3)</math>.

Важно отметить, что могут существовать различные именования — например, [[IEEE P1363|IEEE P1363-2000]] называет проективными координатами то, что обычно называют координатами Якоби.

== Шифрование/дешифрование с использованием эллиптических кривых ==

Первой задачей в рассматриваемой системе является шифрование [[Открытый текст|открытого текста]] сообщения <math>m</math>, {{H:title|Наверняка, здесь имелась в виду сама точка P_m и пара её коодинат P_m(x, y), либо результат конкатенации координат x+y, а не разница двух координат (x - y).|которое должно будет пересылаться в виде значения <math>x-y</math>}} {{H:title|А вот как-то так сообщение кодируется в точки на эллиптической кривой в конечном поле, и декодируется из них - назад. Смотреть код по ссылке. При этом, существует информационная избыточность в шифротексте, так как не все числа от 0 до p - являются координатами уникальных точек, обязательно лежащих на эллиптической кривой, и одно число от 0 до p - может быть закодировано двумя и более точками.|(Как?)}}<ref>{{Cite news|title=Кодирование чисел в точки на эллиптической кривой в конечном поле и шифрование-дешифрование их.|url=https://github.com/username1565/mini_ecdsa/commit/54d2ba23973819806e85456941c3c1a099434bc7|accessdate=2019-10-29}}</ref> для точки <math>P_m</math>. Здесь точка <math>P_m</math> будет представлять закодированный в неё текст и впоследствии будет раскодироваться. Обратите внимание, невозможно закодировать сообщение просто координатой <math>x</math> или <math>y</math> точки, так как не все такие координаты имеются в <math>E_p(a, b)</math>.<br />
Как и в случае системы обмена ключами, в системе шифрования, расшифрования в качестве параметров тоже рассматривается точка <math>G</math> и эллиптическая группа <math>E_p(a, b)</math>. Пользователь <math>A</math> выбирает личный ключ <math>n_A</math> и генерирует [[Инфраструктура открытых ключей|открытый ключ]] <math>P_A=n_AG</math>. Чтобы зашифровать и послать сообщение <math>P_m</math> пользователю <math>B</math>, пользователь <math>A</math> выбирает случайное положительное целое число <math>k</math> и вычисляет шифрованный текст <math>G_m</math>, состоящий из пары точек <br />
:<math>G_m = (kG, P_m + kP_B)</math>. При этом, <math>G_m \ne P_m, G_m</math> — пара точек.
Заметим, что сторона <math>A</math> использует открытый ключ стороны <math>B</math>: <math>P_B</math>. Чтобы дешифровать этот шифрованный текст, <math>B</math> умножает первую точку в паре на секретный ключ <math>n_B</math> и вычитает результат из второй точки: <br /><math>(P_m + kP_B) - n_B(kG)=P_m + k(n_BG) - n_B(kG) = P_m + \cancel{kn_B(G)} - \cancel{kn_B(G)} = P_m</math>

Пользователь <math>A</math> замаскировал сообщение <math>P_m</math> с помощью добавления к нему <math>kP_B</math>. Никто, кроме этого пользователя не знает значения <math>k</math>, поэтому, хотя <math>P_B</math> и является открытым ключом, никто не сможет убрать маску <math>kP_B</math>. Однако, пользователь <math>A</math> включает в сообщение и "подсказку", которой будет достаточно, чтобы убрать маску тому, кто имеет личный ключ <math>n_B</math>. Противнику для восстановления сообщения придется вычислить <math>k</math> по данным <math>G</math> и <math>kG</math>, что представляется трудной задачей<ref>Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. 167 с.</ref>.

Арифметические операции с точками на эллиптической кривой не эквивалентны этим арифметическим операциям с их координатами.

Точки эллиптической кривой над конечным полем представляют собой группу<ref>{{Cite news|title=Эллиптическая криптография: теория|url=https://habrahabr.ru/post/188958/|accessdate=2016-10-13|archive-date=2016-10-13|archive-url=https://web.archive.org/web/20161013221257/https://habrahabr.ru/post/188958/|url-status=live}}</ref>. Умножение сводится к многократным удвоению и суммированию.

Например, G+G ≠ 2G ({{H:title|Вообще-то это одна и та же операция, но здесь скорее, имеется в виду то, что осуществляются они разными алгоритмами.|это разные операции}}), 2G + 2^115G = 2^115G + 2G (суммирование коммутативно);

2G = 2*G; 4G = 2*2G; 8G = 2*4G; 16G = 2*8G, и т. д. (для двух одинаковых точек — только операция удвоения);

25*G; 25 = 11001 (in binary); 25 = 1*2^0 + 0*2^1 + 0*2^2 + 1*2^3 + 1*2^4 = 1 + 8 + 16; 25G = 16G + 8G + G = 1*(2^4)G + 1*(2^3)G + 1*G (операция суммирования).

24G/3 = 24G * (3^-1 mod P); where 3^(-1) mod P - '''[[Обратное по модулю число]],'''

5G - 3G = 5G + (-3G); где -3G = nG - 3G = O - 3G - '''[[Эллиптическая кривая]].'''

=== Пример ===

Рассмотрим случай <math>p=751</math>, <math>E_p(-1,188)</math>, что соответствует кривой <br />
:<math>y^2=x^3-x+188</math> и <math>G=(0, 376)</math>.
Предположим, что пользователь <math>A</math> собирается отправить пользователю <math>B</math> сообщение, которое кодируется эллиптической точкой <math>P_m=(562, 201)</math>, и что пользователь <math>A</math> выбирает случайное число <math>k=386</math>. Открытым ключом <math>B</math> является <math>P_B=(201, 5)</math>. Имеем: <br />
:<math>386(0, 376)=(676, 558)</math>
:<math>(562, 201) + 386(201, 5) = (385, 328)</math>.
Таким образом, пользователь <math>A</math> должен послать шифрованный текст <math>(676, 558),(385, 328)</math>.

== Реализация шифрования ==
Конкретные реализации алгоритмов шифрования на эллиптической кривой описаны ниже. Здесь рассмотрим общие принципы эллиптической криптографии.

=== Набор параметров ===

Для использования эллиптической криптографии все участники должны согласовать все параметры, определяющие эллиптическую кривую, т. е. набор параметров криптографического протокола. Эллиптическая кривая определяется константами <math>a</math> и <math>b</math> из уравнения (2). [[Абелева группа|Абелева]] подгруппа точек является [[циклическая группа|циклической]] и задается одной [[Порождающее множество группы|порождающей]] точкой ''G''. При этом кофактор <math>h = \frac{|E|}{n}</math>, где ''n'' —  [[Порядок элемента группы|порядок]] точки ''G'', должен быть небольшим (<math>h\le4</math>, желательно даже <math>h=1</math>).

Итак, для поля характеристики 2 набор параметров: <math>(m,f,a,b,G,n,h)</math>, а для конечного поля <math>\mathbb{Z}_p</math>, где <math>p>3</math>, набор параметров: <math>(p,a,b,G,n,h)</math>.

Существует несколько рекомендованных наборов параметров: 
* NIST<ref>{{Cite web |url=http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |title=Recommended Elliptic Curves for Government Use |access-date=2009-12-16 |archive-date=2011-06-05 |archive-url=https://web.archive.org/web/20110605101110/http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf |url-status=live }}</ref>
* SECG<ref>[https://web.archive.org/web/20050531214022/http://www.secg.org/download/aid-386/sec2_final.pdf SEC 2: Recommended Elliptic Curve Domain Parameters]</ref>

Для создания собственного набора параметров необходимо сделать следующее.
# Выбрать набор параметров.
# Найти эллиптическую кривую, удовлетворяющую этому набору параметров.

Для нахождения кривой для заданного набора параметров используются два метода.
* Выбрать случайную кривую, затем воспользоваться алгоритмом подсчета точек<ref>[http://www-math.mit.edu/~musiker/schoof.pdf Schoof's algorithm]{{Недоступная ссылка|date=Январь 2018 |bot=InternetArchiveBot }}</ref><ref>[https://web.archive.org/web/20110726052703/http://www.esat.kuleuven.be/cosic/eurocrypt2000/pdf/fre-sea.pdf Schoof–Elkies–Atkin algorithm]</ref>.
* Выбрать точки, после чего построить кривую по этим точкам, используя технику умножения.

Существует несколько классов [[криптостойкость|криптографически «слабых»]] кривых, которых следует избегать:
* Кривые над <math>\mathbb{F}_{2^m}</math>, где <math>m</math> — не простое число. Шифрование на этих кривых подвержено [[Атака Вейля|атакам Вейля]].
* Кривые с <math>|E(\mathbb{F}_q)| = q</math> уязвимы для атаки, которая отображает точки данной кривой в аддитивную группу поля <math>\mathbb{F}_q</math>.

=== Быстрая редукция (NIST-кривые) ===

Деление по модулю ''p'' (которое необходимо для операций сложения и умножения) может выполняться быстрее, если в качестве ''p'' выбрать простое число, близкое к степени числа 2.
В частности, в роли ''p'' может выступать простое [[число Мерсенна]]. Например, хорошим выбором являются <math>p=2^{251} - 1</math> или <math>p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1</math>. 
[[Национальный институт стандартов и технологий (США)|Национальный институт стандартов и технологий]] (NIST) рекомендует использовать подобные простые числа в качестве ''p''.

Ещё одним преимуществом кривых, рекомендованных NIST, является выбор значения <math>a = -3</math>, что ускоряет операцию сложения в координатах Якоби.

=== Эллиптические кривые, рекомендованные NIST ===

NIST рекомендует 15 эллиптических кривых, многие из которых были получены Jerry Solinas (NSA) на базе наработок [[Коблиц, Нил|Нила Коблица]]<ref>{{книга|автор=Neal Koblitz|заглавие=Random Curves: Journeys of a Mathematician|ссылка=https://books.google.ru/books?id=p2QalcsaNtIC&pg=PA312&|издательство=Springer|год=2009 |страницы=312-313|страниц=402|isbn=9783540740780|qoute="In 1991 I proposed using certain curves... This idea was developed and improved upon by Jerry Solinas of NSA. The very first paper ever presented publicly ..by an NSA nenber was Jerry's analysis"}}</ref>. В частности, [[Федеральные стандарты обработки информации|FIPS]] 186-3<ref>[http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf FIPS 186-3] {{webarchive|url=https://web.archive.org/web/20131007234125/http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf%E2%80%8E |date=2013-10-07 }} // NIST, 2009; устарел в 2013 году с выходом FIPS 186-4</ref> рекомендует 10 конечных полей. Некоторые из них: 
* поля <math>\mathbb{F}_p</math>, где простое ''p'' имеет длину 192, 224, 256, 384 или 521<ref>Может показаться, что в этой последовательности допущена ошибка. Однако, последняя величина именно 521, а не 512 битов.</ref> [[бит]], 
* поля <math>\mathbb{F}_{2^m}</math>, где ''m'' = 163, 233, 283, 409 или 571.

Причём для каждого конечного поля рекомендуется одна эллиптическая кривая. Эти конечные поля и эллиптические кривые выбраны, как часто ошибочно считается, из-за высокого уровня безопасности. По заявлениям NIST, их выбор был обоснован эффективностью программной реализации<ref>[[Daniel J. Bernstein]], Tanja Lange, [http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf Security dangers of the NIST curves] {{Wayback|url=http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf|date=20151220022548}} // 2013.09.16: "Why did NIST choose these curves? * Most people we have asked: security * Actual NIST design document: eficiency" ([http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf] {{Wayback|url=http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf|date=20131220060425}})</ref>. Имеются сомнения в безопасности по крайней мере нескольких из них<ref>{{cite web|url=http://safecurves.cr.yp.to/index.html|title=SafeCurves: choosing safe curves for elliptic-curve cryptography.|author=Daniel J. Bernstein and Tanja Lange|date=2013-11-18|publisher=safecurves.cr.yp.to|lang=en|accessdate=2013-12-20|archive-date=2013-12-20|archive-url=https://web.archive.org/web/20131220060425/http://safecurves.cr.yp.to/index.html|url-status=live}}</ref><ref>{{cite news|url=http://www.computerra.ru/82902/elliptic-crypto/|title=Сноуден и эллиптическое крипто: Bitcoin и TOR вне подозрений, но что с другими проектами?|author=Евгений Золотов|date=2013-09-16|publisher=Компьютерра|accessdate=2013-12-20|archive-date=2013-12-20|archive-url=https://web.archive.org/web/20131220033912/http://www.computerra.ru/82902/elliptic-crypto/|url-status=live}}</ref><ref>Dr Michael Scott, [http://www.certivox.com/blog/bid/344797/Backdoors-in-NIST-elliptic-curves Backdoors in NIST elliptic curves] {{Wayback|url=http://www.certivox.com/blog/bid/344797/Backdoors-in-NIST-elliptic-curves |date=20131220045637 }}, Oct 24, 2013: "The curves themselves were suggested by Jerry Solinas who worked at the NSA."</ref>.

=== Размер ключа ===

Самым быстрым алгоритмом, решающим задачу дискретного логарифмирования на эллиптических кривых, таким как [[алгоритм Шенкса]] и [[ρ-метод Полларда дискретного логарифмирования|ρ-метод Полларда]], необходимо <math>O(\sqrt{n})</math> операций. Поэтому размер поля должен как минимум в два раза превосходить размер ключа. Например, для 128-битного ключа рекомендуется использовать эллиптическую кривую над полем <math>\mathbb{F}_p</math>, где ''p'' имеет длину 256 бит.

Самые сложные схемы на эллиптических кривых, публично взломанные к настоящему времени, содержали 112-битный ключ для конечного простого поля и 109-битный ключ для конечного поля характеристики 2{{нет АИ|20|12|2013}}.
В июле [[2009 год]]а кластер из более чем двухсот [[PlayStation 3|Sony Playstation 3]] за 3,5 месяца нашел 109-битный ключ. Ключ над полем характеристики 2 был найден в апреле [[2004 год]]а, с использованием 2600 компьютеров, в течение 17 месяцев{{нет АИ|20|12|2013}}.

== Аналог обмена ключами по алгоритму Диффи-Хеллмана ==

Предположим, что абоненты А и Б хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего, они открыто выбирают какое-либо конечное поле <math>F_q</math> и какую-либо эллиптическую кривую <math>E</math> над ним. Их ключ строится по случайной точке <math>P</math> на этой эллиптической кривой. Если у них есть случайная точка <math>P</math>, то, например, её <math>x</math>-координата дает случайный элемент <math>F_q</math>, который можно затем преобразовать в <math>r</math>-разрядное целое число в <math>p</math>-ичной системе счисления (где <math>r q = p</math> ), и это число может служить ключом в их классической криптосистеме. Они должны выбрать точку <math>P</math> так, чтобы все их сообщения друг другу были открытыми и все же никто, кроме них двоих, ничего бы не знал о <math>P</math>.

Абоненты (пользователи) А и Б первым делом открыто выбирают точку <math>B</math> ∈ <math>E</math> в качестве «основания»; <math>B</math> играет ту же роль, что образующий <math>q</math> в системе Диффи-Хеллмана для конечных полей. Однако, не требуем, чтобы <math>B</math> была образующим элементом в группе точек кривой <math>E</math>. Эта группа может и не быть циклической. Даже если она циклическая, не будем тратить время на проверку того, что <math>B</math> — образующий элемент (или даже на нахождение общего числа N точек, которое нам не понадобится в последующем). Нам хотелось бы, чтобы порожденная В подгруппа была большой, предпочтительно того же порядка величины, что и сама <math>E</math>. Пока что предположим, что <math>B</math> — взятая открыто точка на <math>E</math> весьма большого порядка (равного либо <math>N</math>, либо большому делителю <math>N</math>).

Чтобы образовать ключ, <math>A</math> вначале случайным образом выбирает целое число <math>a</math>, сравнимое по порядку величины с <math>q</math> (которое близко к <math>N</math>); это число он держит в секрете.
Он вычисляет <math>aB</math> ∈ <math>E</math> и передает эту точку открыто. Абонент Б делает то же самое: он выбирает случайно <math>b</math> и открыто передает <math>bB</math> ∈ <math>E</math>. Тогда используемый ими секретный ключ — это <math>P = abB</math> ∈ <math>E</math>. Оба пользователя могут вычислить этот ключ. Например, <math>A</math> знает <math>bB</math> (точка была передана открыто) и своё собственное секретное <math>a</math>. Однако любая третья сторона знает лишь <math>aB</math> и <math>bB</math>. Кроме решения задачи дискретного логарифмирования — нахождения а по <math>B</math> и <math>aB</math> (или нахождения <math>b</math> по <math>B</math> и <math>bB</math>) по-видимому, нет способа найти <math>abB</math>, зная лишь <math>aB</math> и <math>bB</math><ref>''Чалкин Т.А. Жданов О.Н.'' Применение эллиптических кривых в криптографии.</ref>.

=== Пример обмена ключами по схеме Диффи-Хеллмана ===

В качестве примера возьмем 
:<math>p=211</math>, <math>E_p(0, -4)</math>,
что соответствует кривой
:<math>y^2=x^3-4</math>

== Безопасность криптографии с использованием эллиптических кривых ==
Безопасность, обеспечиваемая криптографическим подходом на основе эллиптических кривых, зависит от того, насколько трудной для решения оказывается задача определения <math>k</math> по данным <math>kP</math> и <math>P</math>. Эту задачу обычно называют задачей дискретного логарифмирования на эллиптической кривой. Наиболее быстрым из известных на сегодня методов логарифмирования на эллиптической кривой является так называемый <math>p</math>-метод Полларда. В таблице (см. ниже) сравнивается эффективность этого метода и метод разложения на простые множители с помощью решета в поле чисел общего вида. Из нее видно, что по сравнению с RSA в случае применения методов криптографии на эллиптических кривых примерно тот же уровень защиты достигается со значительно меньшими значениями длины ключей. 

К тому же, при равных длинах ключей вычислительные усилия, требуемые при использовании RSA и криптографии на основе эллиптических кривых, не сильно различаются. Таким образом, в сравнении с RSA при равных уровнях защиты явное вычислительное преимущество принадлежит криптографии на основе эллиптических кривых с более короткой длиной ключа<ref>Жданов О.Н., Золотарев В.В. Методы и средства криптографической защиты информации. 186 с.</ref>.

'''Таблица: Вычислительные усилия, необходимые для криптоанализа при использовании эллиптических кривых и RSA'''

* Логарифмирование на эллиптической кривой с помощью <math>p</math>-метода Полларда.

{| class="wikitable"
|-
! Размер ключа !! MIPS-годы
|-
| 150 || 3,8 * 10^10
|-
| 205 || 7,1 * 10^18
|-
| 234 || 1,6 * 10^28
|}

* Разложение на множители в целых числах с помощью метода решета в поле чисел общего вида.

{| class="wikitable"
|-
! Размер ключа !! MIPS-годы
|-
| 512 || 3 * 10^4
|-
| 768 || 3 * 10^7<!-- Это точно не ошибка? -->
|-
| 1024 || 3 * 10^11
|-
| 1280 || 3 * 10^14
|-
| 1536 || 3 * 10^16
|-
| 2048 || 3 * 10^20
|}

== Построение электронной цифровой подписи с использованием эллиптических кривых ==

Алгоритм [[ECDSA]] (Elliptic Curve Digital Signature Algorithm) принят в качестве стандартов ANSI X9F1 и [[IEEE P1363]].

=== Создание ключей ===

# Выбирается эллиптическая кривая <math>E_p(a,b)</math>. Число точек на ней должно делиться на большое простое число n.
# Выбирается базовая точка <math>G \in E_p(a,b)</math> порядка <math>n, n \cdot G = \infty </math>.
# Выбирается случайное число <math>d \in (1,n)</math>.
# Вычисляется <math>Q=d \cdot G</math>.
# Закрытым ключом является d, открытым ключом — кортеж <a, b, G, n, Q>.

=== Создание подписи ===

# Выбирается случайное число <math>k \in (1,n)</math>.
# Вычисляется <math>k \cdot G = (x_1, y_1)</math> и <math>r=x_1 (\operatorname{mod} n)</math>.
# Проверяется условие <math>r \neq 0</math>, так как иначе подпись не будет зависеть от закрытого ключа. Если r = 0, то выбирается другое случайное число k.
# Вычисляется <math>k^{-1} (\operatorname{mod} n)</math>.
# Вычисляется <math>s=k^{-1} \cdot (H(M)+dr)(\operatorname{mod} n)</math>.
# Проверяется условие <math>s \neq 0</math>, так как в этом случае необходимого для проверки подписи числа <math>s^{-1} (\operatorname{mod} n)</math> не существует. Если s = 0, то выбирается другое случайное число k .

Подписью для сообщения М является пара чисел (r, s).

=== Проверка подписи ===

# Проверим, что числа r и s принадлежат диапазону чисел (1, n). В противном случае результат проверки отрицательный, и подпись отвергается.
# Вычислить <math>w=s^{-1} (\operatorname{mod} n)</math> и H(M).
# Вычислить <math>u_1=H(M)w(\operatorname{mod} n)</math> и  <math>u_2=rw(\operatorname{mod} n)</math>.
# Вычислить <math>u_1G+u_2Q=(x_0,y_0), v=x_0(\operatorname{mod} n)</math>.
# Подпись верна в том и только том случае, когда v = r<ref>Ишмухаметов Ш.Т. Методы факторизации натуральных чисел.99 с.</ref>.

== Приложения ==

Большинство криптосистем современной криптографии естественным образом можно «переложить» на эллиптические кривые. Основная идея заключается в том, что известный алгоритм, используемый для конкретных конечных групп, переписывается для использования групп рациональных точек эллиптических кривых:
* алгоритм [[ECDSA]], основывающийся на [[Электронная цифровая подпись|ЭЦП]],
* алгоритм [[ECDH]], основывающийся на [[Алгоритм Диффи — Хеллмана|алгоритме Диффи — Хеллмана]],
* алгоритм [[ECMQV]], основывающийся на [[MQV]], протоколе распределения ключей Менезеса-Кью-Венстоуна,
* [[ГОСТ Р 34.10-2012]],
* [[факторизация Ленстры с помощью эллиптических кривых]],
* [[dual EC DRBG]].

Необходимо отметить, что безопасность таких систем цифровой подписи опирается не только на криптостойкость алгоритмов шифрования, но и на криптостойкость используемых [[криптографическая хеш-функция|криптографических хеш-функций]] и [[ГПСЧ#ГПСЧ в криптографии|генераторов случайных чисел]].

По обзору 2013 года, чаще всего используются кривые nistp256, nistp384, nistp521, secp256k1, secp384r1, secp521r1<ref>Bos et al, [http://cryptome.org/2013/11/ecc-practice.pdf Elliptic Curve Cryptography in Practice] {{Wayback|url=http://cryptome.org/2013/11/ecc-practice.pdf |date=20160207133548 }} // MSR-TR-2013-119, November 2013</ref>.

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга |автор=Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. |заглавие=Алгоритмические основы эллиптической криптографии |место=Москва |издательство=МЭИ |год=2000 |страниц=100 |ссылка=http://new.math.msu.su/department/dm/dmmc/PUBL1/elcr_ps.zip}}
* {{книга |автор=Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. |заглавие=Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. |место=Москва |издательство=КомКнига |год=2006 |страниц=328}}
* {{книга |автор=Жданов О.Н., Золотарев В.В. |заглавие=Методы и средства криптографической защиты информации |место=Красноярск |издательство=«Город» |год=2007 |страниц=217}}
* {{книга |автор=Ишмухаметов Ш.Т. |заглавие=Методы факторизации натуральных чисел |место=Казань |издательство=КФУ |год=2011 |страниц=190}}
* {{книга |автор=Koblitz N.A. |заглавие=Course in number theory and cryptography. |ответственный=|издание=|место=USA |издательство=Springer-Verlag |год=1994 |страницы=|страниц=235|isbn=|isbn2=}}
{{криптографические алгоритмы с парой открытый/закрытый ключ}}

[[Категория:Криптография]]
[[Категория:Криптография с открытым ключом]]
[[Категория:Стандарты криптографии]]
[[Категория:Электронная подпись]]
[[Категория:Эллиптические кривые]]