Кривая Монтгомери

Кривая Монтгомери — это класс эллиптических кривых, задаваемых уравнением вида \(By^2 = x^3 + Ax^2 + x\) над конечным полем, где \(B(A^2 - 4) \neq 0\). Данный тип кривых был впервые предложен в 1987 году американским математиком Питером Монтгомери для ускорения операций в криптографии на эллиптических кривых (ECC). Кривые Монтгомери обладают особыми алгебраическими свойствами, позволяющими выполнять вычисления с высокой эффективностью, что делает их основой для ряда современных криптографических алгоритмов, включая протокол обмена ключами X25519.

История

Кривые Монтгомери были введены в 1987 году в работе Питера Монтгомери «Speeding the Pollard and Elliptic Curve Methods of Factorization». Изначально они разрабатывались для ускорения алгоритмов факторизации целых чисел, в частности метода эллиптических кривых (ECM). Однако вскоре исследователи заметили, что свойства этих кривых могут быть полезны и в криптографии.

В 2006 году Дэниел Бернстайн представил протокол Curve25519, основанный на кривой Монтгомери \(y^2 = x^3 + 486662x^2 + x\) над полем \(p = 2^{255} - 19\). Этот протокол лёг в основу алгоритма обмена ключами X25519, который стал широко применяться в современных интернет-протоколах, таких как TLS 1.3, Signal и SSH. В 2013 году Curve25519 был стандартизирован IETF (RFC 7748). В 2020 году Национальный институт стандартов и технологий США (NIST) включил кривые Монтгомери в свои рекомендации по криптографии на эллиптических кривых (SP 800-186).

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

Кривая Монтгомери над конечным полем \(\mathbb{F}_p\) (где \(p\) — простое число, \(p > 3\)) задаётся уравнением:

\[ By^2 = x^3 + Ax^2 + x \]

где \(A, B \in \mathbb{F}_p\), причём \(B(A^2 - 4) \neq 0\). Условие \(B(A^2 - 4) \neq 0\) гарантирует, что кривая не является сингулярной (не имеет самопересечений или острых точек). Кривая Монтгомери является частным случаем эллиптической кривой в форме Вейерштрасса, но её уравнение специально подобрано для ускорения вычислений.

Особые точки

Кривая Монтгомери всегда содержит точку в бесконечности \(\mathcal{O}\), которая является нейтральным элементом в группе точек кривой. Кроме того, при \(x = 0\) получается точка \((0, 0)\), которая имеет порядок 2. В зависимости от параметров, кривая может содержать и другие точки с порядком 2.

Криптографические свойства

Кривые Монтгомери обладают рядом свойств, делающих их привлекательными для криптографии:

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

Основное преимущество кривых Монтгомери — возможность использования проективных координат, в которых точка представляется тройкой \((X : Y : Z)\), а не парой \((x, y)\). В проективных координатах уравнение кривой принимает вид:

\[ BY^2Z = X^3 + AX^2Z + XZ^2 \]

При этом сложение точек и удвоение точки можно выполнять, используя только координаты \(X\) и \(Z\), без вычисления \(Y\). Это позволяет избежать дорогостоящих операций инверсии в поле, заменяя их умножениями. В результате операции на кривой Монтгомери выполняются значительно быстрее, чем на обычных эллиптических кривых в форме Вейерштрасса.

Устойчивость к атакам по времени

Алгоритмы на кривых Монтгомери, как правило, используют только операции сложения и удвоения точек, что позволяет реализовать их с постоянным временем выполнения (constant-time). Это делает их устойчивыми к атакам по времени (timing attacks), которые анализируют время выполнения операций для извлечения секретных ключей.

Скалярное умножение

Скалярное умножение \(kP\) (где \(k\) — целое число, \(P\) — точка кривой) на кривой Монтгомери может быть выполнено с помощью алгоритма Монтгомери-лестницы (Montgomery ladder). Этот алгоритм выполняет последовательность удвоений и сложений точек, причём на каждом шаге выполняется ровно одна операция удвоения и одна операция сложения, независимо от значения битов \(k\). Это обеспечивает как постоянное время выполнения, так и защиту от атак по сторонним каналам.

Применение

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

