Return to Revisions

For the inverse you need to solve the discrete logarithm problem; namely, given $P = [x]G$ over a prime curve $E$ wit the generator $G$, find $x$.

There are many works for speeding the discrete logarithm, currently best achievement are performed with Pollard's Rho and this is based on the on the Floyd's cycle-finding algorithm 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 𝑅𝑥 𝑅𝑦

The obtaining the private key $k$ from base point $G$ is calculated as $P = [k]G$ that is scalar multiplication and means add $G$ itself $k$-times ( consider integer value of $k$). This is a long method and we perform double-and-add method^*;

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

There is always doubling, however, there can be point addition only if the current bit value of $k$ is 1. So, for every bit of the key, there is no test value for the reversing, so you need to use a tree structure to follow the the cases. Do you see where is is going? In the final you will have $2^{n}$ where $n$ is the number of bits of $k$, possible values on the tree.

1. You cannot store such tree since you need around $2^{256}$ storage
2. You cannot compute such tree since you need reach $2^{256}$ computing power.

Well, on the other hand Pollard's $\rho$ has complexity around $\mathcal{O}\sqrt{p}$. which is far better than above.

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