Что такое эллиптическая кривая

Этот факт можно истолковать и доказать с помощью некоторых общих тем; см. Локальная дзета-функция, Этальная когомология. Число точек на данной кривой может быть вычислено с помощью алгоритма Шуфа.

Дальнейшие рассуждения по теме см. в статье Арифметика абелевых многообразий.

Приложения

Эллиптические кривые над конечными полями используются в некоторых криптографических приложениях и факторизации. Обычно, основная идея, заложенная в этих приложениях, заключается в том, что известный алгоритм, используемый для конкретных конечных групп переписывается для использования групп рациональных точек эллиптических кривых. Подробнее см.:

• Эллиптическая криптография
• DSA на эллиптических кривых
• ГОСТ Р 34.10-2001
• Факторизация Ленстры с помощью эллиптических кривых
• Доказательство простоты с помощью эллиптических кривых
• Dual EC DRBG
• ДСТУ 4145-2002
• IBE

Список литературы

• Н. Коблиц Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. — Москва: Научное издательство «ТВП», 2001. — С. 254. — ISBN 5-85484-014-6

• Н. Коблиц Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. — Новокузнецк: ИО НФМИ, 2000. — С. 312. — ISBN 5-8032-3325-0

• С. Ленг Эллиптические функции = Elliptic functions. — Новокузнецк: ИО НФМИ, 2000. — С. 312. — ISBN 5-8032-3326-9

• Joseph H. Silverman The Arithmetic of Elliptic Curves. — New York: Springer, 1986. — С. 402. — ISBN 0-387-96203-4

См. также

Эллиптическая криптография: теория

Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.

Эллиптические кривые

Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе:

Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером:

Графики(6 штук)

Эллиптические кривые представленые на первых 4-х рисунках называются гладкими. В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым.
Для гладких эллиптических кривых выполняется следующее неравенство:

Тогда как для сингулярных кривых это условие, сюрприз, не выполняется.
Если вы собираетесь самостоятельно разрабатывать криптографических продукт, поддерживающий «эллиптику» очень важно запомнить следующий факт:
Нельзя использовать в схемах ЭЦП сингулярные кривые. Подробно мы еще затронем эту тему, сейчас же просто скажем, что используя сингулярные кривые вы рискуете значительно снизить стойкость схемы ЭЦП.
Арифметические операции в эллиптической криптографии производятся над точками кривой. Основной операцией является «сложение».
Сложение двух точек легко представить графически:

Как видно из рисунка, для сложения точек P и Q, необходимо провести между ними прямую линию, которая обязательно пересечет кривую в какой-либо третьей точке R. Отразим точку R относительно горизонтальной оси координат и получим искомую точку P+Q.

Алгебраическое представление «сложения»

Запишем сложение двух точек в виде формулы:

Пусть координатами точки P будут (x_p, y_p), а координатами точки Q соответственно (x_q, y_q). Вычислим

и тогда координаты точки P+Q будут равны:

Эллиптические кривые в криптографии

Осталось уточнить всего одну деталь. Все рассмотренные выше кривые относятся к эллиптическим кривым над вещественными числами. И это приводит нас к проблеме округления. Т.е., используя кривые над вещественными числами, мы не сможем получить биекцию между исходным текстом и зашифрованными данными. Чтобы не заморачиваться с округлением в криптографии используются только кривые над конечными полями. Это означает, что под эллиптической кривой понимается набор точек, чьи координаты принадлежат конечному полю.

В криптографии рассматривается два вида эллиптических кривых: над конечным полем — кольцо вычетов по модулю простого числа. И над полем — бинарное конечное поле.
У эллиптических кривых над полем есть одно важное преимущество, элементы поля могут быть легко представленны в виде n-битных кодовых слов, это позволяет увеличить скорость аппаратной реализации эллиптических алгоритмов.

Все математические операции на эллиптических кривых над конечным полем производятся по законам конечного поля над которым построена эллиптическая кривая. Т.е. для вычисления, например, суммы двух точек кривой E над кольцом вычетов все операции производятся по модулю числа p.

