曲线25519 (X25519，Ed25519)转换蒙哥马利曲线和扭曲爱德华兹曲线之间的坐标

Question

我对蒙哥马利曲线和扭曲爱德华兹曲线之间的EdDSA转换坐标有一些误解。在https://www.rfc-editor.org/rfc/rfc7748中，我看到Curve25519的一个基点是

蒙哥马利曲线：

U(P)  9
V(P)  14781619447589544791020593568409986887264606134616475288964881837755586237401

扭曲的Edwards曲线：

X(P)  15112221349535400772501151409588531511454012693041857206046113283949847762202
Y(P)  46316835694926478169428394003475163141307993866256225615783033603165251855960

然后我看到了

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}

但是，如果我们尝试使用这些公式将(x,y)转换为(u,v)或将(u,v)转换为(x,y)，我们将得不到正确的答案。例如，将y坐标转换为u坐标：

(1+46316835694926478169428394003475163141307993866256225615783033603165251855960)/(1-46316835694926478169428394003475163141307993866256225615783033603165251855960)

结果将不等于

14781619447589544791020593568409986887264606134616475288964881837755586237401

如何正确转换蒙哥马利曲线与扭曲爱德华兹曲线之间的坐标？

Answer 1

公式实际上是有效的。您只需记住，在intergers模块2^{255}-19中进行计算，并且实际上有两个平方根，如果您想要得到预期的结果，就需要使用正确的平方根。

您可以测试以下SAGE代码

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

在Sage单元服务器上。

Answer 2

注意，你做的是直接除法，而不是模逆。

由于椭圆曲线算法中没有除法，所以需要进行模逆。这里可以使用pow函数作为助手；它使用第三个参数作为模数：

>>> P = 2 ** 255 - 19
>>> X = 15112221349535400772501151409588531511454012693041857206046113283949847762202
>>> Y = 46316835694926478169428394003475163141307993866256225615783033603165251855960
>>> mod_inverse = lambda x: pow(x, P - 2, P)
>>> # we are replacing `/ 1 - Y` with `* inverse(1 - Y)`
>>> ((1 + Y) * mod_inverse(1 - Y)) % P
9