2
$\begingroup$

I am working with point addition and scalar multiplication on the secp256k1 curve for points $(x,y)$ or public keys to derive the next public key scalar k times further from it. Actually when I use a larger scalar then it loops back due to the cyclic nature of curve or arithmetic operations. I want such a way to stop its looping or cyclic nature and need a way as if the scalar is larger than the order $n$ then it stops and never loop back.

For Example: when I take the 5th public key of the range and use a scalar equal to the total order n which is: 115792089237316195423570985008687907852837564279074904382605163141518161494336 then it derive the 5th public key again due to cyclic nature but I want it to stop and never generate public key after end of order of the curve.

If there is any way to stop looping back then I'll appreciate the help.

$\endgroup$
3
  • $\begingroup$ @fgrieu they ask simply for the reduction. And I don't know why people downvote such questions. $\endgroup$
    – kelalaka
    Dec 28, 2023 at 11:17
  • $\begingroup$ @kelalaka: I had missed the part of the question that wants to "stop", and thought that it was asked that secp256k1 becomes infinite. Still I do not think that what's asked is $[k]G = [k \bmod n]G$, and doubt that what's asked is possible. $\endgroup$
    – fgrieu
    Dec 28, 2023 at 13:18
  • $\begingroup$ I read that as the main problem, looping goes infinity has no meaning since we cannot multiply with the infinity. Anyway, May be I need to extend the simple answer... $\endgroup$
    – kelalaka
    Dec 28, 2023 at 13:53

1 Answer 1

4
$\begingroup$

Let $n$ be the order of the base point $G$ then we know

$$[k]G = [k \bmod n]G \tag{1}\label{1}$$

This is due to the arithmetic fact that is $a\cdot n = 0 \bmod n$

This prevents us from unnecessary finite looping if $k>n$ then we may see that we reached $G$ again and again. How many times will we see the $G$? It is $\lfloor k / n \rfloor$.

So, instead of the unnecessary costly point addition and doubling, we simply use $k \bmod n$ in the beginning to reduce the cost that you call (finite) looping.

Consider that one calculates $[a\cdot b]G$ in a protocol, then the average uniform random $a$ and $b$ is $\lfloor \log_2 n \rfloor +1$- bits. So, if you don't use the trick in Equation $(\ref{1}$), then you will loop circa $\lfloor \log_2 n \rfloor -1$-times. Use the Equation $(\ref{1}$) to reduce the cost and looping.

$\endgroup$

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.