Однако здесь есть свои подводные камни. Если мы сложим два одинаковых элемента из бинарного конечного поля, то получим в результате 0, т.к. сложение происходит по модулю 2. Это означает что характеристика такого поля равна 2. Но эллиптическая кривая вида

описанная над полем характеристики 2 или 3 становится сингулярной, а как уже замечалось выше это неудачная идея использовать сингулярные кривые в криптографии.

Поэтому над бинарным конечным полем используются кривые вида:

Еще одним важным понятие эллиптической криптографии является порядок эллиптической кривой, который показывает количество точек кривой над конечным полем.
Теорема Хассе утверждает, что если N — количество точек кривой, определенной над полем Zq с q элементами тогда справедливо равенство:

Т.к. бинарное конечное поле состоит из 2 n элементов мы можем сказать, что порядок кривой равен , где .

С числом t связано следующее определение:
эллиптическая кривая над бинарным конечным полем называется суперсингулярной, если t делится на характеристику поле(в случае бинарного поля характеристика равна 2) без остатка.
Разумеется все это я к тому, что нельзя использовать в схемах ЭЦП суперсингулярные кривые. Строгая рекомендация не использовать сингулярные и суперсингулярные кривые для цифровой подписи имеет одну очень вескую причину, но об этом позже.

Криптография на эллиптических кривых

Точки эллиптической кривой над конечным полем представляют собой группу. И как мы отмечали выше для этой группы определена операция сложения.
Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми.

Теперь представим, что у нас имеется сообщение M представленное в виде целого числа. Мы можем зашифровать его используя выражение
C=M*G.
Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.
Данная задача называется дискретным логарифмом на эллиптической кривой и не имеет быстрого решения. Более того, считается, что задача дискретного логарифма на эллиптической кривой является более трудной для решения, чем задача дискретного логарифмирования в конечных полях.

Наиболее быстрые методы, разработанные для конечных полей оказываются бесполезны в случае эллиптических кривых.
Так для решения дискретного логарифма существуют достаточно быстрые алгоритмы имеющие сложность , где c и d — некоторые константы, а p — размер поля. Такие алгоритмы называются субэкспоненциальными и позволяют сравнительно легко вскрывать дискретный логарифм в конечном поле, если размер поля не выбран очень большим, порядка 2 1024 .
В тоже время наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность , где q — количество точек эллиптической кривой.
Таким образом, для обеспечения уровня стойкости в 2 80 операций необходимо чтобы q=2 160 . Напомню, для того, чтобы получить аналогичный уровень сложности при вычислении дискретного логарифма в конечном поле необходимо поле порядка q=2 1024 .

Следует, однако, заметить, что поскольку мощность вычислительной техники постоянно повышается, значение q будет постоянно увеличиваться. Но так как графики функций и резко отличаются друг от друга, в группе точек эллиптической кривой q будет расти намного медленнее, чем в произвольном конечном поле.

Варианты атак

1. Алгоритма Полига-Хеллмана. Алгоритм решения дискретного логарифма. Предположим, что n — количество точек эллиптической кривой. Пусть число n раскладывается на простые числа p₁, p₂. p_n. Суть метода сводится к тому, чтобы найти дискретные логарифмы по модулю числе p_i, а затем получить общее решение с помощью китайской теоремы об остатках. Атака позволяет свести проблему дискретного логарифма в большом поле n к той же задаче, но с гораздо меньшим полем p. Для того, чтобы противостоять атаке необходимо просто выбирать кривые, количество точек которых делится на очень большое простое число q≈n.
2. Алгоритм Шенкса, более известный как шаги младенца/шаги гиганта. Типичный пример time memory trade off. Для группы размером n вычисляется таблиц размером n 1/2 , затем по этой таблице происходит поиск нужного элемента. Сложность алгоритма .
3. Уязвимость сингулярных и суперсингулярных кривых. Я уже упоминал, что для решения задачи дискретного логарифма не существует субэкспоненциальных методов решения. На самом деле есть одна оговорка, такие методы есть, но только для определенного рода кривых: сингулярных и суперсингулярных. Особые свойства таких кривых позволяют свести задачу дискретного логарифма на эллиптической кривой, к задаче дискретного логарифма в конечном поле. Соответственно для такого класса кривых стандартные ключи размером в 160-320 бит, будут фатально уязвимы, что позволит злоумышленникам вскрыть секретный ключ, за относительно небольшое время.
4. Уязвимость аномальных кривых Напомню, что количество точек эллиптической кривой вычисляется по формуле
   n=q+1-t, где q — размер исходного поля. И что кривая называется суперсингулярной если t делится на 2.
   Поэтому, на первый взгляд может показаться хорошей идеей использовать кривые в которых количество точек равно q, т.е. t=1.
   Однако такие кривые называются аномальными и решение дискретного логарифма на аномальных эллиптических кривых является еще более простой задачей, чем для суперсингулярных и сингулярных кривых.

