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

Криптография на эллиптических кривых (ECC) реализует схемы с открытым ключом на основе группы точек эллиптической кривой, достигая той же безопасности, что и RSA или Диффи-Хеллман на конечных полях, но с гораздо меньшими ключами.

Definition

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

Scope

Эта тема охватывает групповой закон эллиптических кривых над конечными полями, проблему дискретного логарифмирования на эллиптических кривых и построенные на них схемы: Диффи-Хеллман на эллиптических кривых (ECDH), схемы подписи ECDSA и EdDSA, а также современные кривые, такие как Curve25519. В ней рассматривается, почему дискретные логарифмы на эллиптических кривых сложнее, чем на конечных полях (отсутствие субэкспоненциального индексного исчисления), и вопросы реализации, такие как повторное использование одноразового кода (nonce) в ECDSA. Она исключает RSA и схемы дискретного логарифмирования на конечных полях, рассматриваемые в смежных темах.

Core questions

• Как геометрическое сложение точек на эллиптической кривой образует криптографическую группу?
• Почему дискретный логарифм на эллиптических кривых сложнее, чем его аналог на конечных полях, что позволяет использовать меньшие ключи?
• Как Диффи-Хеллман и цифровые подписи реализуются на эллиптических кривых?
• Что делает современные кривые, такие как Curve25519, более безопасными для реализации, чем старые кривые NIST?
• Почему уникальность одноразового кода для каждой подписи критически важна в ECDSA?

Key concepts

• групповой закон эллиптических кривых
• скалярное умножение
• проблема дискретного логарифмирования на эллиптических кривых
• ECDH
• ECDSA
• EdDSA и Ed25519
• Curve25519
• уязвимость повторного использования одноразового кода
• размер ключа по сравнению с RSA

Key theories

Проблема дискретного логарифмирования на эллиптических кривых

Предполагается, что для заданных точек P и Q = kP на кривой восстановление скаляра k требует полностью экспоненциальных усилий для хорошо выбранных кривых, поскольку атаки с использованием индексного исчисления, ослабляющие дискретные логарифмы на конечных полях, здесь неприменимы.

Меньшие ключи для равной безопасности

Поскольку лучшие атаки на дискретные логарифмы на эллиптических кривых являются общими алгоритмами квадратного корня, 256-битная эллиптическая кривая обеспечивает примерно 128-битную безопасность — сравнимую с 3072-битным RSA — что приводит к более быстрым операциям и меньшим ключам и подписям.

Mechanisms

Точки на эллиптической кривой над конечным полем образуют абелеву группу согласно геометрическому закону сложения; многократное сложение базовой точки P с самой собой k раз (скалярное умножение, kP) является эффективным, но восстановление k из kP представляет собой сложную задачу. ECDH реализует Диффи-Хеллмана путем обмена скалярными произведениями базовой точки; ECDSA и EdDSA генерируют подписи из скалярного значения для каждого сообщения (одноразового кода — nonce), повторное использование или предсказуемость которого приводит к утечке закрытого ключа, как показали несколько реальных взломов.

Clinical relevance

ECC является выбором по умолчанию для новых систем с открытым ключом: ECDHE обеспечивает прямую секретность при обмене ключами в TLS 1.3, Ed25519 подписывает SSH-ключи, обновления программного обеспечения и сертификаты, а Curve25519 обеспечивает безопасность Signal, WireGuard и современных мессенджеров. Ее малые ключи и быстрые операции делают ее хорошо подходящей для мобильных устройств, смарт-карт и ограниченного оборудования IoT.

Evidence & guidelines

ECDSA стандартизирован в FIPS 186, ECDH в NIST SP 800-56A, а EdDSA/Ed25519 в RFC 8032; Curve25519/X25519 в RFC 7748. Современная практика отдает предпочтение кривым Эдвардса и X25519 за их устойчивость к ошибкам реализации. Сбой ECDSA при повторном использовании одноразовых кодов (в частности, извлечение ключа Sony PlayStation 3 в 2010 году) является поучительным стандартным примером.

History

Нил Коблиц и Виктор Миллер независимо предложили использовать эллиптические кривые для криптографии в 1985-1987 годах. Внедрение изначально шло медленно из-за патентных и доверительных проблем, а также сложности кривых NIST, но ECC стала доминирующей в 2010-х годах, поскольку эффективность размера ключа стала более важной, а Curve25519 (2006) и Ed25519 Бернштейна предложили быстрые, устойчивые к ошибкам использования конструкции, широко используемые в настоящее время.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

Почему 256-битный ключ эллиптической кривой соответствует 3072-битному ключу RSA?

Лучшие известные атаки на дискретный логарифм на эллиптических кривых являются общими и занимают время, примерно равное квадратному корню из размера группы, тогда как факторизация и дискретные логарифмы на конечных полях имеют более быстрые субэкспоненциальные алгоритмы. Поэтому эллиптическим кривым требуется гораздо меньше бит для того же уровня безопасности.

Надежны ли эллиптические кривые NIST?

Стандартные P-кривые NIST широко используются и не считаются взломанными, но их необъяснимый выбор констант и сложность реализации привели многих к предпочтению Curve25519 и Ed25519, которые имеют прозрачные обоснования дизайна и легче безопасно реализуются за постоянное время.