Эллиптические кривые в криптографии: точки и ключи

Эллиптические кривые в криптографии дают способ строить открытые ключи из секретных чисел с помощью арифметики точек. Вычислить точку по известным и сравнительно легко; восстановить по и на правильно выбранной большой кривой считается трудной задачей для классического компьютера. Именно это направление вычисления лежит в основе многих схем обмена ключами и цифровой подписи.
Чтобы увидеть арифметику, выберите множитель в калькуляторе. Он использует очень маленькое поле: такой пример удобно проверить вручную, но защищать им данные нельзя.
От уравнения к конечному множеству точек
Одна из форм записи эллиптической кривой над простым конечным полем выглядит так:
Здесь - простое число, а координаты и коэффициенты берутся по модулю . Для невырожденной кривой необходимо . К точкам с координатами добавляют особый элемент , называемый точкой на бесконечности. Вместе они образуют конечную группу относительно специальной операции сложения. Формулы и ограничения этой модели приведены в RFC 6090.
Возьмём , и базовую точку . Проверка подстановкой даёт . Условие невырожденности тоже выполнено: .
На вещественной плоскости похожее уравнение часто изображают гладкой линией. Над конечным полем возможны только отдельные пары остатков, поэтому здесь рисунок состоит из точек. Это не эллипс. Связь с другими областями математики есть, но эллиптическая функция Вейерштрасса рассматривается над комплексными числами и решает другую задачу.
В калькуляторе каждая серая точка соответствует паре остатков, которая удовлетворяет уравнению. Если выбранный результат имеет координаты, он выделяется золотым. При последнем значении ползунка выделенной точки на плоскости нет: результатом становится особый элемент группы. Такой способ изображения помогает отличать множество допустимых точек от всех остальных пар остатков: большинство клеток координатной плоскости условию уравнения просто не удовлетворяет.
Как складывают точки
Над вещественными числами сложение удобно представить геометрически: прямая через и пересекает кривую ещё раз, а отражение этой третьей точки относительно горизонтальной оси даёт . При вместо секущей используют касательную. Над конечным полем остаются алгебраические формулы; проводить обычную прямую через точки на дискретной карте и измерять её линейкой нельзя.
Для разных точек и с сначала находят наклон:
а затем координаты суммы:
Степень означает обратный элемент по модулю, а не обычную дробь. Например, обратный к по модулю равен , потому что . При удвоении точки с наклон равен . Противоположная к точка - ; их сумма равна . Сам элемент играет роль нуля: .
Расчёт на маленькой кривой
Для сначала удвоим точку. Наклон . Поэтому , а . Итак, .
Теперь сложим и : наклон равен . Получаем . Продолжая по тем же правилам, находим , и . Подставьте в калькулятор и сверьте координаты с выделенной точкой.

