Как трудность задачи дискретного логарифма связана с криптографией на эллиптических кривых?

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

$$\begin{выравнивание*} b^x\equiv r&\pmod p\quad(1)\end{align*}$$ это найти $х$ (если существует) для данного $ г, б $ как целые числа, меньшие простого числа $р$.

Я прав до сих пор? пожалуйста, поправьте меня, если я что-то неправильно понимаю.

В криптографии на эллиптических кривых говорят, что в $P=а\умножить на G$ мы не можем вычислить $а$ зная $P$ и $G$ потому что проблема дискретного логарифма трудно решить. Я не понимаю, как это связано с уравнением 1. Я имею в виду, что в обеих задачах схожа только терминология?

Чтобы прояснить мой вопрос, давайте представим, что гений из будущих поколений может, наконец, представить решение уравнения 1, которое делается в приемлемое время, используя среднюю аппаратную настройку того времени. Алгоритм, который они предлагают, способен найти $х$ (если существует) для любого заданного простого $р$ и любой данный $ г, б $. Теперь я хочу знать, представляет ли это изобретение угрозу безопасности криптографии на основе эллиптических кривых? Другими словами, поможет ли знание такого алгоритма в извлечении $а$ от $P$?

Если да, пожалуйста, объясните, как определяется это отношение и каков математический поток, с помощью которого мы можем вычислить $а$ от $P$, который, я думаю, должен будет пройти через решение сравнения, аналогичного уравнению 1.

Если нет, скажите, чем отличается сложность задачи дискретного логарифмирования на эллиптических кривых от сложности уравнения 1 и почему здесь используется эта терминология.

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

Группы могут быть записаны с мультипликативной записью (как и с мультипликативной группой по модулю $р$), так что групповая операция записывается как $*$, $\раз$, $\cdot$ или просто неявно. Во всех этих случаях мы принимаем естественные обозначения для многократного использования групповой операции с одним элементом, т.е. $b^2:=b*b$ и подобные обобщения. Таким образом, общая проблема дискретного логарифмирования для циклической группы $С$ записанный в мультипликативной нотации, сгенерированный $b$ дано $ г \ в C $ найти целое число $х$ такой, что $ б ^ х = г $.

Другие группы записываются с помощью аддитивных обозначений (это обычно зарезервировано для абелевых групп, включая группы эллиптических кривых). В этом случае групповая операция обозначается $+$ (но не следует читать как сложение в обычном смысле) и снова существует естественное обозначение для многократного использования групповой операции с одиночными элементами, т.е. $2G=G+G$ и так далее. При такой записи задача дискретного логарифмирования для циклической группы $С$ Сгенерированно с помощью $G$ становится: дано $P\в C$ найти целое число $х$ такой, что $xG=P$.

Считается, что нет четкого перевода между задачами дискретного логарифмирования в разных группах. Есть группы, в которых проблема дискретного логарифмирования решается легко (например, аддитивные группы по модулю $р$, мультипликативные группы по модулю $2^n$ и даже (в квазиполиномиальном смысле) мультипликативная группа $GF(2^n)$).

Для частного случая мультипликативных групп по модулю $р$ самая известная (классическая) атака — это сито числового поля который решает задачу за субэкспоненциальное время. Эта атака может быть применена только к очень редким классам эллиптических кривых (Кривые MOV), а наиболее известными общими атаками на эллиптические кривые являются атаки «квадратичного корня», которые применяются ко всем группам.

Обратите внимание, что все задачи дискретного логарифмирования могут быть решены за (квантовое) полиномиальное время с помощью Алгоритм Шора.

Позволять $Е$ быть эллиптической кривой, заданной над конечным полем $\mathbb{F}_p$:

$$E : y^2 = x^3 + Ax + B \text{ с } A, B \in \mathbb{F}_p$$

Позволять $P$ и $Т$ быть точками в $E(\mathbb{F}_p)$. Найти целое число $а$ так что

$$ P =aG$$

Это проблема для эллиптических кривых. Задачу можно переписать с помощью логарифма:

$$ а = log_G (P)$$

Вы можете сравнить это со «стандартным» дискретным логарифмом:

$$ b^x \equiv r \mod p \Rightarrow x = log_b(r)$$

Теперь вы видите сходство?

Примечание: Ваш гений должен иметь эффективный способ сломать его, а не потому, что у него неограниченные ресурсы. И да, если у вас есть эффективный способ разбить дискретный логарифм, вы можете использовать его вариант для разбиения эллиптических кривых. Суть криптографии на эллиптических кривых заключается в том, что вычисления выполняются быстрее, чем для «стандартных» систем дискретного логарифмирования (у ecc есть много других плюсов).