Подытожим

1. Гораздо меньшая длина ключа по сравнению к «классической» асимметричной криптографией.
2. Скорость работы эллиптических алгоритмов гораздо выше, чем у классических. Это объясняется как размерами поля, так и применением более близкой для компьютеров структуры бинарного конечного поля.
3. Из-за маленькой длины ключа и высокой скорости работы, алгоритмы асимметричной криптографии на эллиптических кривых могут использоваться в смарт-картах и других устройствах с ограниченными вычислительными ресурсами.

1. Все плюсы эллиптической криптографии вытекают из одного конкретного факта:
   для задачи дискретного логарифмирования на эллиптических кривых не существует субэкспоненциальных алгоритмов решения. Это позволяет уменьшить длину ключа и увеличить производительность. Однако если такие алгоритмы появятся, то это будет означать крах эллиптической криптографии.
2. Эллиптическая криптография — это очень сложно. Не то чтобы я считал обычную асимметричную криптографию совсем уж простой штукой. Но «эллиптика» — это огромное количество тонкостей, которые необходимо учесть. Начиная с выбора эллиптической кривой и заканчивая генерацией ключей. При массовом переходе на эллиптику скорее всего обязательно будет большое количество ошибок и уязвимостей, которые уже отработаны для более привычных методов.

На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами.

Используемая литература

1. Don Johnson, Alfred Menezes, Scott Vanstone — The Elliptic Curve Digital Signature Algorithm.
2. А. Болотов, С. Гашков, А. Фролов, А. Часовских — Элементарное введение в эллиптическую криптографию.
3. Lawrence Washington — Elliptic curves, Number theory and Cryptography.

Эллиптическая кривая

y 2 = x 3 + a x + b . y^2=x^3+ax+b. y 2 = x 3 + a x + b . Здесь подразумевается, что эллиптическая кривая рассматривается над полем действительных чисел . Рассматриваются эллиптические кривые и над другими полями.

Редакция математических наук

Опубликовано 8 ноября 2022 г. в 10:56 (GMT+3). Последнее обновление 8 ноября 2022 г. в 10:56 (GMT+3). Обратная связь

Плоская кривая
Информация

Области знаний: Аналитическая геометрия

• Научно-образовательный портал «Большая российская энциклопедия»
  Свидетельство о регистрации СМИ ЭЛ № ФС77-84198,
  выдано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций (Роскомнадзор) 15 ноября 2022 года.
  ISSN: 2949-2076
• Учредитель: Автономная некоммерческая организация «Национальный научно-образовательный центр «Большая российская энциклопедия»
  Главный редактор: Кравец С. Л.
  Телефон редакции: +7 (495) 917 90 00
  Эл. почта редакции: secretar@greatbook.ru

• © АНО БРЭ, 2022 — 2023. Все права защищены.
• Условия использования информации. Вся информация, размещенная на данном портале, предназначена только для использования в личных целях и не подлежит дальнейшему воспроизведению.
  Медиаконтент (иллюстрации, фотографии, видео, аудиоматериалы, карты, скан образы) может быть использован только с разрешения правообладателей.
• Условия использования информации. Вся информация, размещенная на данном портале, предназначена только для использования в личных целях и не подлежит дальнейшему воспроизведению.
  Медиаконтент (иллюстрации, фотографии, видео, аудиоматериалы, карты, скан образы) может быть использован только с разрешения правообладателей.

