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

Curve25519 — это эллиптическая кривая, определённая над простым полем, используемая в криптографии с открытым ключом для реализации протоколов обмена ключами и цифровых подписей. Она была предложена американским криптографом Дэниелом Бернштейном в 2006 году и предназначена для обеспечения высокой производительности и безопасности при программной реализации. Curve25519 является одной из наиболее распространённых эллиптических кривых в современных криптосистемах, наряду с кривой NIST P-256.

История

Curve25519 была впервые представлена Дэниелом Бернштейном в 2006 году в статье «Curve25519: New Diffie-Hellman Speed Records». Основной целью разработки было создание кривой, устойчивой к известным атакам на эллиптические кривые, включая атаки на основе дискретного логарифма, и обеспечивающей высокую скорость вычислений на широком спектре процессоров, включая устройства с ограниченными ресурсами.

Бернштейн выбрал простое поле с характеристикой \(2^{255} - 19\), что дало кривой название. Это число было выбрано из-за его близости к степени двойки, что упрощает реализацию арифметики по модулю на 64-битных процессорах. Кривая была спроектирована так, чтобы избежать уязвимостей, связанных с использованием кривых с особыми свойствами, и чтобы минимизировать риск утечки секретных данных через побочные каналы (например, время выполнения или энергопотребление).

В 2013 году на основе Curve25519 был разработан протокол обмена ключами X25519, который был стандартизирован в RFC 7748. В 2014 году на основе той же кривой был создан алгоритм цифровой подписи Ed25519, описанный в RFC 8032. С тех пор Curve25519 широко применяется в таких протоколах, как TLS 1.3, Signal, SSH, а также в криптовалютах (например, Monero и Stellar).

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

Уравнение кривой

Curve25519 задаётся уравнением Монтгомери:

\[ y^2 = x^3 + 486662x^2 + x \]

над простым полем \( \mathbb{F}_p \), где:

\[ p = 2^{255} - 19 \]

Это простое число длиной 255 бит. Коэффициент \( a = 486662 \) был выбран Бернштейном как наименьшее целое значение, удовлетворяющее определённым критериям безопасности (например, чтобы порядок кривой и её квадратичного поворота были простыми числами).

Порядок кривой

Порядок кривой (количество точек, включая точку на бесконечности) равен:

\[ n = 2^{252} + 27742317777372353535851937790883648493 \]

Это простое число. Кофактор кривой (отношение порядка кривой к порядку базовой точки) равен 8. Это означает, что кривая содержит подгруппу простого порядка \( n/8 \), которая используется в криптографических протоколах.

Базовая точка

Базовая точка \( G \) имеет координату \( x = 9 \). Её порядок равен \( n/8 \), что обеспечивает работу в подгруппе простого порядка. Выбор \( x = 9 \) был сделан для упрощения вычислений и минимизации риска особых случаев.

Свойства безопасности

Устойчивость к атакам

Curve25519 спроектирована для устойчивости к известным атакам на эллиптические кривые:

• Дискретный логарифм: порядок кривой и её подгруппы являются простыми числами, что исключает возможность атаки Полига — Хеллмана. Ожидаемая сложность атаки составляет около \( 2^{128} \) операций (128-битный уровень безопасности).
• Атаки на основе спаривания: кривая не является суперсингулярной, что предотвращает атаки с использованием спариваний Вейля или Тейта.
• Атаки на основе переноса: поле имеет большой простой характеристику, что исключает возможность переноса на аддитивную группу.
• Атаки на основе побочных каналов: реализация X25519 использует только координату \( x \) и не зависит от знака \( y \), что позволяет избежать условных переходов и упрощает защиту от атак по времени.

Отсутствие встроенных уязвимостей

В отличие от кривых, рекомендованных NIST (например, P-256), Curve25519 не содержит параметров, которые могли бы быть выбраны с целью ослабления безопасности. Коэффициент \( a = 486662 \) был выбран на основе открытых и прозрачных критериев, что исключает подозрения в наличии «чёрного хода».

Применение

Протокол обмена ключами X25519

