0
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ Are you looking for something that, given xG, will give you (x//3)G? If so, well, we hope that you can't (because such an operation allows you to break ECC...) $\endgroup$
    – poncho
    Nov 13, 2023 at 21:34

1 Answer 1

2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Thank you for the insightful explanation! I'm curious about the idea of designing oracles for $//3$ or $//4$. Could you provide more details or steps on how one might programmatically implement these oracles? $\endgroup$
    – Favour
    Nov 14, 2023 at 11:40
  • $\begingroup$ @Favour a little extended the answer.To implement such oracle, you need to give the $k$ it $\endgroup$
    – kelalaka
    Nov 14, 2023 at 15:34
  • 1
    $\begingroup$ @kelalaka: your algorithm works nicely for small $x$ (which can recover the digits base $x$ with $O(\sqrt{x})$ time per digit. For larger $x$, you can rely on checking if $((k-i)//x G == k//xG - iG$; that'll tell you whether $k \bmod x \le i$; you use binary searching to determine $k \bmod x$ taking $O(\log x)$ time per digit $\endgroup$
    – poncho
    Nov 14, 2023 at 17:37
  • 1
    $\begingroup$ @kelalaka: sorry, I meant checking if $((k-i)//xG == k//xG$... $\endgroup$
    – poncho
    Nov 14, 2023 at 20:53
  • 1
    $\begingroup$ @kelalaka: Naah, that's not why your algorithm uses $O(\sqrt{x})$ time. Instead, it effectively computes $kG - x(k//x)G = (k \bmod x)G$. Given that you know $0 \le k \bmod x < x$, you can compute the discrete log of $(k \bmod x)G$, recovering the value of $k \bmod x$ in square-root time (say, by using Giant Step/Baby Step). Of course, for tiny $x$, you don't need to bother with GSBS; for modest $x$ (say, $x \approx 2^{20}$), you would $\endgroup$
    – poncho
    Nov 15, 2023 at 19:35

Your Answer

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

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