2
$\begingroup$

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

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

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