X25519 (также известный как Curve25519-DH) — это функция обмена ключами Диффи — Хеллмана на основе Curve25519. Она принимает на вход 32-байтовый закрытый ключ и 32-байтовый открытый ключ и возвращает 32-байтовый общий секрет. Реализация X25519 использует только координату \( x \) точки, что упрощает вычисления и повышает производительность. Протокол стандартизирован в RFC 7748 и широко применяется в TLS 1.3, SSH, IPsec и других протоколах.

Цифровая подпись Ed25519

Ed25519 — это алгоритм цифровой подписи на основе Curve25519, использующий схему EdDSA (Edwards-curve Digital Signature Algorithm). Он работает с кривой в форме Эдвардса, которая бирационально эквивалентна Curve25519. Ed25519 обеспечивает высокую скорость подписания и верификации, а также устойчивость к атакам с использованием побочных каналов. Алгоритм стандартизирован в RFC 8032 и применяется в таких системах, как OpenSSH, GnuPG, Tor и многих криптовалютах.

Другие протоколы

• Signal Protocol: используется для обмена ключами в мессенджере Signal, а также в WhatsApp (продукт Meta, признанной экстремистской и запрещённой в РФ) и Facebook Messenger (Meta — организация признана экстремистской и запрещена в РФ).
• TLS 1.3: поддерживает X25519 как одну из обязательных групп обмена ключами.
• WireGuard: использует Curve25519 для установления защищённых VPN-соединений.
• Криптовалюты: Monero, Stellar, Cardano и другие используют Ed25519 для подписи транзакций.

Сравнение с другими кривыми

Curve25519 vs NIST P-256

Curve25519 vs Curve448

Curve448 (также известная как Goldilocks) — это ещё одна кривая Монтгомери с полем \(2^{448} - 2^{224} - 1\), обеспечивающая 224-битный уровень безопасности. Она медленнее Curve25519, но предлагает более высокий запас прочности. Curve25519 чаще используется в приложениях, где важна производительность, а Curve448 — в системах, требующих повышенной устойчивости к будущим атакам (например, квантовым).

Реализация

Программная реализация

Curve25519 спроектирована для эффективной программной реализации на большинстве современных процессоров. Арифметика по модулю \(2^{255} - 19\) может быть выполнена с использованием 64-битных целых чисел без аппаратной поддержки больших чисел. Реализации на языке C (например, от самого Бернштейна) и на ассемблере достигают скорости в несколько миллионов операций в секунду на обычных процессорах.

Аппаратная реализация

Существуют аппаратные ускорители для Curve25519, например, в процессорах Intel (через инструкции AVX-512) и в некоторых ARM-процессорах. Однако кривая не требует специализированного оборудования, что делает её доступной для широкого круга устройств.

Библиотеки

Curve25519 поддерживается многими криптографическими библиотеками:

• OpenSSL (начиная с версии 1.1.0)
• libsodium
• NaCl (Networking and Cryptography library)
• WolfSSL
• Botan

Критика

Основной критикой Curve25519 является её кофактор, равный 8. Это может привести к уязвимостям в некоторых протоколах, если не учитывать возможность работы с точками малого порядка. Например, при неправильной реализации X25519 злоумышленник может отправить точку порядка 8, что приведёт к получению общего секрета, равного нулю. Однако стандартные реализации (например, в RFC 7748) включают проверки для предотвращения таких атак.

Также отмечается, что Curve25519 не поддерживает некоторые продвинутые криптографические протоколы, такие как схемы с нулевым разглашением или гомоморфное шифрование, которые требуют кривых с определёнными свойствами (например, кривых с большим кофактором или с возможностью спаривания). Для таких целей обычно используются кривые BLS или BN.

Источники

• Bernstein, D. J. (2006). «Curve25519: New Diffie-Hellman Speed Records». Public Key Cryptography — PKC 2006.
• RFC 7748: «Elliptic Curves for Security».
• RFC 8032: «Edwards-Curve Digital Signature Algorithm (EdDSA)».
• Langley, A., et al. (2016). «Elliptic Curves for Security». Internet Research Task Force.
• Bernstein, D. J., & Lange, T. (2007). «SafeCurves: choosing safe curves for elliptic-curve cryptography».