Return to Revisions

For the inverting the private key from public key, we have a well defined problem; the discrete logarithm problem; namely,

• given $P$ over a prime curve $E(\mathbb{F}_p)$ with the generator $G$, find $x$ such that $P= [x]G$ .

There are many works for speeding the discrete logarithm;

• Baby-step-Giant-Step which has $\mathcal{O}(\sqrt{p})$-time and $\mathcal{O}(\sqrt{p})$-space complexity.
• Pohlig–Hellman algorithm is useful especially if the order of the group is a smooth integer. This is based on the on the Floyd's cycle-finding algorithm. This is not the case for Secp255k1 since the order is prime.
• Pollard's kangaroo algorithm. This is a range based algorithm, given in a range $[a,b]$ it can find the discrete log in $\mathcal{O}(\sqrt{b-a})$-time.

Currently best achievement for Secp256k1 is performed with parallel Pollard's kangaroo. Best record can achieve 112-bit.

If you where to run the script and input a private key it will print the points calculated in the process of deriving the public key. Now take any of the calculated points (𝑅𝑥,𝑅𝑦) and indicate([2] or [1]) if it was derived using point doubling or point addition formula and I'll reverse the calculation the give you the value of 𝑄𝑥 and 𝑄𝑦 that was used in deriving the new points 𝑅𝑥 𝑅𝑦 (Deleted comment)

The obtaining the public key from the private key $k$ and base point $G$ is calculated as $P = [k]G$, this is scalar multiplication and means add $G$ itself $k$-times ( consider integer value of $k$).

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$

This is a very long method and we have better alternatives like double-and-add method^* ( if $k$ is integer than it takes roughly $\lfloor \log_2{k}\rfloor+1 $-time.)

let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
let temp = P # track doubled P val
for bit in bits: 
    if bit == 1:            
        res = res + temp # point add
    temp = temp + temp # double
return res

Now, this speeds up the calculation, and notice that it is depending on the value of bits of the $k$. Actually, this is not good since can cause side channel attacks. We use double-and-add method to demonstrate the problem. Notice two points;

1. There is always doubling
2. There can be point addition only if the current bit value of $k$ is 1.

So, for every bit of the key;

• we may return back to either only doubled case or added and doubled case.

• There is no test value for the reversing, i.e. how to determine that it was only double or add-and-double.

• So one needs to use a tree structure to follow the the cases. Can we see where is is going?

• For every step, we need to branch and this is exactly, two branch.

• In the final, the tree will have depth $n$ where $n$ is the number of bits of $k$, possible values on the tree and $2^n$ leaves.

• This is exactly same as the number of the bits of the key that needed to determine.

Now, one faces two problems;

1. One cannot store such tree since you need around $2^{256}$ storage for Secp256k1, and
2. One cannot compute such tree since you need reach $2^{256}$ computing power for Secp256k1. The best available one, the bitcoin miners can reach $2^{93}$ in a year, so you still need $2^{163}$ year to achieve this.

Well, on the other hand Pollard's $\rho$ has complexity around $\mathcal{O}(\sqrt{p})$, where $p$ is the size of the group generated by the $G$. This is far better than above.

_{^*Similar arguments can make for the Montgomery and Joyce ladder, too.}