3
$\begingroup$

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$?

$\endgroup$
2
  • 1
    $\begingroup$ $G$ is publicly known so there is no need to calculate that. Do you want to check that given a public key is belongs to a private key? then check with $key_{pub} = [key_{private}]G$ $\endgroup$
    – kelalaka
    Dec 4, 2020 at 11:04
  • 1
    $\begingroup$ @kelalaka Sure, I know that G is known and I know both public and private key. This is more of a theoretical exercise. Can a calculate G back from publickey and privatkey? $\endgroup$ Dec 4, 2020 at 11:19

2 Answers 2

4
$\begingroup$

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}}. $$

$\endgroup$
0
3
$\begingroup$

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$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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