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

Эллиптическая кривая — это невырожденная алгебраическая кривая рода 1, задаваемая уравнением третьей степени (кубическим уравнением) над некоторым полем. В наиболее распространённой форме, пригодной для криптографии и теории чисел, эллиптическая кривая над полем действительных чисел, рациональных чисел или конечным полем описывается уравнением Вейерштрасса: \(y^2 = x^3 + ax + b\), где коэффициенты \(a\) и \(b\) удовлетворяют условию несингулярности: дискриминант \(\Delta = -16(4a^3 + 27b^2) \neq 0\). Это условие гарантирует, что кривая не имеет самопересечений, остроконечных точек (каспов) или изолированных точек. Название «эллиптическая» связано не с формой эллипса, а с историей вычисления длины дуги эллипса, что привело к интегралам, обратные функции которых задают эллиптические кривые.

История

Истоки в анализе

Понятие эллиптических кривых возникло в XVIII—XIX веках из задач математического анализа. Леонард Эйлер и Адриен Мари Лежандр изучали эллиптические интегралы — интегралы вида \(\int \frac{dx}{\sqrt{P(x)}}\), где \(P(x)\) — многочлен третьей или четвёртой степени. Обращение этих интегралов привело к эллиптическим функциям, которые, в свою очередь, параметризуют эллиптические кривые. Карл Густав Якоб Якоби и Нильс Хенрик Абель заложили основы теории эллиптических функций.

Развитие в алгебраической геометрии

В XX веке эллиптические кривые стали центральным объектом алгебраической геометрии и теории чисел. В 1922 году Луис Морделл доказал, что группа рациональных точек на эллиптической кривой над полем рациональных чисел является конечно порождённой абелевой группой (теорема Морделла). В 1985 году Герхард Фрей выдвинул гипотезу, связывающую эллиптические кривые с великой теоремой Ферма, что в 1994 году привело Эндрю Уайлса к её доказательству. Уайлс показал, что каждая полустабильная эллиптическая кривая над рациональными числами является модулярной (гипотеза Таниямы — Симуры), что исключило возможность существования контрпримера к теореме Ферма.

Применение в криптографии

В 1985 году Нил Коблиц и Виктор Миллер независимо предложили использовать эллиптические кривые в криптографии. Это привело к созданию криптосистем на основе эллиптических кривых (ECC), которые обеспечивают эквивалентную стойкость при значительно меньших размерах ключей по сравнению с RSA.

Определение и классификация

Уравнение Вейерштрасса

Эллиптическая кривая \(E\) над полем \(K\) (характеристика не 2 и не 3) задаётся уравнением: \[ E: y^2 = x^3 + ax + b, \quad a, b \in K, \quad \Delta = -16(4a^3 + 27b^2) \neq 0. \] Для полей характеристики 2 или 3 используется более общая форма Вейерштрасса. Точка на бесконечности \( \mathcal{O} \) добавляется как нейтральный элемент группы.

Классификация по дискриминанту и j-инварианту

• j-инвариант: \(j(E) = 1728 \frac{4a^3}{4a^3 + 27b^2}\). Две эллиптические кривые изоморфны над алгебраическим замыканием поля тогда и только тогда, когда их j-инварианты равны.
• Дискриминант: \(\Delta \neq 0\) — условие несингулярности. Если \(\Delta = 0\), кривая вырождается (имеет особую точку) и не является эллиптической.

Групповая структура

На множестве точек эллиптической кривой (включая бесконечно удалённую точку \(\mathcal{O}\)) определена операция сложения, превращающая его в абелеву группу. Геометрически сложение двух точек \(P\) и \(Q\) строится так: проводится прямая через \(P\) и \(Q\); третья точка пересечения прямой с кривой отражается относительно оси абсцисс. Нейтральным элементом является \(\mathcal{O}\). Обратная точка к \(P = (x, y)\) — это \( -P = (x, -y)\).

Применение

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