Всего здесь 18 точек с координатами и ещё . Последовательность кратных проходит все 19 элементов группы: , а . На диаграмме точка не показана, поскольку у неё нет обычной пары координат. Ползунок позволяет проверить и этот крайний случай.
Проверить сложение можно двумя независимыми действиями. Сначала вычислите координаты по формулам с приведением каждого промежуточного результата по модулю. Затем подставьте полученную пару в исходное уравнение: обе стороны должны дать одинаковый остаток. Например, для точки с координатами девять и шестнадцать квадраты и кубы можно сокращать по модулю семнадцать уже в процессе вычисления. Такая проверка подтверждает принадлежность результата кривой, хотя сама по себе не доказывает, что сложение выполнено верно: для этого нужно сверить и промежуточные действия.
Открытый ключ и трудная обратная задача
Умножение означает повторное сложение точки с самой собой, а не умножение каждой координаты на . На практике используют быстрые алгоритмы, например последовательные удвоения и сложения: не нужно выполнять отдельных шагов. Секретное число служит закрытым ключом, а вычисленная точка - соответствующим открытым ключом в типичной схеме.
Обратная задача называется дискретным логарифмированием на эллиптической кривой: по и найти подходящее в подгруппе, порождённой . В игрушечном примере хватит перебрать 19 вариантов. В корректно выбранной большой группе такой перебор и известные общие классические методы требуют огромных ресурсов. Трудность зависит от параметров и размера порядка подгруппы, а не просто от того, что в названии есть слово «эллиптическая».
При сравнении ключей нельзя приравнивать количество бит ECC к такому же количеству бит RSA: лежащие в их основе задачи различаются. Размеры выбирают по требуемому уровню стойкости и действующим рекомендациям, а не по внешнему виду числа. В частности, маленький пример из статьи предназначен только для обучения.
Порядок точки определяет, сколько различных результатов можно получить при последовательном сложении. В больших системах выбирают базовую точку большой подходящей подгруппы; число всех точек кривой и порядок этой точки - разные характеристики, даже если в нашем учебном примере они совпадают. Уменьшение множителя по модулю порядка не меняет результат: например, , поскольку . Это помогает понять цикличность, но не делает произвольную кривую безопасной. Параметры также должны исключать известные слабые случаи, а сама группа должна быть выбрана согласно требованиям конкретной схемы. Проверка одной только длины числа не заменяет такую оценку.
Как работает ECDH
В эллиптическом варианте обмена Диффи - Хеллмана стороны заранее договариваются о параметрах и базовой точке . Алиса выбирает секрет и отправляет ; Боб выбирает секрет и отправляет . Затем Алиса вычисляет , а Боб - . По свойствам группы оба получают одну точку:
В нашем примере при и открытые точки равны и , а общий результат - . Подслушивающий видит параметры и открытые точки, но не секретные множители. Стойкость конкретного протокола опирается на соответствующие вычислительные предположения и корректную реализацию, а не на один лишь факт совпадения результатов.
На практике общий результат обрабатывают функцией вывода ключа вместе с контекстом протокола. Сам по себе ECDH не подтверждает личность собеседника: без аутентификации возможна подмена открытых ключей посредником. Проверка допустимости полученных ключей зависит от выбранной схемы и реализации; параметры и библиотеку следует брать из проверенных стандартов. Рекомендации NIST по согласованию ключей описаны в SP 800-56A.
В реальном обмене стороны обычно не показывают пользователю координаты общего результата. Протокол кодирует точки, согласует набор параметров и преобразует полученный материал в ключи для дальнейших операций. Важна и проверка контекста: например, ключи разных сеансов и направлений связи не следует считать взаимозаменяемыми только потому, что они получены одинаковым математическим приёмом. Эти детали задаёт конкретная спецификация протокола.
Подписи и ограничения стойкости
Кривые применяют и в цифровых подписях, например ECDSA: владелец закрытого ключа подписывает сообщение, а другие проверяют подпись открытым ключом. Это не шифрование: проверка подписи подтверждает связь подписи с ключом и целостность данных в рамках схемы, но не скрывает текст. В подписи важны корректное формирование одноразового значения и обработка сообщения; свойства криптографической хеш-функции также имеют значение.
Утечка секрета, слабая случайность, ошибки реализации и побочные каналы могут разрушить защиту даже при хорошей математике. Для обычных ECC-схем есть и долгосрочное ограничение: достаточно мощный отказоустойчивый квантовый компьютер с алгоритмом Шора угрожал бы задаче дискретного логарифма. Поэтому планируют переход к постквантовой криптографии; NIST отдельно описывает эту угрозу и подготовку к ней в материалах о постквантовой криптографии.
Практическая оценка безопасности поэтому начинается с вопроса о системе целиком. Надо знать, какая схема согласования или подписи применяется, как хранятся секретные данные и как проверяется открытый ключ другой стороны. Надёжная математическая задача не исправляет случайно раскрытый ключ. Для учебных расчётов полезно писать арифметику самостоятельно, но для рабочих приложений безопаснее использовать поддерживаемые библиотеки и принятые параметры, следуя документации выбранного протокола.
Частые ошибки
- Рисовать гладкую кривую поверх точек поля. Для вещественного рисунка это полезная интуиция, но в конечном поле координаты дискретны.
- Складывать координаты отдельно. Операция группы задаётся формулами кривой; обычно не является нужной суммой.
- Забывать про и обратные точки. В этих случаях формула с обратным к нулю знаменателем не применяется.
- Считать ECDH готовым шифрованием. Он согласует общий секрет; для защиты канала нужны вывод ключа, аутентификация и подходящий протокол.
FAQ
Почему эллиптическая кривая называется эллиптической, если это не эллипс?
Название исторически связано с эллиптическими интегралами. Современное определение кривой относится к алгебраической структуре, а не к форме эллипса на рисунке.
Что означает порядок точки?
Это наименьшее положительное число , для которого . В нашем примере порядок равен 19; кратные повторяются с этим периодом.
Можно ли использовать пример с модулем 17 для шифрования?
Нет. Возможных секретов слишком мало, и их легко перебрать. Реальные системы используют стандартизованные параметры и проверенные реализации.
Коротко
ECC строит операции с ключами на группе точек эллиптической кривой над конечным полем. Прямое вычисление эффективно, а обратное восстановление множителя на подходящих больших параметрах трудно для известных классических методов. Для безопасности необходимы также правильный протокол, генерация секретов и реализация.
Читайте также

Алгоритм Полига-Хеллмана: дискретный логарифм по частям
Как алгоритм Полига-Хеллмана решает задачу дискретного логарифма, когда порядок группы раскладывается на малые простые: разбиение по китайской теореме об остатках, шаги и сложность.

Протокол Шнорра: схема доказательства знания и подпись
Разбираем протокол Шнорра: интерактивное доказательство знания дискретного логарифма, тройку обязательство-вызов-ответ, проверку и переход к подписи через Фиата-Шамира.

Схема Эль-Гамаля: шифрование на дискретном логарифме
Схема Эль-Гамаля простыми словами: как работает асимметричное шифрование на дискретном логарифме, генерация ключей, формулы шифрования и расшифровки, пример с числами и цифровая подпись.

Схема подписи Эль-Гамаля: формулы и проверка подписи
Схема подписи Эль-Гамаля простыми словами: генерация ключей, формулы подписи и проверки, роль секретного k, связь с задачей дискретного логарифма и отличие от RSA и DSA.

Цифровая подпись ECDSA: как устроена и как проверяется
Разбираем цифровую подпись ECDSA на эллиптических кривых: как из приватного ключа и хэша рождается пара (r, s), как идет проверка и почему важен nonce k.

Алгоритм Диффи-Хеллмана: обмен ключами без передачи ключа
Как алгоритм Диффи-Хеллмана позволяет двум сторонам выработать общий секрет по открытому каналу: дискретный логарифм, протокол по шагам и защита от атаки посередине.