3
$\begingroup$

I wrote a solidity smart contract for elliptic curve point addition in Jacobian coordinates.

Jacobian coordinates: [X,Y,Z] Affine representation: [x,y]=[X/Z^2, Y/Z^3]

I used the following formulas: Link. My code seems to work fine however my questions are:

  1. What is the additive inverse in Jacobian coordinates? Is it the point at infinity and the result therefore: P-P=[0,1,0]?

  2. My elliptic curve multiplication function seems to have an error, any idea? I think I need to set the start value of R to "additive zero for points".

// function for elliptic curve multiplication in jacobian coordinates using Double-and-add method
function ecmul(uint256[3] P, uint256 d) constant returns (uint256[3] R) {

  R[0]=0;
  R[1]=0;
  R[2]=0;

  //return (0,0) if d=0 or (x1,y1)=(0,0)
  if (d == 0 || ((P[0]==0) && (P[1]==0)) ) {
    return (R);
  }
  uint256[3] memory T;
  T[0]=P[0]; //x-coordinate temp
  T[1]=P[1]; //y-coordinate temp
  T[2]=P[2]; //z-coordiante temp

  while (d != 0) {
    if ((d & 1) == 1) {  //if last bit is 1 add T to result
      R = ecadd(R,T);
    }
    T = ecdouble(T);    //double temporary coordinates
    d=d/2;              //"cut off" last bit
  }

  return R;
}
$\endgroup$
  • 1
    $\begingroup$ The additive inverse of the point $[X, Y, Z]$ is $[X, -Y, Z]$ (assuming a standard Weierstrauss curve which is not characteristic 2 or 3) $\endgroup$ – poncho Mar 7 '17 at 21:59
  • $\begingroup$ I probably forgot to add that all this calculations are done in Fp, a finite field domain. I am only using positive integers. $\endgroup$ – floyd Mar 7 '17 at 23:11
  • $\begingroup$ In $GF(p)$, we have $-Y = P-Y$. That is, the additive inverse of $Y$ is denoted as $-Y$, and it can be computed as $P-Y$ (unless $Y=0$) $\endgroup$ – poncho Mar 8 '17 at 1:19
2
$\begingroup$

Since Meysam Ghahramani answered correctly to your first question, I will just tackle the second one.

In theory, yes, you should set $R$ equal to the point at infinity, which is the neutral element in the addition law on (this type of) elliptic curves.

But in practice it won't work. The formulas you are using for addition is incomplete as both inputs are required to be different from the point at infinity (as stated in your link).

You can solve it by first checking if $R$ is equal to $(0,0,0)$ and in that case instead of performing ecadd, you just copy $T$ to $R$.

Also note that there are elliptic curves where $(0,0)$ is a valid point, in which case you should not just return $(0,0,0)$ as you are doing. But you didn't specify which curve you are using so this might not be an issue.

$\endgroup$
3
$\begingroup$

The projective form of Weierstrass equation of an elliptic curve is obtained by replacing $x$ by $X/Z^c$ and $y$ by $Y/Z^d$. If $c=d=1$ then we have standard projective coordinates. In this state, point at infinity is $(0:1:0)$. But in Jacobian coordinates($c=2$ and $d=3$), point at infinity is $(1:1:0)$.

As poncho said in comments, The additive inverse of the point $(X:Y:Z)$ is $(X:-Y:Z)$ .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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