Эллиптическая кривая

Эллипти́ческая крива́я над полем [math]\displaystyle< K >[/math] — неособая кубическая кривая на проективной плоскости над [math]\displaystyle < \hat>[/math] (алгебраическим замыканием поля [math]\displaystyle< K >[/math] ), задаваемая уравнением 3-й степени с коэффициентами из поля [math]\displaystyle< K >[/math] и «точкой на бесконечности». В подходящих аффинных координатах её уравнение приводится к виду [1] [2]

в котором используется исторически сложившееся обозначение коэффициентов [math]\displaystyle< a_1, a_2, a_3, a_4, a_6 >[/math] .

История

Древнейшим дошедшим до нашего времени источником, в котором рассматриваются кубические кривые, является «Арифметика» древнегреческого математика Диофанта. В этой работе ставится задача найти рациональные и нетривиальные решения уравнения [math]\displaystyle< y(6 - y) = x^3 - x >[/math] . Диофант решает эту задачу при помощи подстановки [math]\displaystyle< x = 3y - 1 >[/math] .

В 1670-х годах Ньютон, используя приёмы аналитической геометрии, делает попытку классифицировать кубические кривые. В ходе исследований Ньютон заметил, что решение Диофанта состоит, по существу, в пересечении кривой, заданной уравнением [math]\displaystyle< y(6 - y) = x^3 - x >[/math] , с касательной [math]\displaystyle< x = 3y - 1 >[/math] . Открытие Ньютона в конечном итоге привело к формулам сложения точек на эллиптической кривой. В XIX веке эллиптические кривые находят применение [ уточнить ] в теории эллиптических функций, которые, в свою очередь, тесно связаны с эллиптическими интегралами. Таким образом, исторически термин «эллиптическая кривая» происходит от термина «эллиптический интеграл» [3] .

Каноническая форма

Если характеристика поля [math]\displaystyle< K >[/math] не равна 2 или 3 (что включает поля нулевой характеристики, например поля рациональных чисел [math]\displaystyle< \Q >[/math] , вещественных чисел [math]\displaystyle< \R >[/math] и комплексных чисел [math]\displaystyle< \C >[/math] ), общее уравнение эллиптической кривой с помощью замены координат приводится к канонической форме

называемой нормальной формой Вейерштрасса.

В случае если характеристика поля [math]\displaystyle< K >[/math] равна 3, общее уравнение кривой можно привести к одной из следующих двух форм:

• [math]\displaystyle< y^2 = x^3 + ax^2 + b\quad >[/math] ( несуперсингулярная кривая[en] );
• [math]\displaystyle< y^2 = x^3 + ax + b\quad >[/math] (суперсингулярная кривая).

Наконец, если характеристика поля [math]\displaystyle< K >[/math] равна 2, общее уравнение кривой можно привести к одной из следующих двух форм [4] [5] :

• [math]\displaystyle< y^2 + xy = x^3 + ax^2 + b\quad >[/math] (несуперсингулярная кривая);
• [math]\displaystyle< y^2 + cy = x^3 + ax + b\quad >[/math] (суперсингулярная кривая).

Во всех указанных случаях коэффициенты [math]\displaystyle< a >[/math] и [math]\displaystyle< b >[/math] (либо [math]\displaystyle< a >[/math] , [math]\displaystyle< b >[/math] и [math]\displaystyle< c >[/math] ) являются элементами поля [math]\displaystyle< K >[/math] .

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

Графики кривых y 2 = x 3 − x и y 2 = x 3 − x + 1

Формальное определение эллиптической кривой требует некоторых знаний в алгебраической геометрии, но некоторые свойства эллиптических кривых над вещественными числами можно описать, используя только знания алгебры и геометрии старших классов школы.

Поскольку характеристика поля вещественных чисел — 0, а не 2 или 3, то эллиптическая кривая — плоская кривая, определяемая уравнением вида:

где [math]\displaystyle< a >[/math] и [math]\displaystyle< b >[/math] — вещественные числа. Этот вид уравнений называется уравнениями Вейерштрасса.

