EssayAI
Блог
Блог
Математика и алгоритмы

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

8 ноября 2026Время чтения: 8 минут
#эллиптические кривые#криптография#конечное поле#дискретный логарифм#ECDH
Эллиптические кривые в криптографии: точки и ключи

Эллиптические кривые в криптографии дают способ строить открытые ключи из секретных чисел с помощью арифметики точек. Вычислить точку Q=kGQ=kG по известным kk и GG сравнительно легко; восстановить kk по GG и QQ на правильно выбранной большой кривой считается трудной задачей для классического компьютера. Именно это направление вычисления лежит в основе многих схем обмена ключами и цифровой подписи.

Чтобы увидеть арифметику, выберите множитель в калькуляторе. Он использует очень маленькое поле: такой пример удобно проверить вручную, но защищать им данные нельзя.

От уравнения к конечному множеству точек

Одна из форм записи эллиптической кривой над простым конечным полем Fp\mathbb F_p выглядит так:

y2≡x3+ax+b(modp).y^2 \equiv x^3+ax+b \pmod p.

Здесь p>3p>3 - простое число, а координаты и коэффициенты берутся по модулю pp. Для невырожденной кривой необходимо 4a3+27b2≢0(modp)4a^3+27b^2\not\equiv0\pmod p. К точкам с координатами добавляют особый элемент OO, называемый точкой на бесконечности. Вместе они образуют конечную группу относительно специальной операции сложения. Формулы и ограничения этой модели приведены в RFC 6090.

Возьмём p=17p=17, a=b=2a=b=2 и базовую точку G=(5,1)G=(5,1). Проверка подстановкой даёт 12≡53+2⋅5+2≡1(mod17)1^2\equiv5^3+2\cdot5+2\equiv1\pmod{17}. Условие невырожденности тоже выполнено: 4⋅23+27⋅22=140≡4(mod17)4\cdot2^3+27\cdot2^2=140\equiv4\pmod{17}.

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

На карте конечного поля выделены последовательные кратные точки G от 1G до 6G и обратно: прибавление одной и той же точки переводит результат между дискретными координатами.

В калькуляторе каждая серая точка соответствует паре остатков, которая удовлетворяет уравнению. Если выбранный результат имеет координаты, он выделяется золотым. При последнем значении ползунка выделенной точки на плоскости нет: результатом становится особый элемент группы. Такой способ изображения помогает отличать множество допустимых точек от всех остальных пар остатков: большинство клеток координатной плоскости условию уравнения просто не удовлетворяет.

Как складывают точки

Над вещественными числами сложение удобно представить геометрически: прямая через PP и QQ пересекает кривую ещё раз, а отражение этой третьей точки относительно горизонтальной оси даёт P+QP+Q. При P=QP=Q вместо секущей используют касательную. Над конечным полем остаются алгебраические формулы; проводить обычную прямую через точки на дискретной карте и измерять её линейкой нельзя.

Для разных точек P=(x1,y1)P=(x_1,y_1) и Q=(x2,y2)Q=(x_2,y_2) с x1≠x2x_1\ne x_2 сначала находят наклон:

λ=(y2−y1)(x2−x1)−1(modp),\lambda=(y_2-y_1)(x_2-x_1)^{-1}\pmod p,

а затем координаты суммы:

x3=λ2−x1−x2,y3=λ(x1−x3)−y1(modp).x_3=\lambda^2-x_1-x_2,\qquad y_3=\lambda(x_1-x_3)-y_1\pmod p.

Степень −1-1 означает обратный элемент по модулю, а не обычную дробь. Например, обратный к 22 по модулю 1717 равен 99, потому что 2⋅9≡12\cdot9\equiv1. При удвоении точки с y1≠0y_1\ne0 наклон равен (3x12+a)(2y1)−1(3x_1^2+a)(2y_1)^{-1}. Противоположная к (x,y)(x,y) точка - (x,−y mod p)(x,-y\bmod p); их сумма равна OO. Сам элемент OO играет роль нуля: P+O=PP+O=P.

