How to find the base point given public and private key and EC parameters except the base point

Question

I'm working on the curve secp256k1 and I've private key $k$ and public key $P = [k]G$. I look for solutions to the following problems;

• What is the inverse of a scalar $k$ in ECC?

• If I'm only missing $G$ but know all parameters of the curve can I find $G$ from $k$ and $P$?

Answer 1

Most standardized curves has a base point $G$ of prime order $q$ so computing the inverse of $k$ (the private key) modulo $q$ can be easily done as $$ k_{\text{inv}} = k^{p-2} \bmod q, $$ thanks to Fermat's Little Theorem since $$ k_{\text{inv}}\times k \equiv k^{p-1} \equiv 1 \pmod{q} $$

In the case the order is a composite integer $n$, then Euclid Extended algorithm is a good way to find it.

In your problem you have a public point $P_{\text{pub}}$ such that $$ P_{\text{pub}} = [k]G, $$ and you only know $k$ and $P_{\text{pub}}$. To find $G$, use of the above algorithm (if the order of $G$ is known) to find $k_{\text{inv}}$ and we have $$ G = [k_{\text{inv}}] P_{\text{pub}}. $$

Answer 2

In ECC, the private key $k$ is a scalar and a public key is $[k]G$, this is scalar multiplication defined as

\begin{align} [k]:& E \to E\\ &P\mapsto [k]G=\underbrace{G+G+\cdots+G}_{\text{$k$ times}}.\end{align}

As we can see, it is a short definition of multiple additions of the same element. Since in ECC we work in finite fields $\mathbf{F}$, the elements of the curve are finite and actually forms an abelian group with an identity $\mathcal{O}$, this can be the point of infinity or not, depending on the curve definition. If the order of the point $G$ is $t$ ( the $t$ can be equal to the order of the EC group or a divisor of it, i.e. $ord(G)\mid \#|E(\mathbf{F})|$) then

$$\underbrace{G+G+\cdots+G}_{\text{$t$ times}} = [t]G= \mathcal{O}$$

Inverse of private key

Now if you want to the inverse of $k^{-1}$ it is just $t-k$. You can see this from this

$$[k]G + [t-k]G = [k+t-k]G = [t]G = \mathcal{O}$$

Finding the base point only with private and public key

The question has little meaning since the base point comes with a standard and it is publicly known for all parties. To able to calculate any arithmetic, you already must know the Elliptic curve construction parameters.

let's consider you all know but the basepoint $G$ and formalizing ;

find $x$ such that $[x]P = G$ where $P = [k]G$ given $P$ and $k$.

We will use this identity on the scalars;

$$[k]([a]P) = [ak]P$$

$$[k]([a]P)=\underbrace{ \underbrace{P+P+\cdots+P}_{\text{$a$ times}} + \cdots + \underbrace{P+P+\cdots+P}_{\text{$a$ times}} }_{ \text{$k$ times}}$$

Since the scalars are working a modulus, i.e.

$$[k]P = [k \bmod t]P$$ where $t$ was the order of the $G$. So, as given by the corspini's answer if the multiplicative inverse of $k$ over the group of order $t$ then we can use it to find $G$. In ECC, we use usually use prime order subgroups so inverses exist in them.

Let $k'\cdot k \equiv 1 \bmod t$ and thake $P = [k]G$ now add $k'$ times

$$[k' \bmod t]P = [k'([k]]G) = [k' \cdot k \bmod t]G = G$$