2
$\begingroup$

I am using Montgomery ladder with Montgomery curve $by^2=x^3+ax^2+x$ using XZ coordinates and I recovered the $X$ value using $X3=X1/Z1$, but I don't know how to recover the $Y$ coordinates.

for Double and add ladder I am using this:

      A = X2+Z2
      AA = A2
      B = X2-Z2
      BB = B2
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = Z1*(DA+CB)2
      Z5 = X1*(DA-CB)2
      X4 = AA*BB
      Z4 = E*(BB+a24*E)

I tried this way :

x3=2;
y3 = mod(mod((x3.^3 + mod(a*x3.^2,p)+x3),p) * mod(modinvr(b,p),p),p);

for y = 0:22
    x = mod(y^2, 23);
    if x == y3
        fprintf("y = %d\n", y);// here I got two values of y 8 and 15
    end
end

here I got two values of y 8 and 15 both are correct points on the curve but in my case I want to choose 8 because the affine scalar point is (2,8) I have another point on the curve (2,15) but not in my scalar point! so that's why I need to select 8 instead of 15.

$\endgroup$
6
  • 1
    $\begingroup$ Have you tried solving the curve equation for $y$? $\endgroup$
    – swineone
    Commented Mar 12, 2023 at 21:35
  • $\begingroup$ I tried but it gives me 2 y coordinates but dont know how to choose the correct one $\endgroup$ Commented Mar 13, 2023 at 7:40
  • $\begingroup$ @swineone I tried this %y3=(x+X1/Z1)[(X1+x*Z1)(X2+x*Z2)+(x^2+y)(Z1*Z2)](x*Z1*Z2)^-1+y but it doesn't give me the correct value? $\endgroup$ Commented Mar 13, 2023 at 15:50
  • $\begingroup$ @swineone I edited with my trial $\endgroup$ Commented Mar 13, 2023 at 18:43
  • 1
    $\begingroup$ Being a quadratic equation, there are indeed 2 possible solutions. I’m a little rusty on my elliptic curves, but either both are valid, or your standard should specify a disambiguation rule: say, always take the positive value, or a value with some other property. $\endgroup$
    – swineone
    Commented Mar 14, 2023 at 13:13

2 Answers 2

4
$\begingroup$

Although x25519 uses only the x-coordinate for the DH, for some protocols the $y$ coordinate is also required. So, if one wants to find the $y$ coordinate of $[n]P$, where $P=(x_1,y_1)$ is in affine coordinates, there is a paper for finding $y_n=Y_n/Z_n$ from $x_1,y_1$, and $x_n$;

Given the Montgomery curve $$M_{A,B}:By^2 = x^3 + Ax^2 +x$$ The result simply is;

$$y_n = \frac{(x_nx_1+1)(x_n+x_1+2A)-2A-(x_n-x_1)^2x_{n+1}}{2By_1}$$

Yes, it is $x_{n+1}$, and for that one needs to go for $[n+1]P$.

$\endgroup$
1
$\begingroup$

I also recommend seeing section 4.3 on Montgomery curves and their arithmetic by Craig Costello and Benjamin Smith. It cites the document from the answer above but also explains, has the algorithm and the closed form while giving some "history" on the recovery of y.

$\endgroup$
1
  • 1
    $\begingroup$ We prefer self-contained answers to mere link to references. But your reference is extremely relevant! $\endgroup$
    – fgrieu
    Commented Nov 13, 2023 at 7:26

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.