Расчёт на маленькой кривой

Для G=(5,1)G=(5,1) сначала удвоим точку. Наклон λ=(3⋅52+2)⋅9≡13(mod17)\lambda=(3\cdot5^2+2)\cdot9\equiv13\pmod{17}. Поэтому x3≡132−5−5≡6x_3\equiv13^2-5-5\equiv6, а y3≡13(5−6)−1≡3y_3\equiv13(5-6)-1\equiv3. Итак, 2G=(6,3)2G=(6,3).

Теперь сложим GG и 2G2G: наклон равен (3−1)(6−5)−1=2(3-1)(6-5)^{-1}=2. Получаем 3G=(10,6)3G=(10,6). Продолжая по тем же правилам, находим 4G=(3,1)4G=(3,1), 5G=(9,16)5G=(9,16) и 6G=(16,13)6G=(16,13). Подставьте k=5k=5 в калькулятор и сверьте координаты с выделенной точкой.

Точки кривой по модулю 17: выделена точка 5G с координатами 9 и 16
Точки кривой по модулю 17: выделена точка 5G с координатами 9 и 16

Всего здесь 18 точек с координатами и ещё OO. Последовательность кратных GG проходит все 19 элементов группы: 18G=(5,16)=−G18G=(5,16)=-G, а 19G=O19G=O. На диаграмме точка OO не показана, поскольку у неё нет обычной пары координат. Ползунок позволяет проверить и этот крайний случай.

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

Открытый ключ и трудная обратная задача

Умножение kGkG означает повторное сложение точки с самой собой, а не умножение каждой координаты на kk. На практике используют быстрые алгоритмы, например последовательные удвоения и сложения: не нужно выполнять kk отдельных шагов. Секретное число kk служит закрытым ключом, а вычисленная точка Q=kGQ=kG - соответствующим открытым ключом в типичной схеме.

Обратная задача называется дискретным логарифмированием на эллиптической кривой: по GG и QQ найти подходящее kk в подгруппе, порождённой GG. В игрушечном примере хватит перебрать 19 вариантов. В корректно выбранной большой группе такой перебор и известные общие классические методы требуют огромных ресурсов. Трудность зависит от параметров и размера порядка подгруппы, а не просто от того, что в названии есть слово «эллиптическая».

При сравнении ключей нельзя приравнивать количество бит ECC к такому же количеству бит RSA: лежащие в их основе задачи различаются. Размеры выбирают по требуемому уровню стойкости и действующим рекомендациям, а не по внешнему виду числа. В частности, маленький пример из статьи предназначен только для обучения.

Порядок точки определяет, сколько различных результатов можно получить при последовательном сложении. В больших системах выбирают базовую точку большой подходящей подгруппы; число всех точек кривой и порядок этой точки - разные характеристики, даже если в нашем учебном примере они совпадают. Уменьшение множителя по модулю порядка не меняет результат: например, (19+5)G=5G(19+5)G=5G, поскольку 19G=O19G=O. Это помогает понять цикличность, но не делает произвольную кривую безопасной. Параметры также должны исключать известные слабые случаи, а сама группа должна быть выбрана согласно требованиям конкретной схемы. Проверка одной только длины числа pp не заменяет такую оценку.

Как работает ECDH

В эллиптическом варианте обмена Диффи - Хеллмана стороны заранее договариваются о параметрах и базовой точке GG. Алиса выбирает секрет aa и отправляет A=aGA=aG; Боб выбирает секрет bb и отправляет B=bGB=bG. Затем Алиса вычисляет aBaB, а Боб - bAbA. По свойствам группы оба получают одну точку:

aB=a(bG)=abG=b(aG)=bA.aB=a(bG)=abG=b(aG)=bA.

