Implementing Floor Division on secp256k1 Elliptic Curve in Python

Question

I understand that the // operator is used for floor division in regular arithmetic

result = 7 // 3  # This will result in 2

but how can I adapt this to work with the specific mathematical operations involved in secp256k1?

Could someone provide guidance or a code snippet illustrating how to perform floor division on secp256k1 elliptic curve in Python?

Answer 1

Let, us have a public base point $G$ on the curve $E$, and let us have a public key $P$ with a related secret key $k$ with $P = [k]G$.

Discrete Logarithm

Finding $k$ given $G$ and $P$ and curve parameters is called the Discrete Logarithm Problem (DLP) on the curve. In general, if there is no special structure of the curve this is a hard problem and the best generic algorithms (Pollard's Rho) have $\sqrt{n}$ cost where $n$ is the number of the points on the curve.

Division Floor Problem (DFP)

Let's call this problem a Division Floor Problem (DFPx) that is given $[k]$ returns $[\lfloor k/x \rfloor]G$.

Oracles

We use Oracle/machine/program as a tool to investigate relations with other problems.

DLP $\implies$ DFP

If we have an oracle to solve discrete logarithm then we solve the DFP problem since we can get $k$ and simply use // and scalar multiplication to return the desired value. So, DLP is at least as hard as DFP.

DFP2 $\implies$ DLP :

Now, Let us have a DFP2 oracle given $[k]G$ that returns $[\lfloor k/2 \rfloor]G$. Now, we can use this oracle to break the Discrete Logarithms as follows

1. extracted = 0, step = 0

2. Ask oracle $P = [k]G$. Oracle returns $P' = [\lfloor k/2 \rfloor]G$

3. if $[2]P' = [k]G$ then we know that the last bit of $k$ is $0$ else the last bit of $k$ is $1$

4. $\text{extracted} | (\text{last bit} \ll \text{step})$

5. Let $step = step + 1$

6. Let $P = P'$

7. if all bits of $k$ are not determined,

   set k = k //2 and return step 2.

As we can see, we break the Dlog easily as long as the Oracle's operation is not expensive. So, DFP2 is at least as hard as DLP.

DFP3 $\implies$ DLP :

This is a little more complicated, instead, I'll give the gist of the idea

• Let $k = 18$ and we get $6$. We can notice this if $(3[\lfloor k/3 \rfloor])G = [k]G$
• let $k = 17$ and we get $5$. We know that it is not the previous case so we try $3\cdot5 +1$ and $3\cdot5 +2$ if any of them is $17$ then we find the key bits.

Of course, we don't get $6$ or $5$, I've used the numbers to indicate how we can use the equality to $[k]P$ to determine the bits.

Similar Oracles can be designed for $//4$ or $//5$... requiring a little more work.

Complexity and better alternative for large $x$

As Poncho pointed out, for small $x$'s the above algorithm can work very nicely, with complexity $\mathcal{O}(\sqrt{x})$. We can see that see that with $[k]G - [x\lfloor(k/x)\rfloor]G = [k \bmod x]G$. By using this equality, we can find $k \mod x$ in $\mathcal{O}(\sqrt{x})$-time with BsGs or Pollard's rho. Of course, for small $x$ we do not bother to initiate BsGs or Pollard's rho, using direct calculation is faster. For large $x$'s below is faster.

The improvement for the large $x$ comes from the binary search. Instead of looking all, we use the mentioned trick is check for $0<i<x$ in binary case to see that;

$$\big[\lfloor{(k-i)/x}\rfloor\big]G == \big[\lfloor(k/x)\rfloor\big]G$$

With this, we can recover $\mathcal{O}(\log x)$ per digit $x$.