Определение эллиптической кривой также требует, чтобы кривая не имела особых точек. Геометрически это значит, что график не должен иметь каспов и самопересечений. Алгебраически, достаточно проверить, что дискриминант

Если кривая не имеет особых точек, то её график имеет две связные компоненты, если дискриминант положителен, и одну — если отрицателен. Например, для графиков выше в первом случае дискриминант равен 64, а во втором он равен −368.

Групповой закон

Добавлением «точки в бесконечности» получается проективный вариант этой кривой [7] . Если [math]\displaystyle< P >[/math] и [math]\displaystyle< Q >[/math] — две точки на кривой, то возможно единственным образом описать третью точку — точку пересечения данной кривой с прямой, проведённой через [math]\displaystyle< P >[/math] и [math]\displaystyle< Q >[/math] . Если прямая является касательной к кривой в точке, то такая точка считается дважды. Если прямая параллельна оси ординат, третьей точкой будет точка в бесконечности.

Таким образом, можно ввести групповую операцию «+» на кривой со следующими свойствами: точка в бесконечности (обозначаемая символом [math]\displaystyle< O >[/math] ) является нейтральным элементом группы, и если прямая пересекает данную кривую в точках [math]\displaystyle< P >[/math] , [math]\displaystyle< Q >[/math] и [math]\displaystyle< R' >[/math] , то [math]\displaystyle< P + Q + R' = O >[/math] в группе. Суммой точек [math]\displaystyle< P >[/math] и [math]\displaystyle< Q >[/math] называется точка [math]\displaystyle< R = P + Q >[/math] , которая симметрична точке [math]\displaystyle< R' >[/math] относительно оси [math]\displaystyle< Ox >[/math] . Можно показать, что относительно введённой таким образом операции лежащие на кривой точки и точка [math]\displaystyle< O >[/math] образуют абелеву группу; в частности, свойство ассоциативности операции «+» можно доказать, используя теорему о 9 точках на кубической кривой (кубике) [8] .

Данная группа может быть описана и алгебраически. Пусть дана кривая [math]\displaystyle< y^2 = x^3 + ax + b >[/math] над полем [math]\displaystyle< K >[/math] (характеристика которого не равна ни 2, ни 3), и точки [math]\displaystyle< P = (x_P, y_P) >[/math] и [math]\displaystyle< Q = (x_Q, y_Q) >[/math] на кривой; допустим, что [math]\displaystyle< x_P \ne x_Q >[/math] . Пусть [math]\displaystyle< s = \tfrac >[/math] ; так как [math]\displaystyle< K >[/math] — поле, то [math]\displaystyle< s >[/math] строго определено. Тогда мы можем определить [math]\displaystyle< R = P + Q = (x_R, y_R) >[/math] следующим образом:

Если [math]\displaystyle< x_P = x_Q >[/math] , то есть два варианта. Если [math]\displaystyle< y_P = -y_Q >[/math] , то сумма определена как 0; значит, обратную точку к любой точке на кривой можно найти, отразив её относительно оси [math]\displaystyle< Ox >[/math] . Если [math]\displaystyle< y_P = y_Q \ne 0 >[/math] , то [math]\displaystyle< R = P + P = 2P = (x_R, y_R) >[/math] определяется так:

Если [math]\displaystyle< y_P = y_Q = 0 >[/math] , то [math]\displaystyle< P + P = O >[/math] .

Обратный элемент к точке [math]\displaystyle< P >[/math] , обозначаемый [math]\displaystyle< -P >[/math] и такой, что [math]\displaystyle< P + (-P) = 0 >[/math] , в рассмотренной выше группе определяется так [9] :

• Если координата [math]\displaystyle< y_P >[/math] точки [math]\displaystyle< P = (x_P, y_P) >[/math] не равна [math]\displaystyle< 0 >[/math] , то [math]\displaystyle< -P = (x_P, -y_P) >[/math] .
• Если [math]\displaystyle< y_P = 0 >[/math] , то [math]\displaystyle< -P = P = (x_P, y_P) >[/math] .
• Если [math]\displaystyle< P = O >[/math] — точка на бесконечности, то и [math]\displaystyle< -P = O >[/math] .

