Скрученная кривая Эдвардса

Скрученная кривая Эдвардса — это алгебраическая кривая, задаваемая уравнением вида \(a x^2 + y^2 = 1 + d x^2 y^2\), где \(a\) и \(d\) — элементы поля (обычно конечного), не равные нулю, причём \(a \neq d\). Она является обобщением кривой Эдвардса (\(a=1\)) и относится к классу эллиптических кривых в форме Эдвардса. Скрученные кривые Эдвардса используются в криптографии с открытым ключом, в частности, в алгоритмах цифровой подписи и протоколах обмена ключами, благодаря высокой скорости вычислений и устойчивости к некоторым видам атак.

История

Кривые Эдвардса были впервые описаны американским математиком Гарольдом Эдвардсом в 2007 году как альтернативная форма эллиптических кривых, удобная для вычислений. В 2008 году Дэниел Бернстайн и Таня Ланге предложили обобщение — скрученные кривые Эдвардса, которые позволили охватить большее число эллиптических кривых, включая те, что используются в стандартах (например, Curve25519). В 2011 году скрученные кривые Эдвардса были включены в стандарт Национального института стандартов и технологий США (NIST) для криптографических алгоритмов.

Определение и уравнение

Скрученная кривая Эдвардса над полем \(K\) (характеристика которого не равна 2) задаётся уравнением:

\[ E_{a,d}: a x^2 + y^2 = 1 + d x^2 y^2, \]

где \(a, d \in K\), \(a d (a - d) \neq 0\). Параметр \(a\) отвечает за «скручивание»: при \(a=1\) кривая превращается в обычную кривую Эдвардса. Если \(a\) — квадрат в поле \(K\), то кривая изоморфна кривой Эдвардса; в противном случае она является квадратичным скручиванием.

Особые точки

Кривая не имеет особых точек при условии \(a d (a - d) \neq 0\). Точка \((0,1)\) является нейтральным элементом (единицей) для группового закона. Точки \((0,-1)\) и \((\pm 1/\sqrt{a}, 0)\) имеют порядок 2 и 4 соответственно.

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

На скрученной кривой Эдвардса определена операция сложения точек, превращающая её в абелеву группу. Для точек \(P_1 = (x_1, y_1)\) и \(P_2 = (x_2, y_2)\) их сумма \(P_3 = (x_3, y_3)\) вычисляется по формулам:

\[ x_3 = \frac{x_1 y_2 + y_1 x_2}{1 + d x_1 x_2 y_1 y_2}, \quad y_3 = \frac{y_1 y_2 - a x_1 x_2}{1 - d x_1 x_2 y_1 y_2}. \]

Эти формулы универсальны: они работают для всех точек, включая нейтральный элемент и точки порядка 2, без необходимости в отдельных случаях. Сложение является коммутативным и ассоциативным. Удвоение точки получается как частный случай при \(P_1 = P_2\).

Преимущества группового закона

• Единообразие: не требуется проверять особые случаи (например, сложение с бесконечно удалённой точкой), что упрощает реализацию.
• Скорость: вычисления требуют меньше операций в поле по сравнению с кривыми в форме Вейерштрасса, особенно при использовании проективных координат.
• Устойчивость к атакам по времени: формулы не содержат условных переходов, что затрудняет анализ времени выполнения.

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

Для ускорения вычислений используется проективная форма кривой. В однородных координатах \((X : Y : Z)\) уравнение принимает вид:

\[ a X^2 Z^2 + Y^2 Z^2 = Z^4 + d X^2 Y^2. \]

После упрощения получаем:

\[ a X^2 Z^2 + Y^2 Z^2 - Z^4 - d X^2 Y^2 = 0. \]

Точка на кривой представляется тройкой \((X, Y, Z)\), где \(Z \neq 0\), а аффинные координаты восстанавливаются как \(x = X/Z\), \(y = Y/Z\). Нейтральный элемент в проективных координатах — \((0, 1, 1)\). Сложение в проективных координатах выполняется без деления, что значительно быстрее.

