2
$\begingroup$

In RFC 7748, it is explained how the Montgomery curve, curve448, is deterministically generated from the prime $p = 2^{448} - 2^{224} - 1$. It is also explained how the generator (given below) for curve448 is derived.

    U(P)  5

    V(P)  355293926785568175264127502063783334808976399387714271831880898
          435169088786967410002932673765864550910142774147268105838985595290
          606362

RFC 7748 also defines the Edwards curve, edwards448, and states that there is an isogeny from curve448 to edwards448 (explicit transformations are defined for curve448 --> edwards448 and edwards448 --> curve448).

The following generator for edwards448 is given:

   X(P)  224580040295924300187604334099896036246789641632564134246125461
         686950415467406032909029192869357953282578032075146446173674602635
         247710

   Y(P)  298819210078481492676017930443930673437544040154080242095928241
         372331506189835876003536878655418784733982303233503462500531545062
         832660

Can someone explain how X(P),Y(P) are computed from U(P),V(P)?

Plugging U(P),V(P) into the transformation curve448 --> edwards448 does not yield X(P),Y(P) (perhaps it yields some point in an equivalence class with X(P),Y(P) but I am not sure how to check that). However, if you plug X(P),Y(P) into the transformation edwards448 --> curve448, then you do get U(P),V(P).

In case it is helpful, the maps given in RFC 7748 are presented below as sage code:

p =  2^448 - 2^224 - 1


# edwards448 --> curve448
def getU(x,y):
    u = mod(y^2/x^2, p)
    return u

def getV(x,y):
    v = mod((2 - x^2 - y^2)*y/x^3, p)
    return v

# curve448 --> edwards448
def getX(u,v):
    x = mod(4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1), p)
    return x

def getY(u,v):
    y = mod(-(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)
    return y

# edwards448 generator
Gx = 224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710
Gy = 298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660

# curve448 generator
Gu = 5
Gv = 355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362
$\endgroup$
6
  • $\begingroup$ Did you check the errata? rfc-editor.org/errata/rfc7748 $\endgroup$
    – kelalaka
    Sep 7 at 20:09
  • $\begingroup$ yes, I did check the errata. There is no mention of this there. $\endgroup$
    – user61836
    Sep 7 at 20:10
  • $\begingroup$ Base points are mapped via the birational equivalence, not with the Isogenies $\endgroup$
    – kelalaka
    Sep 7 at 20:18
  • $\begingroup$ the birational map is defined between curve448 and an edwards curve slightly different from edwards448 (it has a different d value). I don't see how to use the birational map to go from curve448 to edwards448. $\endgroup$
    – user61836
    Sep 7 at 20:25
  • 2
    $\begingroup$ I read that paper previously. A different generator is defined there (i.e. it does not match up with RFC 7748). $\endgroup$
    – user61836
    Sep 7 at 21:43

2 Answers 2

3
$\begingroup$

It doesn't work as you expect.

This is a 4 degree isogeny, not an isomorphism or a birational equivalence. One complete map $toMonty(toEdwards(P))$ will not get you to the starting point $(P)$, it will get you to $4*P$ due to the degree of the isogeny.

So, the map from $x,y$ to $u,v$ works as you expect because the point on edwards448 was specifically chosen to match, but the inverse map will move you to $4*P$ and not to $P$.

Here's the sage code that use your formulas to get the Edwards coordinate of $4^{-1}G$ that matches the point on Edwards

#define the Montgomery curve. Montgomery curves are natively supported in sage so better to use this instead of Edwards
p = 2^448-2^224-1
F = GF(p)
d = -39081
E = EllipticCurve(F,[0,2-4*d,0,1,0])
#define the base point on Montgomery
curve448_basepoint = E([5,355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362])

#define the order of the point
order = 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

#Multiply the generator by 4^-1
P = curve448_basepoint*inverse_mod(4,order)

#now use your formulas to get the edwards coordinates
def getX(u,v):
    x = 4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1)
    return x

def getY(u,v):
    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)
    return y

#and verify it matches the expected value (the point multiplied by 4)
assert getX(P.xy()[0],P.xy()[1])==224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710
assert getY(P.xy()[0],P.xy()[1])==298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660
$\endgroup$
6
  • $\begingroup$ Great, curve enthusiast. $\endgroup$
    – kelalaka
    Sep 8 at 16:06
  • $\begingroup$ thank-you, Ruggero! $\endgroup$
    – user61836
    Sep 8 at 17:46
  • $\begingroup$ I wonder if it would be better to write $4^{-1} G$ rather than $-4 G$? $\endgroup$
    – user61836
    Sep 8 at 19:01
  • $\begingroup$ @user61836 Ruggero uses additive notation, not multiplication since, in general, we say point addition and scalar multiplication that is just adding $k$ time ( usually written as $[k]P$ ), and the addition comes from the lattices... $\endgroup$
    – kelalaka
    Sep 8 at 23:56
  • $\begingroup$ The standard notation is to write -4 G to indicate the point that is the additive inverse of 4 G in the ec group (so that -4 G + 4 G = id), but that is not what is meant here. I think writing 4^{-1} G would be clearer. $\endgroup$
    – user61836
    Sep 9 at 0:15
0
$\begingroup$

The code below complements Ruggero's answer.

Ruggero explained that the given isogeny, curve448 --> edwards448, is a 4-isogeny, as is stated in RFC 7748.

When it is applied to a point on curve448, it returns 4 times a point on edwards448.

Ruggero's sage code shows that 4^{-1}*(Gu,Gv) maps to (Gx,Gy).

The code below shows that (Gu, Gv) maps to 4*(Gx,Gy):

p =  2**448 - 2**224 - 1
d = -39081
a = 1

def getX(u,v):
    x = mod(4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1), p)
    return x

def getY(u,v):
    y = mod(-(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)
    return y

Gx = 224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710
Gy = 298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660

Gu = 5
Gv = 355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362

# edwards448 addition/double
def add(x1,y1,x2,y2):
    x3 = mod((x1*y2+y1*x2)/(1+d*x1*x2*y1*y2),p)
    y3 = mod((y1*y2-a*x1*x2)/(1-d*x1*x2*y1*y2),p)
    return x3,y3

twoGx, twoGy = add(Gx,Gy,Gx,Gy)
fourGx, fourGy = add(twoGx, twoGy, twoGx, twoGy)

X = getX(Gu,Gv)
Y = getY(Gu,Gv)

print(X==fourGx)
print(Y==fourGy)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.