Join Log in
Score:2
LeonMSH avatar Crypto

ECC Point Addition on Jacob coordinate -- Not Commutative?

us flag
LeonMSH

I have a python script that does the ECC point addition (code paste below), it simply performs the P =Q1+Q2 on Jacob coordination. However, when doing some regression tests, I found that if I exchange the P1 and P2 positions, I will get different results, one of which is correct. Below is an example that simply using secp256k1 G point as one point, and 2*G as the 2nd point to run the test.

My questions (Update comments after get reply from @fgrieu) 1). The ECC point addition on a curve--would that be Commutative ( should be)?

2). I noticed that for the results, x coordinate are the same while y/z are different-- (they represent the same on affine coordinate).

3). Based on suggestions I update the script making it completed.

def Point_Add(self, Q1, Q2):
    if (Q1.x==self.p): 
        return Q2
    if (Q2.x==self.p):
        return Q1
    Q1z2 = (Q1.z*Q1.z)      % self.p
    Q2z2 = (Q2.z*Q2.z)      % self.p

    U1   = (Q1.x*Q2z2)      % self.p
    U2   = (Q2.x*Q1z2)      % self.p

    S1  = (Q1.y*Q2z2*Q2.z)  % self.p
    S2  = (Q2.y*Q1z2*Q1.z)  % self.p
    if (U1 == U2): 
        if (S1!=S2): # oppsite pair, i.e. Q1 = -Q2
            return self.Unit
        else:   # Q1 = Q2
            return self.Point_Double(Q1)

    H    = (U2-U1)      % self.p   
    R    = (S2-S1)      % self.p
    H2   = (H*H)        % self.p
    H3   = (H2*H)       % self.p

    x3   = (R*R-H3-2*U1*H2 )   % self.p
    y3   = (R*(U1*H2-x3)-S1*H3 )   % self.p
    z3   = (H*Q1.z*Q2.z)           % self.p

return JBPoint(self, x3, y3, z3)

Test result
Debug 1: test P=Q1+Q2:
Point.X(Jacob):  0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Point.Y(Jacob):  0x435afe76017b8d55d04ff8a98dd60b2ba7eb6f87f6b28182ca4493d7165dd127
Point.Z(Jacob):  0x9242fa9c0b9f23a3bfea6a0eb6dbcfcbc4853fe9a25ee948105dc66a2a9b5baa
Point.X(affine):  0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Point.Y(affine):  0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Point.X(affine):  112711660439710606056748659173929673102114977341539408544630613555209775888121
Point.Y(affine):  25583027980570883691656905877401976406448868254816295069919888960541586679410
Debug 2: test P=Q2+Q1:
Point.X(Jacob):  0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Point.Y(Jacob):  0xbca50189fe8472aa2fb007567229f4d458149078094d7e7d35bb6c27e9a22b08
Point.Z(Jacob):  0x6dbd0563f460dc5c401595f1492430343b7ac0165da116b7efa23994d564a085
Point.X(affine):  0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Point.Y(affine):  0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Point.X(affine):  112711660439710606056748659173929673102114977341539408544630613555209775888121
Point.Y(affine):  25583027980570883691656905877401976406448868254816295069919888960541586679410
127
1 + 0
Score:4
fgrieu avatar Crypto
ng flag
fgrieu

  1. ECC point addition is commutative.

  2. The problem encountered is that in the Jacobian coordinate system, a point other than the neutral has several equally valid triplets of coordinates $(x,y,z)$, all corresponding to the same $(z^{-2}\,x,z^{-3}\,y)$ in the Cartesian coordinate system. Equality can be tested as ${z_2}^2\,x_1-{z_1}^2\,x_2\bmod p=0$ and ${z_2}^3\,y_1-{z_1}^3\,y_2\bmod p=0$ (If there is a shortcut beyond reusing $z^2$ to compute $z^3$ assuming the points are on the curve, I want to learn it).

  3. The code initially shown did not handle the case where Q1 and Q2 represent the same point (that is, point doubling). Further, nothing specified how the neutral is represented on input and output. That's fixed now.

