Кривая Эдвардса¶

Кривая Эдвардса — это семейство эллиптических кривых, используемых в криптографии, описываемое уравнением вида \(x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2\), где \(d\) — параметр, не равный 0 или 1. Предложены американским математиком Гарольдом Эдвардсом в 2007 году как альтернатива традиционным эллиптическим кривым в форме Вейерштрасса. Отличаются высокой скоростью выполнения арифметических операций, устойчивостью к некоторым типам атак и простотой реализации, что делает их привлекательными для современных криптографических систем, включая протоколы цифровой подписи и обмена ключами.

¶История

Кривые Эдвардса были впервые описаны Гарольдом Эдвардсом в 2007 году в статье «A normal form for elliptic curves». Эдвардс предложил новую форму записи эллиптических кривых, которая упрощает вычисления и уменьшает количество операций, необходимых для сложения точек. В 2008 году Дэниел Бернстайн и Таня Ланге опубликовали работу, в которой показали, что кривые Эдвардса могут быть использованы для создания высокоэффективных криптографических систем, и ввели понятие «скрученных кривых Эдвардса» (twisted Edwards curves), описываемых уравнением \(a \cdot x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2\), где \(a\) — дополнительный параметр. Это расширение позволило включить в семейство большее количество кривых, включая те, которые ранее использовались в стандартах, таких как Curve25519.

С 2010-х годов кривые Эдвардса начали активно внедряться в практические криптографические протоколы. В 2013 году они были включены в стандарт Национального института стандартов и технологий США (NIST) для цифровых подписей EdDSA (Edwards-curve Digital Signature Algorithm). В России кривые Эдвардса не являются стандартизированными для государственных нужд, но используются в коммерческих и открытых проектах.

¶Математическое описание

¶Уравнение и параметры

Кривая Эдвардса задается уравнением:

\[ x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2 \]

где \(x\) и \(y\) — координаты точки на кривой, а \(d\) — параметр, отличный от 0 и 1. Для скрученной кривой Эдвардса уравнение принимает вид:

\[ a \cdot x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2 \]

где \(a\) — дополнительный параметр, обычно равный 1 или -1. Параметры \(a\) и \(d\) выбираются так, чтобы кривая была невырожденной (не имела сингулярностей) и обладала криптографической стойкостью.

¶Арифметика точек

Основное преимущество кривых Эдвардса — простота и скорость операций сложения и удвоения точек. Сложение двух точек \((x_1, y_1)\) и \((x_2, y_2)\) на кривой выполняется по формулам:

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

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

¶Нейтральный элемент

На кривой Эдвардса нейтральным элементом (точкой «бесконечности» в традиционных кривых) является точка \((0, 1)\). Это упрощает реализацию протоколов, так как не требует специальной обработки для нулевого элемента.

¶Классификация

¶Обычные кривые Эдвардса

Описываются уравнением \(x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2\). Параметр \(a\) равен 1. Пример: кривая Ed25519, используемая в алгоритме EdDSA.

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

Описываются уравнением \(a \cdot x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2\), где \(a\) может быть отличен от 1 (часто \(a = -1\)). Это расширение позволяет включать в семейство кривые, которые не могут быть представлены в обычной форме. Пример: кривая Ed448-Goldilocks, используемая в некоторых реализациях.

¶Кривые с параметром d, не являющимся квадратом

Для криптографической стойкости важно, чтобы параметр \(d\) не был квадратом в поле \(F_p\) (где \(p\) — простое число). Это предотвращает атаки, основанные на изоморфизмах.

¶Применение

¶Цифровая подпись (EdDSA)

Основное применение кривых Эдвардса — алгоритм цифровой подписи EdDSA (Edwards-curve Digital Signature Algorithm), который является вариантом схемы Шнорра. EdDSA использует кривые Ed25519 (на основе Curve25519) и Ed448. Преимущества EdDSA перед ECDSA (Elliptic Curve Digital Signature Algorithm) включают:

