Score:2

Help with adding and multiplying points on secp256k1

im flag

I'm currently working on implementing digital signatures on the curve secp256k1 (for learning purposes only), and I'm having some trouble implementing ECDSA on curve secp256k1. As I understand it, this curve is a koblitz curve, which means it can't be written in the Montgomery form. Due to this limitation, I'm unable to use the Montgomery ladder.

Can anyone suggest how I can add and multiply points on the curve in this case? Any guidance or resources would be greatly appreciated.

Thanks in advance

Score:2
ng flag

Roadmap to implementing ECDSA on secp256k1 for educative purposes

  1. Have low expectations:
    • Something slow if you stop at the end of 2, and not fast even if you go all the way of 3.
    • Something not safe from side-channel (and others) attacks for signature generation.
  2. Dive in:
    • Get large-integer arithmetic running (that's built in Python, an bundled in Java), including modular inversion.
    • Implement point adding and doubling by the standard technique from sec1.
    • Use secp256k1 parameters from sec2.
    • implement point multiplication by a scalar using straight double-and-add according to the binary representation of the scalar.
    • get SHA-256 running (that's bundled in Python and Java).
    • get ECDSA running.
  3. Optimize speed:
    • Use projective or Jacobian coordinates to eliminate most modular inversions, which are the bottleneck in 2.
    • Use wNAF to perform less point additions.
    • Use sliding window to the same effect.
    • Use Shamir's trick to about halve the number of doublings in signature verification.
    • Use the Koblitz-curve-specific technique there.

Proofread and test along the way. Again, do NOT expect something secure for signature generation.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.