Точка [math]\displaystyle< Q = nP >[/math] , где [math]\displaystyle< n >[/math] целое, определяется (при [math]\displaystyle< n \gt 0 >[/math] ) как [math]\displaystyle< Q = \underbrace_ >[/math] . Если [math]\displaystyle< n \lt 0 >[/math] , то [math]\displaystyle< Q >[/math] есть обратный элемент к [math]\displaystyle< |n| P >[/math] . Если [math]\displaystyle< n = 0 >[/math] , то [math]\displaystyle< Q = 0 \cdot P = O >[/math] . Для примера покажем, как найти точку [math]\displaystyle< Q = 4P >[/math] : она представляется как [math]\displaystyle< 4P = 2P + 2P >[/math] , а точка [math]\displaystyle< 2P >[/math] находится по формуле [math]\displaystyle< 2P = P + P >[/math] [10] .

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

Эллиптическая кривая над комплексными числами строится как фактор комплексной плоскости по решётке Λ, порождённой фундаментальными периодами ω₁ и ω₂. Показано также 4-кручение, соответствующее решётке 1/4 Λ, содержащей Λ

Эллиптические кривые, определённые над комплексными числами, соответствуют вложениям тора в комплексную проективную плоскость. Точки тора также образуют группу, и соответствие между точками эллиптической кривой и точками тора является изоморфизмом групп.

Определение эллиптических кривых как вложения тора в комплексную проективную плоскость естественным образом следует из одного любопытного свойства эллиптических функций Вейерштрасса, согласно которому они и их первые производные связаны формулой

где [math]\displaystyle< g_2 >[/math] и [math]\displaystyle< g_3 >[/math] — константы; [math]\displaystyle< \wp(z) >[/math] — эллиптическая функция Вейерштрасса, а [math]\displaystyle< \wp'(z) >[/math] — её производная. Функции Вейерштрасса дважды периодичны, то есть периодичны относительно решётки [en] [math]\displaystyle< \Lambda >[/math] , и, следовательно, определены на торе [math]\displaystyle < T = \mathbb/ \Lambda >[/math] . Этот тор может быть вложен в комплексную проективную плоскость отображением

Это отображение — изоморфизм римановых поверхностей, то есть топологически данную эллиптическую кривую можно рассматривать как тор. Если решётка [math]\displaystyle< \Lambda >[/math] связана с решёткой [math]\displaystyle< c\Lambda >[/math] умножением на ненулевое комплексное число [math]\displaystyle< c >[/math] , то соответствующие кривые изоморфны. Класс изоморфизма эллиптической кривой однозначно определяется её j-инвариантом.

Классы изоморфизма можно рассмотреть более простым образом. Константы [math]\displaystyle< g_2 >[/math] и [math]\displaystyle< g_3 >[/math] , называемые модулярными инвариантами, однозначно определяются решёткой, то есть структурой тора. С другой стороны, уравнение эллиптической кривой можно записать как

Можно показать, что

[math]\displaystyle< g_3 = \frac (\lambda + 1) (2 \lambda^2 - 5 \lambda + 2), >[/math]

Представление в виде тора также облегчает понимание точек кручения эллиптической кривой: если решётка Λ порождена фундаментальными периодами [math]\displaystyle< \omega_1 >[/math] и [math]\displaystyle< \omega_2 >[/math] , то точки [math]\displaystyle< n >[/math] -кручения — это классы эквивалентности точек

где [math]\displaystyle< a >[/math] и [math]\displaystyle< b >[/math] — целые числа от [math]\displaystyle< 0 >[/math] до [math]\displaystyle< n - 1 >[/math] .

Каждая эллиптическая кривая над комплексными числами имеет девять точек перегиба. На каждой прямой, проходящей через две точки перегиба, лежит третья точка перегиба; 9 точек и 12 прямых, построенных таким образом, образуют конфигурацию Гессе.

Эллиптические кривые над полем рациональных чисел

