Преамбула
Одна сторона безопасности ЭЦДСА зависит от безопасности дискретного логарифма используемой эллиптической кривой (назовем ее $Е$). Эллиптические кривые образуют аддитивную алгебраическую группу порядка $n$. Если группа, образованная используемой кривой, является общей группой, то наилучшая классическая атака — это $\mathcal{O}(\sqrt{2^n})$ - Ро Полларда.
ЭЦДСА
Закрытый ключ $к$ вычисляется как случайное целое число в интервале $[1,n-1]$ и все время держали в секрете. Обратите внимание, что закрытый ключ $к$ целое число, а не точка на кривой $Е$.
Открытый ключ $P$, с другой стороны, рассчитывается как точка $p = [k]G$ куда $G$ является базовой точкой кривой, определенной в стандартах и операции $[k]G$ называется скалярным умножением, определяемым как;
$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$
Это не следует путать с умножением, нет, это то, что мы пишем, чтобы упростить $к$-кратные дополнения.
$[к]П$ можно вычислить по крайней мере с помощью алгоритма двойного сложения, чтобы ускорить вычисление в $\mathcal{O}(\log k)$-время.
Точки
Теперь, как мы видим, даже $к=0$ не является проблемой в ECDSA, так как это недопустимое значение для $к$.
Если дискретный журнал легко
Если дискретный журнал легок на этой кривой, это находит $к$ данный $[k]G$, то каждое значение легко выводится.
Если кривая закрыта другой базовой точкой $Ч$, то есть кто-то может решить дискретный логарифм по основанию $Ч$ в группе кривых. Затем они могут использовать это, чтобы решить Длог на базе. $G$ очень легко;
- Они рассчитывают $G = [t]H$ за $t \in [1,n-1]$ только однажды
- Они решают $P =[k\cdot a]G$ на базу $Ч$ за $а \in [0,n-1]$. Один раз $ка$ находится $к$ можно рассчитать как $k = a \cdot k \cdot a^{-1}$ так как мы знаем $а$ и $a^{-1} \cdot a = 1 \bmod n$.
Если дискретный журнал не прост
В этом случае некоторые из них можно вычислить до их максимальной мощности. Предположим, вы можете использовать суперкомпьютер Summit и у вас есть возможность вычислять $2^{70}$ удвоить и добавить для заданного числа $t$. Они рассчитывают и настраивают хеш-таблицу для быстрого запроса существования дискретного журнала в диапазоне $[1,2^{70}]$. Пробег в течение одного года, и необходимое хранилище составляет $2^{70}*256*3$-бит (~ 147574 петабайт). Что ж, хранение — это одна из проблем, а другая — хэш-таблица. $\mathcal{О}(1)$ больше. Предположим, что вы решили эту задачу, тогда какова вероятность того, что вы сможете найти данный закрытый ключ из открытого ключа. Точное значение зависит от группы кривых, предположим, что используется группа кривых размера $2^{256}$ для защиты от стандартных атак Dlog. Вероятность попадания равна $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ Это даже имеет гораздо меньшую вероятность, чем $\dfrac{1}{100}$, поэтому мы говорим, что это не произойдет!
Вместо последовательного случайного выбора $t$с изменить результат, НЕТ!
Специальное примечание 1:0x0000...0000 это обычная кодировка $\mathcal{О}(п)$ поскольку $(0,0)$ находится не на кривой. Это не принимается в качестве действительного открытого ключа в СЕК 1 Вер. 2.0 раздел 3.2.2.1.
Специальное примечание 2: некоторые эллиптические кривые являются простыми кривыми, это означает, что группа, которую они образуют, имеет простой порядок. В этом случае каждый элемент является генератором, кроме элемента идентичности. Если порядок не простой, как в кривой 25519, то у нас есть кофактор $h = \#E(K)/n$ куда $n$ — наибольшее простое число, делящее порядок кривой. Если используется полная группа, легко заметить мелкие элементы порядка, просто отметьте $[o]P = \mathcal{O}$ или нет, где $о$ это небольшой заказ. Для Curve25519 $о$ значения $2,4,$ и $8$. Это не проблема безопасности, поскольку законные пользователи всегда выбирают $k \экв 0 \pmod 8$.