В нашем примере при a=2a=2 и b=3b=3 открытые точки равны (6,3)(6,3) и (10,6)(10,6), а общий результат - 6G=(16,13)6G=(16,13). Подслушивающий видит параметры и открытые точки, но не секретные множители. Стойкость конкретного протокола опирается на соответствующие вычислительные предположения и корректную реализацию, а не на один лишь факт совпадения результатов.

На практике общий результат обрабатывают функцией вывода ключа вместе с контекстом протокола. Сам по себе ECDH не подтверждает личность собеседника: без аутентификации возможна подмена открытых ключей посредником. Проверка допустимости полученных ключей зависит от выбранной схемы и реализации; параметры и библиотеку следует брать из проверенных стандартов. Рекомендации NIST по согласованию ключей описаны в SP 800-56A.

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

Подписи и ограничения стойкости

Кривые применяют и в цифровых подписях, например ECDSA: владелец закрытого ключа подписывает сообщение, а другие проверяют подпись открытым ключом. Это не шифрование: проверка подписи подтверждает связь подписи с ключом и целостность данных в рамках схемы, но не скрывает текст. В подписи важны корректное формирование одноразового значения и обработка сообщения; свойства криптографической хеш-функции также имеют значение.

Утечка секрета, слабая случайность, ошибки реализации и побочные каналы могут разрушить защиту даже при хорошей математике. Для обычных ECC-схем есть и долгосрочное ограничение: достаточно мощный отказоустойчивый квантовый компьютер с алгоритмом Шора угрожал бы задаче дискретного логарифма. Поэтому планируют переход к постквантовой криптографии; NIST отдельно описывает эту угрозу и подготовку к ней в материалах о постквантовой криптографии.

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

Частые ошибки

  • Рисовать гладкую кривую поверх точек поля. Для вещественного рисунка это полезная интуиция, но в конечном поле координаты дискретны.
  • Складывать координаты отдельно. Операция группы задаётся формулами кривой; обычно (x1+x2,y1+y2)(x_1+x_2,y_1+y_2) не является нужной суммой.
  • Забывать про OO и обратные точки. В этих случаях формула с обратным к нулю знаменателем не применяется.
  • Считать ECDH готовым шифрованием. Он согласует общий секрет; для защиты канала нужны вывод ключа, аутентификация и подходящий протокол.

FAQ

Почему эллиптическая кривая называется эллиптической, если это не эллипс?

Название исторически связано с эллиптическими интегралами. Современное определение кривой относится к алгебраической структуре, а не к форме эллипса на рисунке.

Что означает порядок точки?

Это наименьшее положительное число nn, для которого nG=OnG=O. В нашем примере порядок GG равен 19; кратные повторяются с этим периодом.

Можно ли использовать пример с модулем 17 для шифрования?

Нет. Возможных секретов слишком мало, и их легко перебрать. Реальные системы используют стандартизованные параметры и проверенные реализации.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Алгоритм Полига-Хеллмана: дискретный логарифм по частям

Алгоритм Полига-Хеллмана: дискретный логарифм по частям

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

20 июня 20268 минут
Протокол Шнорра: схема доказательства знания и подпись

Протокол Шнорра: схема доказательства знания и подпись

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

19 июня 20268 минут
Схема Эль-Гамаля: шифрование на дискретном логарифме

Схема Эль-Гамаля: шифрование на дискретном логарифме

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

19 июня 20268 минут
Схема подписи Эль-Гамаля: формулы и проверка подписи

Схема подписи Эль-Гамаля: формулы и проверка подписи

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

19 июня 20268 минут
Цифровая подпись ECDSA: как устроена и как проверяется

Цифровая подпись ECDSA: как устроена и как проверяется

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

25 мая 20268 минут
Алгоритм Диффи-Хеллмана: обмен ключами без передачи ключа

Алгоритм Диффи-Хеллмана: обмен ключами без передачи ключа

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

6 мая 20267 минут