Если коэффициенты уравнения эллиптической кривой [math]\displaystyle< E >[/math] рациональны, то можно рассматривать множество рациональных точек на такой кривой (включая [math]\displaystyle< O >[/math] ). Это множество образует подгруппу группы действительных точек (включая [math]\displaystyle< O >[/math] ) на кривой [math]\displaystyle< E >[/math] с таким же групповым законом сложения точек на кривой. Это можно показать следующим образом: рассмотрим алгебраическую формулу получения координаты суммы двух точек [math]\displaystyle< P >[/math] и [math]\displaystyle< Q >[/math] , лежащих на кривой [math]\displaystyle< E >[/math] . Если эти точки и коэффициенты уравнения кривой рациональны, то координаты точки [math]\displaystyle< R = P + Q >[/math] тоже будут рациональны, так как [math]\displaystyle< x_R >[/math] и [math]\displaystyle< y_Q >[/math] являются рациональными функциями от коэффициентов кривой [math]\displaystyle< E >[/math] координат точек [math]\displaystyle< P >[/math] и [math]\displaystyle< Q >[/math] [12] .

Порядком точки [math]\displaystyle< P >[/math] на кривой [math]\displaystyle< E >[/math] называется наименьшее натуральное [math]\displaystyle< k >[/math] такое, что [math]\displaystyle< kP = O >[/math] .

Для эллиптических кривых над полем рациональных чисел справедлива теорема Морделла [en] : на эллиптической кривой [math]\displaystyle< E >[/math] существует такое конечное множество рациональных точек бесконечного порядка [math]\displaystyle< P_1, P_2, \dots, P_n >[/math] , что любая точка на эллиптической кривой представляется в виде

где [math]\displaystyle< a_1, \dots, a_n >[/math] — целые числа, однозначно определённые для точки [math]\displaystyle< P >[/math] , а [math]\displaystyle< Q >[/math] — точка кручения, являющаяся точкой конечного порядка [13] . Другими словами, теорема гласит, что если поле [math]\displaystyle< K >[/math] — поле рациональных чисел, то группа [math]\displaystyle< K >[/math] -рациональных точек — конечнопорождённая. Это означает, что группа может быть представлена как прямая сумма свободной абелевой группы и конечной подгруппы кручения [14] .

Рангом эллиптической кривой [math]\displaystyle< E >[/math] называется минимальное число рациональных точек бесконечного порядка из теоремы Морделла. Нет общего алгоритма для вычисления ранга свободной подгруппы и, соответственно, ранга эллиптической кривой. Формула для вычисления ранга даётся в гипотезе Бёрча — Свиннертон-Дайера.

На 2021 год эллиптическая кривая с максимальным точно известным рангом описывается следующим уравнением:

Её ранг равен 20, она была найдена Ноамом Элкисом и Зевом Клагсберном в 2020 году [15] . Про следующую кривую, найденную Элкисом в 2006 году и описываемую уравнением

известно, что её ранг по крайней мере 28, однако точный ранг этой кривой неизвестен [16] . В 2016 году было опубликовано доказательство того, что ранг этой кривой равен в точности 28, если верна обобщённая гипотеза Римана [17] .

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

Эллиптическую кривую [math]\displaystyle< E >[/math] можно определить над конечным полем [math]\displaystyle< \mathbb_q >[/math] , где [math]\displaystyle< q = p^r >[/math] , а [math]\displaystyle< p >[/math] — простое.

Точное число точек эллиптической кривой [math]\displaystyle< E >[/math] над полем [math]\displaystyle< \mathbb_q >[/math] вычислить достаточно трудно, однако теорема Хассе об эллиптических кривых даёт следующую оценку [18] :

[math]\displaystyle< \big| \#E(\mathbb_q) - q - 1 \big| \leqslant 2 \sqrt. >[/math]

Этот факт можно истолковать и доказать с помощью общей теории; см. Локальная дзета-функция, Этальные когомологии [en] .

Число точек на конкретной кривой может быть вычислено с помощью алгоритма Шуфа.

Приложения

Эллиптические кривые над конечными полями используются в некоторых криптографических приложениях для факторизации и тестирования простоты чисел. Обычно основная идея, заложенная в этих приложениях, заключается в том, что известный алгоритм, используемый для конкретных конечных групп, переписывается для использования групп рациональных точек эллиптических кривых.

