1
$\begingroup$

Is the result of 4G the same when calculated as 3G + 1G or 2G + 2G in projective coordinates? Considering a curve like (y^2 = x^3 + 10x^2 + x (mod 83)) with a Generator point G = (3, 28) in affine coordinates, or (3:28:1) in projective coordinates, the calculations indicate that 2G = (64:Y-coordinate:65) and 3G = (25:Y-coordinate:9). However, for 4G, when calculated as:

First: 2G + 2G, you obtain (64:Y-coordinate:65) + (64:Y-coordinate:65) = (41:Y-coordinate:26),

Second: and when calculated as 3G + 1G, you get (25:Y-coordinate:9) + (3:28:1) = (77:Y-coordinate:48).

The first calculation correct because the x-coordinates match when converted back to affine coordinates. But there always seems to be a difference between 4G=2G+2G and 4G=3G+1G. Why is that?

Note that I wrote Y-coordinate based on how points are represented in projective coordinates and since it wasn't utilized in the subsequent computations, I didn’t mention its value and I just wrote Y-coordinate instead. I will detail all the calculations to clarify the challenges encountered in this curve and others in Montgomery curves: As I mentioned that I am sure that 2G = (64:Y:65) and 3G (25:Y:9). let’s start with 4G = 2G + 2G utilizing the point doubling mathematical laws and of curse all the calculations is made under (mod 83) :

4G = 2G + 2G = (64:Y:65) + (64:Y:65)

4XZ = (X+Z)^2 –(X-Z)^2 = (64+65)^2 – (64-65)^2 = 40

X_result = (X+Z)^2 * (X-Z)^2 = (64+65)^2 * (64-65)^2 = 41

Z_result = 4XZ * ((X-Z)^2 + (A+2/4)*4XZ) = 40 * ((64-65)^2 + (10+2/4) * 40) = 26

So 4G in this scenario is (41:Y:26) or (41:26) as excluding Y representation.

but when we calculate 4G = 3G + 1G = (25:Y:9)+(3:28:1) utilizing the point adding mathematical laws, we get the following:

X_result = Z * ((X2-Z2)(X1+Z1)+(X2+Z2)(X1-Z1))^2 = 1*((3-1)(25+9)+(3+1)(25-9))^2 = (234 + 416)^2 = 77

Z_result = X * ((X2-Z2)(X1+Z1)-(X2+Z2)(X1-Z1))^2 = 3 * ((3-1)(25+9) - (3+1)(25-9))^2 = 3 * (234 – 416)^2 = 48

As shown and in this scenario 4G = (77:Y:48) or (77:48)

$\endgroup$
6
  • 1
    $\begingroup$ Why do you write Y-coordinate and why do you omit $Z$ in projective coordinates? $(X:Y:Z)$ This tells the projective coordinate used ( equivalence relation). Where are the details of your calculations? Probably $Z$ becomes larger than 1 and you omit to normalize? $\endgroup$
    – kelalaka
    Commented Mar 24 at 19:19
  • $\begingroup$ @kelalaka , what do you mean by (Probably Z becomes larger than 1 and you omit to normalize?) because in addition law the X3 it always multiplied by Z-coordinate of the generator point and it is equal to 1 always. Right ? or there is something I misunderstood ? $\endgroup$ Commented Mar 25 at 9:52
  • 1
    $\begingroup$ In the Q there is (A+2/4) where there should be ((A+2)/4), and then the doubling method in the Q matches this. When I compute 2*(3:28:1) then 4*(3:28:1) in this way I get (64:Y:65) and (41:Y:26) like in the Q. What is the origin and conditions of application of the formula used to compute 4G = 3G + 1G ? I think I recognize the formula for (2n+1)G as a function of nG, (n+1)G, and G, as in the bottom of the first page of this, but how would that allow to compute 4G? $\endgroup$
    – fgrieu
    Commented Mar 25 at 13:51
  • $\begingroup$ @fgrieu , I didn't get what do you mean by(I think I recognize the formula for (2n+1)G as a function of nG, (n+1)G, and G, as ...). I made my calculations according to the code exists in page 8 of [datatracker.ietf.org/doc/html/rfc7748#page-4] which based on the formula in the [en.wikipedia.org/wiki/Montgomery_curve#Montgomery_arithmetic]. I don't face any problem with doubling calculations, so I got the correct answers when I calculate 2G = G+G, 4G =(2G+2G), 8G=(4G+4G), ... but I am facing the problem in Adding operation 4G=3G+1, 5G=4G+1,... but I didn't face it with 3G=2G+G $\endgroup$ Commented Mar 25 at 14:45
  • $\begingroup$ I think (not sure) that the formula for addition that you are using has preconditions that are met in the case of that algorithm, but not in your use to compute 3G+G. This formula works when adding (n+1)G and nG knowing G, perhaps more generally to add P and Q knowing P-Q, but I do not see that we are in this case, at least when you take X=3. $\endgroup$
    – fgrieu
    Commented Mar 25 at 15:22

1 Answer 1

2
$\begingroup$

On the Montgomery Curve $y^2\equiv x^3+10x^2+x\pmod{83}$ with $G$ having $(x,y)=(3,28)$, and using projective coordinates $(X,Y,Z)$ defined by $x\,Z=X$ and $y\,Z=Y$, the question is correctly stating that $(X,Z)$ is $(3,1)$ for $G$, is $(64,65)$ for $2G$, and is $(25,9)$ for $3G$.

The question computes $4G$ by doubling $2G$ using these doubling formulas, correctly yielding that $(X,Z)$ is $(41,26)$ for $2(2G)=4G$.

The question then attempts an alternate computation of $4G$ as $3G+G$ using essentially these addition formulas (with the indexes changed). The formulas compute $(X,Z)$ for $P+Q$ knowing $(X,Z)$ for $P$, $Q$, and $P-Q$, respectively noted (X1, Z1), (X2, Z2), and (X, Z) in the question.

The mistake made is using the wrong $(X,Z)$ for $P-Q$: that should be $(64,65)$ for $2G=3G-G$, not $(3,1)$ for $G$. The cause of the mistake is that the formula is most often used in the Montgomery ladder, where the two operands are $(n+1)G$ and $nG$ (within order), thus $P-Q$ is $G$ (within sign, which does not change the $(X,Z)$ coordinates).

With this correction we get that $(X,Z)$ for $3G+G$ is $(25,28)$, which as expected is equivalent to $(X,Z)$ for $2(2G)$ of $(41,26)$, since $25⋅26\equiv28⋅41\pmod{83}$.

$\endgroup$
4
  • $\begingroup$ You accurately pointed out the mistake I made. I'm very grateful for your help, thank you so much for assisting me. $\endgroup$ Commented Mar 25 at 19:46
  • $\begingroup$ @NawrasHussein: this has been useful to me too: I now better understand the so-called differential addition on Montgomery curve. $\endgroup$
    – fgrieu
    Commented Mar 25 at 20:10
  • $\begingroup$ So does this what differential addition on Montgomery curve means? Or does it have another meaning? $\endgroup$ Commented Mar 25 at 22:11
  • 1
    $\begingroup$ @NawrasHussein: My new understanding of differential addition on Montgomery curve is that it computes on (X,Z) coordinates, getting these for P+Q knowing these for P, Q, and P-Q. My former understanding was restricted to the context of computing multiples of G per the Montgomery ladder, which happens to keep (X,Z) for P-Q to the same (X,1) as for G all along. $\endgroup$
    – fgrieu
    Commented Mar 26 at 8:42

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.