Performing EdDSA/Ed448 employing Montgomery ladder

Question

EdDSA can be efficiently performed employing the Montgomery ladder. In order to implement this method, the base point should be converted to Mont. space, then the Mont. ladder should be executed, and the $y$-coordinate is required to recover. Eventually, the achieved point should be converted to twisted Edwards space.

I design a scheme to work in twisted Edward space, and all results are verified by the given test vector in RFC 8032.

Now I am trying to work over Montgomery space. The first three mentioned steps, i.e., convert the base point to Mont., Mont. ladder execution, and y-coordinate recovery can be performed simply. However, the back transformation has a problem. Based on the equation described in RFC 7748, the map between Mont. space and Ed space are as follows: \begin{multline} (x, y) = \frac{(4*v*(u^2 - 1)}{(u^4 - 2*u^2 + 4*v^2 + 1)},- \frac{(u^5 - 2*u^3 - 4*u*v^2 + u)}{(u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u)} \end{multline}

I have used (5 , 355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362) as the base point over Curve448. Furthermore, in $y$-coordinate recovery, I suppose $A=156326$, and $B=1$. After $y$-coordinate recovery, the $(u,v)$ coordinates in Mont. space is represented in projective coordinates, i.e., $(X,Y,Z)$. Now this point is required to converet to Edward space, i.e. $(x,y)$.

This is my attempt (in sage) to achieve the point in Ed448-Goldilocks:

#P_projective=y_recovery(R0,R1,P_base) where R0=k*P_base
x2=R0[0]
z2=R0[1]
x3=R1[0]
z3=R1[1]
x1=P_base[0]
y1=P_base[1]

t1 = mod(x1*z2,p)
t2 = mod(x2+t1,p)
t3 = mod(x2-t1,p)
t3 = mod(t3^2, p)
t3 = mod(t3 * x3,p)
t1 = mod(312652 * z2,p) #2A = 2*156326
t2 = mod(t2 + t1,p)
t4 = mod(x1 * x2,p)
t4 = mod(t4 + z2,p)
t2 = mod(t2 * t4,p)
t1 = mod(t1 * z2,p)
t2 = mod(t2-t1,p)
t2 = mod(t2 * z3,p)
t1 = mod(y1 + y1,p)
t1 = mod(t1 * z2,p)
t1 = mod(t1 * z3,p)
X = mod(t2-t3,p)
Y = mod(t1 * x2,p)
Z = mod(t1 * z2,p)

# convert from Mont. space to Edwards space where x=a1/a2 y=b1/b2
a1 = mod(4*Y*Z*(X^2-Z^2),p)
a2 = mod(X^4-2*X^2*Z^2+4*Y^2*Z^2+Z^4,p)
b1 = mod(-(X^5-2*X^3*Z^2-4*X*Y^2*Z^2+X*Z^4),p)
b2 = mod(X^5-2*X^2*Y^2*Z-2*X^3*Z^2-2*Y^2*Z^3+X*Z^4,p)

a2_inv = Integer(inverse_mod(Integer(a2),p))
x = mod(a1*a2_inv,p)

b2_inv = Integer(inverse_mod(Integer(b2),p))
y = mod(b1*b2_inv,p)

The results are not correct. what mistake I did? Should I do any other step to get the same point in the Ed448 curve?

Answer 1

According to Alternative Elliptic Curve Representations, each other point $(x1,y1)$ of Edwards448 corresponds to the point $(u,v)$ of Curve448, where:

$u = y1^2/x1^2$

$v = y1*(2-x1^2-y1^2)/x1^3.$

Under this isogenous mapping, the base point $(G1x, G1y)$ of Edwards448 corresponds to the base point $(Gu,Gv)$ of Curve448. The dual isogeny maps both the point at infinity and the point $(0,0)$ of order two of Curve448 to the point $(0,1)$ of Edwards448, while each other point $(u,v)$ of Curve448 corresponds to the point $(x1,y1)$ of Edwards448, where:

$x1 = 4*(u^2-1)*v/((u^2-1)^2+4*v^2)$

$y1 = u*((u^2-1)^2-4*v^2)/(2*(u^2+1)*v^2-u*(u^2-1)^2).$

under this dual isogenous mapping, the base point $(Gu, Gv)$ of Curve448 corresponds to a multiple of the base point $(G1x, G1y)$ of Edwards448, where this multiple is $l=4$ (the degree of the isogeny)