Это немного расширенный ответ;
Мне было интересно, есть ли другие способы вычисления модульной мультипликативной инверсии точки на эллиптической кривой (например, secp256k1)? Или, возможно, причина, по которой это доказуемо невозможно?
Биткойн-сообщество обычно называет обычное скалярное умножение умножением1. То, что мы определяем как скалярное умножение, как
$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$ другими словами, добавление самой точки $к$ раз.
Для этого уже определена проблема (с использованием версии EC $г$ порядок базового элемента $G$, кривая имеет простой порядок, и $Е(К)$ — множество точек кривой);
Определения;
- CDH : дается тройка $(G,[a]G,[b])$ найти $[аб]G$.
- Обратный DH : дана пара $(G, [a]G) \in E(K) - \{\mathcal{O}\}$ элементов простого порядка $г$ в $Е(К)$ вычислить $[a^{-1}]G$.
- Square-DH: Вычислительная задача Square-DH
дано $(G, [a]G )$ куда $G \in E(K)$ имеет простой порядок $г$ вычислить $[а^2]G$.
Скидки;
$\text{Обратный-DH} \leq_R \text{CDH}$.
Предположим, у нас есть оракул $О$ которые решают $\text{CDH}$. Нам дано $(G,[a]G)$ как $\text{Обратный-DH}$ экземпляр, и мы хотим найти $P = [a]G$. Тогда у нас есть $$G = [a^{-1}]P = [a^{-1}a]G = G$$
Теперь вызовите оракула $О$ с $O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P) $ и оракул выдает $[a^{-2}]P$. Заменять $P$ получить $$[a^{-2}]P = [a^{-2}a]G = [a^{-1}]G$$ Это показывает сокращение.
$\text{Квадратный-DH} \leq_R \text{Обратный-DH}$.
Предположим $О$ быть оракулом, который решает $\text{Обратный-DH}$ и разреши $(G, P = [a]G )$ быть данным. Если $P = \mathcal{O}$ затем вернуться $\mathcal{O}$ еще $$O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P.$$ Это показывает сокращение.
Итак, у нас есть $\text{Квадратный-DH} \leq_R \text{Обратный-DH} \leq_R \text{CDH}$. Если мы сможем показать, что $\text{CDH} \leq_R \text{Квадрат-DH}$ тогда мы будем иметь эквивалентность.
$\text{CDH} \leq_R \text{Квадрат-DH}$
позволять $О$ быть оракулом, чтобы решить $\text{Квадрат-DH}$ и нам дано $(G,[a]G, [b]G)$ как $\text{CDH}$ пример.
Вызов $О$ два раза с $O(G,[a]G)$ и $O(G,[b]G)$ получить $P= [a^2]G$ и $Q= [b^2]G$, соответственно.
Теперь еще один звонок $O(G, P+Q) = O(G, [a+b]G)$ и получить $$R = [(a+b)^2]G = [a^2+2ab+b^2]G.$$
Теперь, наконец, вычислить $$[2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ аб]G$$ Это показывает сокращение.
Следовательно, у нас есть эквивалентность. Итак, если $\text{CDH}$ тяжело тогда $\text{Обратный-DH}$ тоже тяжело. Что ж, мы надеемся, что это для неквантовых противников.
Есть ли способ (кроме грубой силы) найти целое число, которое приводит к 1, когда открытый ключ умножается на это целое число?
Я могу прочитать это двумя способами;
$1$ это тождество кривой, которую мы пишем $\mathcal{O}$, то имеем тождество $[r]P = \mathcal{O}$ для каждого элемента простой кривой порядка $г$. Это определение порядок элемента в теории групп.
$1$ как $[a\cdot a^{-1}]G = [\color{red}{1}]G = G$ тогда это $\text{Обратный-DH}$ как мы уже обсуждали.
1Что ж, можно (определить | назвать) сложение точек как умножение точек, однако сложение является историческим, и все основные книги по эллиптическим кривым используют сложение точек; Над комплексными числами любую эллиптическую кривую можно представить как $\mathbb C/\Гамма$
для некоторой решетки $\Гамма$. В этом случае сложение просто происходит от стандартного сложения комплексных чисел.
