This is a bit extended answer;
I was wondering if there were any other ways of calculating the modular multiplicative inverse of a point on an elliptic curve (like secp256k1)? Or perhaps a reason why it is provably impossible?
The bitcoin community usually calls the usual scalar multiplication as multiplication1. What we define as scalar multiplication as
$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$ in other words, adding a point itself $k$ times.
There is already a problem defined for this ( using EC version $r$ is the order of the base element $G$, the curve is prime order,and $E(K)$ is the set of the point of the curve);
Definitions;
- CDH : given a triple $(G,[a]G,[b])$ find $[ab]G$.
- Inverse-DH : given a pair $(G, [a]G) \in E(K) - \{\mathcal{O}\}$ of elements of prime order $r$ in $E(K)$ to compute $[a^{-1}]G$.
- Square-DH: The computational problem Square-DH
is: given $(G, [a]G )$ where $G \in E(K)$ has prime order $r$ to compute $[a^2]G$.
Reductions;
$\text{Inverse-DH} \leq_R \text{CDH}$.
Let's assume we have an oracle $O$ that solve $\text{CDH}$. We are given $(G,[a]G)$ as the $\text{Inverse-DH}$ instance and we want to find $P = [a]G$. Then we have $$G = [a^{-1}]P = [a^{-1}a]G = G$$
Now, call the oracle $O$ with $O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P) $ and the oracle outputs $[a^{-2}]P$. Replace $P$ to get $$[a^{-2}]P = [a^{-2}a]G = [a^{-1}]G$$ This shows the reduction.
$\text{Square-DH} \leq_R \text{Inverse-DH}$.
Let's assume $O$ be an oracle that solves $\text{Inverse-DH}$ and let $(G, P = [a]G )$ be given. If $P = \mathcal{O}$ then return $\mathcal{O}$ else $$O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P.$$ This shows the reduction.
So we have $\text{Square-DH} \leq_R \text{Inverse-DH} \leq_R \text{CDH}$. If we can show that $\text{CDH} \leq_R \text{Square-DH}$ then we will have the equivalence.
$\text{CDH} \leq_R \text{Square-DH}$
let $O$ be an oracle to solve $\text{Square-DH}$ and we are given $(G,[a]G, [b]G)$ as a $\text{CDH}$ instance.
Call $O$ two times with $O(G,[a]G)$ and $O(G,[b]G)$ to get $P= [a^2]G$ and $Q= [b^2]G$, respectively.
Now one more call $O(G, P+Q) = O(G, [a+b]G)$ and get $$R = [(a+b)^2]G = [a^2+2ab+b^2]G.$$
Now finally compute $$[2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ab]G$$ This shows the reduction.
Therefore we have the equivalence. So if the $\text{CDH}$ is hard then $\text{Inverse-DH}$ is hard, too. Well, we hope this is for non-quantum adversaries.
Is there a way (other than brute force) to find an integer that results in 1 when the public key is multiplied by that integer?
I can read this in two ways;
$1$ is the identity of the curve we write $\mathcal{O}$, then we have the identity $[r]P = \mathcal{O}$ for every element of a prime curve of order $r$. This is the definition of order of an element in the group theory.
$1$ as the $[a\cdot a^{-1}]G = [\color{red}{1}]G = G$ then this is the $\text{Inverse-DH}$ as we discussed.
1Well, one can (define|call) the point addition as point multiplication, however, the addition is historical and all major Elliptic curve books use point addition; Over the complex numbers, any elliptic curve can be realized as $\mathbb C/\Gamma$
for some lattice $\Gamma$. In this case, addition simply comes from standard addition of complex numbers.
