6
$\begingroup$

I am working with golang's elliptic library.

It implements functions on Weierstrass elliptic curves with $a=-3$. I need to make my own library that allows me to handle curves with $a=0$. I understand there are specific equations to use to optimally perform operations on different elliptic curves, which can be found in Short Weierstrass curves.

I would like to know which functions from the library I should change, and which stay the same (as I'm not an expert in cryptography). Here is the full list:

IsOnCurve, affineFromJacobian, Add, addJacobian, Double, doubleJacobian, ScalarMult, ScalarBaseMult, GenerateKey, Marshal, Unmarshal, and some initialization functions.

As I understand I need to change the following:

  • IsOnCurve (removing the -3x)
  • doubleJacobian (different equation)
  • and the init functions

Those should stay the same:

  • Add
  • addJacobian (same optimal equation)
  • Double
  • ScalarBaseMult
  • Marshal
  • Unmarshal

And I'm not sure about those:

  • affineFromJacobian
  • ScalarMult
  • GenerateKey

Can anyone tell me if my list is correct, and if not, give me some feedback on how I should change the given items?

$\endgroup$

1 Answer 1

2
$\begingroup$

I have not thoroughly investigated golang's elliptic library (or Go at all), but I have implemented elliptic curves (with Jacobian coordinates) and I would say that your guess is correct. The "$a$" parameter is not used in the addition of two distinct points, but it appears in the formulas for doubling a point. With Jacobian coordinates, a normal implementation will include core functions such as addJacobian() and doubleJacobian(), which are used only through wrappers which filter out the special cases (if both operants to an "add" are identical, then it must be a "double"; if one operand is the point-at-infinity, then the result is the other operand).

The $a$ curve parameter is supposedly used when doubling a point, and when deciding if a point is on the curve or not (by applying the curve equation). It would also be used in point (de)compression, a kind of marshalling which saves a bit of space; but point compression does not appear to be implemented in the code you link to (it is optional and rumoured to be patented, which is why it is often avoided).

I am not entirely sure that the code is correct, though. In ScalarMult(), the multiplier is not reduced modulo the curve order, so an oversized value k could imply calling addJacobian() on a point and itself, something which does not appear to be handled in the code (this should be checked: if $n$ is the curve order, try $k = n+2$; this should yield $2G$ if the code is correct).

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