ECC — семейство криптосистем с открытым ключом, основанных на сложности задачи дискретного логарифма в группе точек эллиптической кривой. Основные протоколы:

• ECDH (Elliptic Curve Diffie-Hellman) — протокол выработки общего секретного ключа.
• ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм цифровой подписи, используемый, например, в блокчейне Биткойна и в протоколах TLS.
• EdDSA (Edwards-curve Digital Signature Algorithm) — вариант на кривых Эдвардса (например, Curve25519).

Преимущества ECC перед RSA: при одинаковом уровне стойкости (например, 128 бит) ключ ECC имеет длину 256 бит, тогда как ключ RSA — 3072 бита. Это уменьшает вычислительную нагрузку и требования к памяти.

Теория чисел

• Великая теорема Ферма: доказательство Уайлса использует модулярность эллиптических кривых.
• Гипотеза Берча — Свиннертон-Дайера: одна из семи «задач тысячелетия» Института Клэя, связывающая ранг эллиптической кривой с поведением её L-функции.
• Алгоритм факторизации Ленстры: использует эллиптические кривые для факторизации больших целых чисел.

Физика и другие области

• Теория струн: эллиптические кривые возникают при компактификации дополнительных измерений.
• Кодирование: эллиптические кривые применяются в теории кодирования для построения кодов, исправляющих ошибки.

Примеры эллиптических кривых

Кривая secp256k1

Используется в криптовалюте Биткойн. Уравнение: \(y^2 = x^3 + 7\) над полем \(F_p\), где \(p = 2^{256} - 2^{32} - 977\). Эта кривая является стандартом для ECDSA в Биткойне.

Кривая Curve25519

Предложена Дэниелом Бернштейном. Уравнение: \(y^2 = x^3 + 486662x^2 + x\) над полем \(F_p\) с \(p = 2^{255} - 19\). Используется в протоколе X25519 (разновидность ECDH) и в Ed25519 (цифровая подпись). Отличается высокой скоростью и устойчивостью к атакам.

Кривая P-256 (NIST P-256)

Стандарт Национального института стандартов и технологий США (NIST). Уравнение: \(y^2 = x^3 - 3x + b\) над полем \(F_p\) с определённым \(p\) и \(b\). Широко применяется в TLS и правительственных системах.

Интересные факты

• Количество рациональных точек: согласно теореме Хассе, число точек эллиптической кривой над конечным полем \(F_q\) лежит в интервале \(q + 1 \pm 2\sqrt{q}\).
• Ранг кривой: максимальный известный ранг эллиптической кривой над рациональными числами (на 2024 год) составляет не менее 28 (найдено Ноамом Элкисом и другими).
• Связь с музыкой: некоторые композиторы (например, Том Джонсон) использовали эллиптические кривые для генерации музыкальных последовательностей.
• Рекорд факторизации: в 2020 году с помощью алгоритма Ленстры на эллиптических кривых было разложено число RSA-250 (795 бит).

Критика и ограничения

• Квантовая угроза: алгоритм Шора позволяет решать задачу дискретного логарифма на эллиптических кривых за полиномиальное время на квантовом компьютере. Это ставит под сомнение долгосрочную безопасность ECC.
• Сложность реализации: неправильный выбор кривой или параметров (например, использование слабой случайности) может привести к уязвимостям.
• Стандартизация: некоторые стандартные кривые (например, от NIST) подвергались критике из-за возможного внедрения «чёрных ходов» (backdoors), хотя доказательств этому нет.

Источники

• Сильверман Дж. «Арифметика эллиптических кривых». — М.: МЦНМО, 2001.
• Коблиц Н. «Курс теории чисел и криптографии». — М.: ТВП, 2001.
• Хассе Г. «Лекции по теории чисел». — М.: ИЛ, 1953.
• Стандарт NIST FIPS 186-5 (Digital Signature Standard).
• Бернштейн Д. «Curve25519: New Diffie-Hellman Speed Records» (2006).
• Уайлс Э. «Modular elliptic curves and Fermat’s Last Theorem» (1995).