Наиболее известное применение кривых Монтгомери — протокол обмена ключами X25519 (Curve25519). Он основан на кривой \(y^2 = x^3 + 486662x^2 + x\) над полем \(p = 2^{255} - 19\). Протокол использует скалярное умножение на кривой Монтгомери для вычисления общего секрета между двумя сторонами. X25519 является одним из самых быстрых и безопасных протоколов обмена ключами, что привело к его широкому распространению в интернет-стандартах.

Протоколы цифровой подписи

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

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

Кривые Монтгомери также применяются в:

• Гомоморфное шифрование: некоторые схемы гомоморфного шифрования используют эллиптические кривые, и кривые Монтгомери могут ускорять вычисления.
• Доказательства с нулевым разглашением: в протоколах, таких как zk-SNARKs, могут использоваться кривые Монтгомери для эффективных вычислений.
• Факторизация целых чисел: метод эллиптических кривых (ECM) для факторизации больших чисел часто использует кривые Монтгомери для ускорения операций.

Примеры кривых Монтгомери

Curve25519 (X25519)

• Поле: \(p = 2^{255} - 19\) (простое число)
• Уравнение: \(y^2 = x^3 + 486662x^2 + x\)
• Кофактор: 8
• Порядок кривой: \(8 \cdot q\), где \(q\) — простое число
• Применение: протокол обмена ключами X25519 (RFC 7748)

Curve448 (X448)

• Поле: \(p = 2^{448} - 2^{224} - 1\) (простое число)
• Уравнение: \(y^2 = x^3 + 156326x^2 + x\)
• Кофактор: 4
• Порядок кривой: \(4 \cdot q\), где \(q\) — простое число
• Применение: протокол обмена ключами X448 (RFC 7748)

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

Кривые Вейерштрасса

Кривые Вейерштрасса (формы \(y^2 = x^3 + ax + b\)) являются наиболее общим представлением эллиптических кривых. Они широко используются в стандартах, таких как NIST P-256. Однако операции на кривых Вейерштрасса требуют большего количества вычислений, особенно инверсий в поле. Кривые Монтгомери, напротив, оптимизированы для быстрого скалярного умножения, но не все эллиптические кривые можно преобразовать в форму Монтгомери.

Кривые Эдвардса

Кривые Эдвардса (формы \(x^2 + y^2 = 1 + dx^2y^2\)) также являются эффективными для криптографии. Они бирационально эквивалентны кривым Монтгомери, что позволяет легко преобразовывать точки между этими формами. Кривые Эдвардса обладают дополнительными преимуществами, такими как полная абелева группа (без исключительных точек), но кривые Монтгомери проще в реализации для протоколов обмена ключами.

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

Безопасность криптосистем на кривых Монтгомери основана на сложности задачи дискретного логарифмирования на эллиптической кривой (ECDLP). Для кривых, таких как Curve25519 и Curve448, считается, что задача ECDLP имеет экспоненциальную сложность относительно размера поля. Кривые Монтгомери специально выбираются с простым порядком (или с малым кофактором) и без известных уязвимостей, таких как атаки на основе спаривания или атаки на кривые с особыми свойствами.

Кривые Монтгомери, используемые в современных стандартах, не имеют известных уязвимостей, и их безопасность подтверждена многолетними криптоаналитическими исследованиями.

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

• Кривые Монтгомери были названы в честь Питера Монтгомери, который разработал их для ускорения алгоритмов факторизации, а не для криптографии.
• Протокол X25519 (Curve25519) был разработан Дэниелом Бернстайном в 2006 году и с тех пор стал одним из самых распространённых протоколов обмена ключами в интернете.
• Кривые Монтгомери не поддерживают операции спаривания (pairing), что ограничивает их применение в некоторых криптографических протоколах, таких как схемы на основе идентичности (IBE).

Источники

• Montgomery, P. L. (1987). «Speeding the Pollard and Elliptic Curve Methods of Factorization». Mathematics of Computation, 48(177), 243–264.
• Bernstein, D. J. (2006). «Curve25519: New Diffie-Hellman Speed Records». Public Key Cryptography – PKC 2006, 207–228.
• RFC 7748: «Elliptic Curves for Security» (2016). Internet Engineering Task Force.
• NIST SP 800-186: «Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters» (2020).
• Hankerson, D., Menezes, A., Vanstone, S. (2004). «Guide to Elliptic Curve Cryptography». Springer.