В теории чисел эллиптические кривые были, в частности, использованы Эндрю Джоном Уайлсом (совместно с Ричардом Тейлором) в доказательстве великой теоремы Ферма.

В криптографии они образуют самостоятельный раздел эллиптической криптографии, посвящённый изучению криптосистем на базе эллиптических кривых. В частности, на эллиптических кривых основаны российские стандарты ГОСТ Р 34.10-2001 и сменивший его ГОСТ Р 34.10-2012, описывающие алгоритмы формирования и проверки электронной цифровой подписи.

Примечания

1. ↑Silverman, 2009, p. 59.
2. ↑Коблиц, 2001, с. 188.
3. ↑Adrian Rice, Ezra Brown.Why Ellipses Are Not Elliptic Curves(англ.) // Mathematics Magazine. — 2012. — Vol. 85, no. 3 . — P. 163—176.
4. ↑Silverman, 2009, p. 42—43,409—410.
5. ↑П. П. Урбанович.Защита информации методами криптографии, стеганографии и обфускации. — Минск: БГТУ, 2016. — С. 81. — 220 с. — ISBN 978-985-530-562-1.
6. ↑Silverman, 2009, p. 42—43.
7. ↑Коблиц, 2001, с. 192.
8. ↑Острик, 2001, с. 21—24.
9. ↑Коблиц, 2001, с. 188—200.
10. ↑Острик, 2001, с. 24.
11. ↑Коблиц, 2000, с. 33—37.
12. ↑Silverman, 2009, p. 20.
13. ↑Острик, 2001, с. 26.
14. ↑Коблиц, 2001, с. 195.
15. ↑Dujella, Andrej.History of elliptic curves rank records(англ.). Andrej Dujella home page. Дата обращения: 1 декабря 2021.
16. ↑ Dujella, Andrej. Construction of high rank elliptic curves and related Diophantine problems. 7th Symposium on Algebra and Computation (AC 2007). 2007.
17. ↑ Klagsbrun, Zev, Travis Sherman, and James Weigandt. The Elkies curve has rank 28 subject only to GRH. arXiv preprint arXiv:1606.07178 (2016).
18. ↑Silverman, 2009, p. 137—138.

Литература

• Клеменс, Г. Мозаика теории комплексных кривых. — М.: Мир, 1984.
• Коблиц Н. Курс теории чисел и криптографии = A Course in Number Theory and Cryptography. — М. : Научное изд-во «ТВП», 2001. — С. 188—200. — 254 с. — ISBN 5-85484-014-6.
• Острик В. В., Цфасман М. А.Алгебраическая геометрия и теория чисел: рациональные и эллиптические кривые. — М. : МЦНМО, 2001. — С. 48. — (Библиотека «Математическое просвещение»). — ISBN 5-900916-71-5.
• Коблиц Н. Введение в эллиптические кривые и модулярные формы = Introduction to Elliptic Curves and Modular Forms. — Новокузнецк: ИО НФМИ, 2000. — С. 33—37. — 312 с. — ISBN 5-8032-3325-0.
• Ленг С. Эллиптические функции = Elliptic functions. — Новокузнецк: ИО НФМИ, 2000. — С. 312. — ISBN 5-8032-3326-9.
• Joseph H. Silverman.The Arithmetic of Elliptic Curves. — N. Y. : Springer, 2009. — P. 42—43,59,137—138. — 408 p. — ISBN 978-0-387-09493-9.
• Урбанович, П. П.Защита информации методами криптографии, стеганографии и обфускации. — Минск: БГТУ, 2016. — С. 81. — 220 с. — ISBN 978-985-530-562-1.

Ссылки

• 14H52 Elliptic Curves(англ.). The Mathematical Atlas. Дата обращения: 2 января 2015.Архивировано 23 февраля 2003 года.
• Weisstein, Eric W.Elliptic Curves(англ.) на сайте Wolfram MathWorld.
• Николенко С.Эллиптическая криптография // Компьютерра. — 1 сентября 2006.
• Соловьёв Ю. П.Рациональные точки на эллиптических кривых // Соросовский образовательный журнал. — 1997. — № 10 . — С. 138—143 .