7
$\begingroup$

I have some misunderstanding about EdDSA conversion coordinates between Montgomery curve and twisted Edwards curve. In https://tools.ietf.org/html/rfc7748 I see that a base point for Curve25519 is

Montgomery curve:

U(P)  9
V(P)  14781619447589544791020593568409986887264606134616475288964881837755586237401

Twisted Edwards curve:

X(P)  15112221349535400772501151409588531511454012693041857206046113283949847762202
Y(P)  46316835694926478169428394003475163141307993866256225615783033603165251855960

and then I see

The birational maps are:

$(u, v) = \frac{1+y}{1-y}, \sqrt{-486664}*\frac{u}{x}$

$(x, y) = \sqrt{-486664}*\frac{u}{v}, \frac{u-1}{u+1}$

But if we try convert $(x,y)$ to $(u,v)$ or $(u,v)$ to $(x,y)$ by using these formulas, we will not get correct answers. For example convert y-coordinate to u-coordinate:

(1+46316835694926478169428394003475163141307993866256225615783033603165251855960)/(1-46316835694926478169428394003475163141307993866256225615783033603165251855960)

result will not be equal to

14781619447589544791020593568409986887264606134616475288964881837755586237401

How can I convert coordinates between Montgomery curve and twisted Edwards curve correctly?

$\endgroup$
10
$\begingroup$

The formulas actually work. You just have to keep in mind to make computation in the field of intergers modulo $2^{255}-19$ and that there are actually two square roots, you need to use the right one if you want to have the expected result.

You can test the following SAGE code

gf=GF(2^255-19)
X_P = gf(15112221349535400772501151409588531511454012693041857206046113283949847762202)
Y_P = gf(46316835694926478169428394003475163141307993866256225615783033603165251855960)
u = (1+Y_P)/(1-Y_P) 
v = gf(-486664).sqrt()*u/X_P,-(gf(-486664).sqrt())*u/X_P
print u
print v

on the Sage Cell server.

$\endgroup$
1
$\begingroup$

You operations have to be modulo $p$ where $p=2^{255}-19$ because you are working in $\mathbb{F}_p$.

$\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.