Update, expanding on 3: there are several special cases to point addition $Q_1+Q_2$, that need special treatment:

  • when $Q_1$ is the neutral, result is $Q_2$;
  • when $Q_2$ is the neutral, result is $Q_1$;
  • when $Q_1=Q_2$ (within the definition in 2), that's point doubling;
  • when $Q_1=-Q_2$, the result is the neutral.

There are multiple ways to handle this. If asked to modify the Python code initially shown, I'd first add prominent disclaimers that the code is not even trying to mitigate timing attacks (which is next to impossible to do perfectly in Python anyway), thus must not be used when that's an issue (often including computing a signature); then I would probably:

  • define that anything with $z=0$ is the neutral, and use this to handle the first two cases in the obvious way, and the fourth with no extra code needed.
  • detect that $H=0$ and $R=0$, which tells we are doing point doubling and thus need other formulas.

The code now shown uses another (I think, valid) method where $(p,0,1)$ is the neutral. That works too, with a (probably barely measurable) performance and code size drawback:

  • explicit code is needed for the $Q_1=-Q_2$ non-neutral case, when it's not for the neutral defined as $(p,0,1)$. In legitimate practical use in cryptography, that special case is so rare that removing it improves performance.
  • the two initial tests for the neutral are slightly larger and slower.

Again, comments should be added that the code makes no effort to avoid data-dependent timing dependencies, which can constitute a side channel.

0 + 8
LeonMSH avatar
us flag
LeonMSH
Thanks a lot for the quick response... Q2). Does that mean both results I got are valid (represent the same point on Cartesian coordinate)? Is there some further restriction I can set, so that I can get the same unique Jacob coordinate, I can convert back to check on Cartesian coordinate for that but as I have some benchmark test to be done later to make sure Jacob coordinate works perfect, without a unique value it is very inconvenient ). 3)Yes you find it, I did not put the checking of the special case yet, that should be added;
0
Reply
LeonMSH avatar
us flag
LeonMSH
Yes, I make an affine coordinate check, the result points are the same on affine actually. My left question would be: is there any way (or tricky) that I can always get the same Jacob coordinate(I don't care coverage, just care about correctness.
0
Reply
fgrieu avatar
ng flag
fgrieu
@LeonMSH: the only ways I see to "always get the same Jacob[ian] coordinate" are to normalize to the same $z$, e.g. $z=1$, that is change $(x,y,z)$ of the result to $(z^{-2}\,x,z^{-3}\,y,1)$. But that negates the rationale of using Jacobian coordinates in the first place, which is to avoid the modular inverse.
0
Reply
111 avatar
us flag
111
Maybe, if you use only affine coordinates. Having affine coordinates, say $(a,b)$ to get the projective coordinates of this point, just send it to $[a:b:1].$ Special care is needed for the point at infinity. If you add the points $(a_1,b_1)$ and $(a_2,b_2)$ you have to check if $b_1=b_2.$ The addition of these points is the point at infinity $[0:1:0]$ (using Weierstrass model). Hope that helps.
0
Reply
LeonMSH avatar
us flag
LeonMSH
@111, for affine point P1(a1,b1) and P2(a2,b2), if b1=b2, P1+P2 should be point double? I think you mean b1 =-b2 case?
0
Reply
LeonMSH avatar
us flag
LeonMSH
@fgrieu in terms of infinity point O Jacobian coordinate -- I see different representations, like O= (p, 0, 1), (0, 1, 0), (1 , 1 , 0) , then what is the right?
0
Reply
111 avatar
us flag
111
@LeonMSH right. b1=-b2.
0
Reply
LeonMSH avatar
us flag
LeonMSH
@fgrieu I update the script , BTW the Unit point I am using for this code is O(p,0,1) but not point with z=0.. It works anyway. that is why I ask the question regarding the point O, for jacob point..
0
Reply
ธงชาติไทย
Elon Musk
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.