• Высокую скорость генерации и верификации подписей.
• Отсутствие необходимости в генерации случайных чисел (детерминированная подпись), что снижает риск утечки ключа.
• Устойчивость к атакам по времени (side-channel attacks) благодаря постоянному времени выполнения операций.

EdDSA стандартизирован в RFC 8032 (2017 год) и используется в протоколах SSH, TLS, DNSSEC, а также в криптовалютах, таких как Monero и Stellar.

¶Обмен ключами

Кривые Эдвардса могут быть использованы для протоколов обмена ключами, таких как X25519 (на основе Curve25519). X25519 — это функция Диффи-Хеллмана на эллиптической кривой, которая использует скрученную кривую Эдвардса Ed25519. Она обеспечивает высокую скорость и безопасность, и широко применяется в TLS 1.3, Signal Protocol и других системах.

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

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

¶Преимущества и недостатки

¶Преимущества

• Высокая скорость: операции сложения и удвоения на кривых Эдвардса выполняются быстрее, чем на кривых в форме Вейерштрасса, благодаря меньшему количеству умножений в поле.
• Устойчивость к атакам: симметричные формулы сложения и отсутствие деления на координаты делают кривые менее уязвимыми к атакам по времени и атакам на основе анализа мощности.
• Простота реализации: нейтральный элемент \((0, 1)\) и отсутствие необходимости в специальной обработке для точки бесконечности упрощают код.
• Детерминированность: в EdDSA подпись не зависит от генератора случайных чисел, что исключает уязвимости, связанные с плохой случайностью.

¶Недостатки

• Ограниченное семейство: не все эллиптические кривые могут быть преобразованы в форму Эдвардса. Например, кривые с параметром \(a = 0\) (как некоторые стандартные кривые NIST) не могут быть представлены в этой форме.
• Меньшая распространенность: хотя кривые Эдвардса становятся популярнее, многие старые системы и стандарты (например, ГОСТ Р 34.10-2012 в России) используют кривые Вейерштрасса, что затрудняет миграцию.
• Зависимость от параметра \(d\): неправильный выбор параметра \(d\) (например, если он является квадратом) может привести к снижению стойкости.

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

¶Ed25519

• Уравнение: \(x^2 + y^2 = 1 + (121665/121666) \cdot x^2 \cdot y^2\) над полем \(F_p\), где \(p = 2^{255} - 19\).
• Используется в EdDSA (Ed25519) и X25519.
• Обеспечивает 128-битный уровень безопасности.

¶Ed448-Goldilocks

• Уравнение: \(x^2 + y^2 = 1 - 39081 \cdot x^2 \cdot y^2\) над полем \(F_p\), где \(p = 2^{448} - 2^{224} - 1\).
• Используется в EdDSA (Ed448) и X448.
• Обеспечивает 224-битный уровень безопасности.

¶Критика

Кривые Эдвардса критикуются за то, что они не являются универсальными: не все кривые, используемые в существующих стандартах, могут быть преобразованы в эту форму. Это создает проблемы совместимости при переходе с традиционных кривых. Кроме того, некоторые исследователи отмечают, что упрощенная арифметика может скрывать потенциальные уязвимости, связанные с атаками на основе изогении (isogeny attacks), хотя на практике таких атак для кривых Эдвардса не обнаружено.

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

• Кривая Ed25519 была разработана Дэниелом Бернстайном и используется в протоколе Signal, который применяется в мессенджерах WhatsApp (продукт Meta, признанной экстремистской и запрещённой в РФ) и Signal (признаны экстремистскими и запрещены в РФ — прим. автора: на момент написания статьи статус не подтвержден, но упоминается для контекста).
• В 2019 году в стандарт TLS 1.3 были включены алгоритмы на основе кривых Эдвардса (Ed25519 и Ed448) для аутентификации серверов.
• В России кривые Эдвардса не входят в государственные стандарты (ГОСТ Р 34.10-2012 использует кривые Вейерштрасса), но применяются в коммерческих продуктах, например, в некоторых реализациях блокчейн-платформ.