2
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.