Связь с кривыми в форме Вейерштрасса

Любая скрученная кривая Эдвардса бирационально эквивалентна некоторой эллиптической кривой в форме Вейерштрасса. Преобразование задаётся формулами:

\[ u = \frac{a + y}{a - y}, \quad v = \frac{2a}{a - y} \cdot \frac{1}{x}, \]

где \((u, v)\) — координаты на кривой Вейерштрасса. Обратное преобразование:

\[ x = \frac{2a}{v(a - y)}, \quad y = \frac{a(u - 1)}{u + 1}. \]

Эта эквивалентность позволяет переносить результаты из теории эллиптических кривых на скрученные кривые Эдвардса.

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

Скрученные кривые Эдвардса широко используются в криптографии с открытым ключом благодаря следующим свойствам:

• Высокая производительность: операции сложения и удвоения точек выполняются быстрее, чем на кривых в форме Вейерштрасса, особенно на процессорах с ограниченными ресурсами (например, в смарт-картах).
• Устойчивость к атакам по сторонним каналам: единообразные формулы сложения затрудняют анализ времени выполнения и энергопотребления.
• Малый размер ключей: эллиптические кривые обеспечивают эквивалентную безопасность при меньших длинах ключей по сравнению с RSA.

Примеры кривых

• Curve25519 (X25519): используется в протоколе обмена ключами Diffie-Hellman на эллиптических кривых (ECDH). Её скрученная форма Эдвардса — Ed25519 — применяется в алгоритме цифровой подписи EdDSA. Параметры: \(a = -1\), \(d = -121665/121666\) над простым полем \(p = 2^{255} - 19\).
• Curve448 (X448): аналогичная кривая для 448-битного поля, используется в Ed448-Goldilocks. Параметры: \(a = 1\), \(d = -39081\) над полем \(p = 2^{448} - 2^{224} - 1\).

Стандартизация

Скрученные кривые Эдвардса включены в следующие стандарты:

• NIST SP 800-186 (2019): рекомендации по использованию кривых Эдвардса.
• RFC 8032 (2017): описание алгоритма EdDSA, основанного на кривых Ed25519 и Ed448.
• ГОСТ Р 34.10-2021 (Россия): в стандарте цифровой подписи предусмотрена возможность использования кривых в форме Эдвардса, в том числе скрученных.

Безопасность

Скрученные кривые Эдвардса обладают высокой криптостойкостью при правильном выборе параметров. Основные угрозы:

• Атака на дискретный логарифм: для кривых с большим простым порядком (например, Ed25519) эта задача считается вычислительно сложной.
• Атаки по сторонним каналам: единообразные формулы сложения снижают риск, но не устраняют его полностью — требуется защита на уровне протокола.
• Квантовые атаки: как и все эллиптические кривые, скрученные кривые Эдвардса уязвимы для алгоритма Шора, что требует перехода на постквантовую криптографию в будущем.

Сравнение с другими формами

M — умножение в поле, S — возведение в квадрат.

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

• Скрученные кривые Эдвардса позволяют реализовать криптографию с постоянным временем выполнения, что важно для защиты от атак по времени.
• Кривая Ed25519 обеспечивает 128-битный уровень безопасности, а Ed448 — 224-битный.
• В России скрученные кривые Эдвардса используются в некоторых коммерческих и государственных криптографических системах, например, в протоколах защищённого обмена данными.

Источники

• Bernstein, D. J., Lange, T. (2007). "Faster addition and doubling on elliptic curves". Advances in Cryptology – ASIACRYPT 2007.
• Bernstein, D. J., et al. (2012). "Twisted Edwards curves". Progress in Cryptology – AFRICACRYPT 2008.
• RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA), 2017.
• NIST SP 800-186: Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters, 2019.
• ГОСТ Р 34.10-2021: Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.