Subject: [Cfrg] Question about edwards448 mapping in draft-irtf-cfrg-curves-11

From: Andrew Bennett <[email-masked]>
Date: Mon, 18 Jan 2016 03:59:18 +0000

Hello,

Quick disclaimer: my question detailed below might simply be due to my own
lack of knowledge related to the mathematical concepts of elliptic curves
and their isogenies.

In section 4.2 [1], there are 3 curves described: (1) a Montgomery curve
named "curve448" (2) an unnamed birationally equivalent Edwards curve (3) a
4-isogenous Edwards curve named "edwards448".

For each curve, a set of (u, v) and (x, y) functions are provided which are
easily verifiable using the provided basepoints between curves (1) and (2)
and partially between curves (1) and (3).

My question is about the 4-isogeny mapping listed under (3):

(u, v) = (y^2/x^2, (2 - x^2 - y^2)*y/x^3)
(x, y) = (4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1),
          -(u^5 - 2*u^3 - 4*u*v^2 + u)/
          (u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u))

The (u, v) functions return the expected basepoint from "curve448" when
using the x and y values from "edwards448" (in python/sage):

# variables used in examples below
p = 2^448 - 2^224 - 1
u = 5
v =
355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362
x =
224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710
y =
298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660

# testing (u, v) functions; both return True
u == y^2/x^2 % p
v == (2 - x^2 - y^2)*y/x^3 % p

However, I am unable to produce the expected "edwards448" basepoint from
the (x, y) functions when using the u and v values from "curve448":

# testing (x, y) functions; both return False
x == 4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1) % p
y == -(u^5 - 2*u^3 - 4*u*v^2 + u)/(u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u) % p

# x returned is:
209710714663589237570084264541991420589833663592202160838176801982171960997051286469552065490170659385708816452452440655275673121357616
# y returned is:
603515570432573637134887094808958022419371301976351441963100315034426774344109511210661998660350679225364893651728492312845104034682937

Adding to my confusion, while searching for more understanding of the
Edwards-Montgomery mapping, I found another paper [2] which contains a
"Proposition 2" with similar functions which produce the same x and y
values:

# variables used in examples below
d = -39081
A = -(4*d - 2)

# testing alternative (x, y) functions; both return False returning
identical x and y values mentioned above
x == (-4*(1 - u^2)*v)/(u^4 - 2*u^2 + 4*v^2 + 1) % p
y == ((u^2 + 2*v - 1)*(u^2 - 2*v - 1))/(2*A*u^3 + u^4 + 2*A*u + 6*u^2 + 1)
% p

All of the above code examples are also available in a gist [3].

My question is: Are the functions for the (x, y) mapping correct?  If so,
am I calculating the resulting x and y values correctly?  If so, how are
the x and y values returned related to "edwards448"?

Any help with understanding the (x, y) mapping between "curve448" and
"edwards448" would be greatly appreciated.

Thanks,
Andrew Bennett

[1] https://tools.ietf.org/html/draft-irtf-cfrg-curves-11#section-4.2
[2] http://cryptosith.org/papers/isogenies_tEd2Mont.pdf
[3] https://gist.github.com/potatosalad/fc758365095d5d659cdb

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 18 Jan 2016 06:26:52 +0200

> lack of knowledge related to the mathematical concepts of elliptic curves

Quick guess to the cause: This is not isomorphism, but 4-isogeny, so
when one round-trips once, the point gets multiplied (as in scalar
multiplication by four: 4G).

The conversion from Edwards basepoint to Montgomery basepoint "works"
since the Edwards basepoint is specifically chosen so that:

- It yields Montgomery basepoint when converted
- It has prime order.

-Ilari

---

From: Andrew Bennett <[email-masked]>
Date: Tue, 19 Jan 2016 16:54:11 +0000

Whoops, for some reason I didn't connect the meaning of the 4-isogeny
between curve448 and edwards448 as being a scalar multiplication by 4.
Thank you for your accurate guess :-)

I was curious if I could find some sort of reproducible pattern for
converting between the (u,v) of curve448 and the (x,y) of edwards448 and
wound up with this slow/messy conversion using Sage (in case anyone else in
the future is confused like I was):

p = 2^448-2^224-1
F = GF(p)
d = -39081
E = EllipticCurve(F,[0,2-4*d,0,1,0])
curve448_basepoint = E.lift_x(5)
curve448_basepoint_div4 = curve448_basepoint.division_points(4)[0]
u = curve448_basepoint_div4[0]
v = curve448_basepoint_div4[1]
edwards448_x = 4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1) % p
edwards448_y = -(u^5 - 2*u^3 - 4*u*v^2 + u)/(u^5 - 2*u^2*v^2 - 2*u^3 -
2*v^2 + u) % p

Thanks again for you help!
Andrew Bennett