Группа точек эллиптической кривой

Группа точек эллиптической кривой — это абелева группа, образованная множеством рациональных точек на эллиптической кривой, определённой над некоторым полем, вместе с операцией сложения точек, задаваемой геометрическим правилом «хорд и касательных». В криптографии, алгебраической геометрии и теории чисел эта структура является фундаментальным объектом, лежащим в основе таких приложений, как эллиптическая криптография (ECC) и доказательство великой теоремы Ферма.

Определение и основные свойства

Эллиптическая кривая над полем \( K \) (обычно \( \mathbb{Q} \), \( \mathbb{R} \), \( \mathbb{C} \) или конечным полем \( \mathbb{F}_q \)) задаётся уравнением Вейерштрасса: \[ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6, \] где коэффициенты \( a_i \in K \), и дискриминант кривой ненулевой (кривая неособая). Для простоты часто используют короткую форму Вейерштрасса: \[ y^2 = x^3 + ax + b, \] где \( a, b \in K \), и \( 4a^3 + 27b^2 \neq 0 \).

Множество точек \( E(K) \) включает все пары \( (x, y) \in K^2 \), удовлетворяющие уравнению, а также бесконечно удалённую точку \( \mathcal{O} \), которая играет роль нейтрального элемента группы.

Операция сложения

Групповая операция определяется геометрически:

1. Сложение двух различных точек \( P \) и \( Q \). Проводится прямая через \( P \) и \( Q \). Она пересекает кривую в третьей точке \( R \). Тогда \( P + Q = -R \), где \( -R \) — точка, симметричная \( R \) относительно оси абсцисс (для короткой формы Вейерштрасса).

1. Удвоение точки \( P \). Проводится касательная к кривой в точке \( P \). Она пересекает кривую в точке \( R \). Тогда \( 2P = P + P = -R \).

1. Сложение с бесконечно удалённой точкой: \( P + \mathcal{O} = P \).

1. Обратная точка: \( -P \) — это точка, симметричная \( P \) относительно оси \( x \). Для точки \( P = (x, y) \) имеем \( -P = (x, -y) \).

Эта операция коммутативна, ассоциативна, имеет нейтральный элемент \( \mathcal{O} \) и обратный элемент для каждой точки, что делает \( E(K) \) абелевой группой.

Структура группы

Конечные поля

Для эллиптической кривой над конечным полем \( \mathbb{F}_q \) группа \( E(\mathbb{F}_q) \) конечна. Её порядок \( N = |E(\mathbb{F}_q)| \) удовлетворяет теореме Хассе: \[ |N - (q + 1)| \leq 2\sqrt{q}. \] Структура группы — прямое произведение двух циклических групп: \[ E(\mathbb{F}_q) \cong \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}, \] где \( n_2 \) делит \( n_1 \), и \( n_2 \) делит \( q - 1 \). Это свойство важно для криптографии, так как сложность задачи дискретного логарифмирования в эллиптической кривой (ECDLP) зависит от порядка группы.

Поле рациональных чисел

Над полем \( \mathbb{Q} \) группа \( E(\mathbb{Q}) \) является конечно порождённой абелевой группой (теорема Морделла — Вейля): \[ E(\mathbb{Q}) \cong \mathbb{Z}^r \times T, \] где \( r \) — ранг кривой, а \( T \) — конечная подгруппа кручения. Ранг может быть нулевым (конечная группа) или положительным (бесконечная группа). Поиск ранга и вычисление образующих — активная область исследований. Например, кривая \( y^2 = x^3 - x \) имеет ранг 0, а \( y^2 = x^3 + 1 \) — ранг 0 с кручением порядка 6. Кривая \( y^2 = x^3 - 2 \) имеет ранг 1, а её образующая — точка \( (3, 5) \).

Подгруппа кручения

Подгруппа кручения \( T \) состоит из точек конечного порядка. Теорема Мазура (1977) классифицирует возможные подгруппы кручения для эллиптических кривых над \( \mathbb{Q} \): \[ \mathbb{Z}_n \text{ для } n = 1, 2, \dots, 10, 12, \] \[ \mathbb{Z}_2 \times \mathbb{Z}_{2n} \text{ для } n = 1, 2, 3, 4. \] Над конечными полями возможны более разнообразные структуры кручения.

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

Эллиптическая криптография (ECC) использует группу точек эллиптической кривой над конечным полем для построения криптосистем с открытым ключом. Основные алгоритмы:

• ECDH (Elliptic Curve Diffie-Hellman) — протокол обмена ключами.
• ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм цифровой подписи.
• ECIES (Elliptic Curve Integrated Encryption Scheme) — гибридная схема шифрования.

Безопасность ECC основана на сложности задачи дискретного логарифмирования в группе точек (ECDLP): по данным точкам \( P \) и \( Q = kP \) найти целое число \( k \). Для кривых с большим простым порядком подгруппы (например, 256-битные кривые, такие как secp256k1) эта задача считается вычислительно неразрешимой при современном уровне развития алгоритмов. ECC обеспечивает аналогичный уровень безопасности, как RSA, но при значительно меньших размерах ключей (например, 256-битный ключ ECC эквивалентен 3072-битному ключу RSA).

Другие применения

• Теория чисел: эллиптические кривые используются в доказательстве великой теоремы Ферма (Эндрю Уайлс, 1994) через гипотезу Таниямы — Шимуры.
• Факторизация целых чисел: метод Ленстры (ECM) использует группы точек эллиптических кривых для нахождения малых простых делителей.
• Проверка простоты: тест Гольдвассер — Килиана и тест Аткина — Мораина основаны на эллиптических кривых.
• Изогении: криптография на изогениях (SIDH, CSIDH) использует отображения между эллиптическими кривыми.

Примеры

1. Кривая secp256k1 (используется в биткойне):

\[ y^2 = x^3 + 7 \pmod{p}, \] где \( p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 \). Порядок группы — простое число, равное \( 2^{256} - 432420386565659656852420866394968145599 \).

1. Кривая NIST P-256 (стандарт FIPS 186-4):

\[ y^2 = x^3 - 3x + b \pmod{p}, \] где \( p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1 \), \( b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b \).

1. Кривая над \( \mathbb{Q} \): \( y^2 = x^3 - x \). Её группа \( E(\mathbb{Q}) \) состоит из четырёх точек: \( \mathcal{O}, (0,0), (1,0), (-1,0) \), что изоморфно \( \mathbb{Z}_2 \times \mathbb{Z}_2 \).

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

• Квантовая угроза: алгоритм Шора позволяет эффективно решать ECDLP на квантовом компьютере, что может сделать ECC уязвимой в будущем. В ответ разрабатываются постквантовые криптосистемы (например, на решётках).
• Сложность реализации: неправильный выбор кривой или параметров (например, малый порядок подгруппы) может привести к уязвимостям. Известны атаки на кривые с аномальным порядком (MOV-атака, атака Смарта).
• Стандартизация: в России стандарт ГОСТ Р 34.10-2012 определяет параметры эллиптических кривых для цифровой подписи, но не все кривые из зарубежных стандартов (например, NIST) рекомендованы к использованию в РФ.

Источники

• Silverman, J. H. The Arithmetic of Elliptic Curves. Springer, 2009.
• Washington, L. C. Elliptic Curves: Number Theory and Cryptography. CRC Press, 2008.
• Koblitz, N. A Course in Number Theory and Cryptography. Springer, 1994.
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.
• Mazur, B. "Modular curves and the Eisenstein ideal." Publications Mathématiques de l'IHÉS, 1977.