Score:2 Crypto

# Is it possible to calculate the modular inverse of a secp256k1 public key? I know that it wouldn't be possible to use the extended Euclidean algorithm, since it would require the ability to divide a public key and calculate the remainder. 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? 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 am not especially well educated in mathematics or cryptography, but I find it interesting, so maybe I just don't know the correct terminology to research it myself.

Score:3 Crypto 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?

Actually, given a public key $$H$$, it is easy to find the smallest integer $$x > 0$$ such that $$xH = 1$$. For secp256k1 (and if $$H$$ isn't the neutral element), then $$x = 115792089237316195423570985008687907852837564279074904382605163141518161494337$$. This is true no matter which point $$H$$ is; all points on that curve (other than the neutral element) have that order.

However, that's not what we usually mean if we refer to 'the mod inverse'; that sounds more like "given $$xG$$, find the point $$x^{-1}G$$", which is known to be equivalent to the CDH problem (which we hope is hard)

Score:1 Crypto 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.  