给定Edward曲线和x的参数，如果存在y值，则确定y值

Question

我正在使用ECC 密码体制制作一个演示ElGamal。我目前有一个爱德华曲线操作的工作实现和一个基本的ElGamal实现(只加密曲线上的点)，为了执行这个答案中描述的映射操作，我需要确定爱德华曲线上给定一个x的点的y值。我对爱德华曲线的工作方式有一个基本的理解，但是有限域对我有信心在直觉的基础上正确地实现这一点。任何帮助都是非常感谢的。

Answer 1

爱德华兹曲线的方程是x^2 + y^2 = 1 + dx^2y^2。假设您知道曲线参数，那么，假设您知道x，那么您正在解一个未知的方程，即y。我们可以在一个未知数中把它重写为一个二次方程，然后求解它。注意，所有操作都是\bmod{p}，其中p是曲线所定义的字段的特征(请记住，除以z等于乘以z^{-1}\bmod{p}，平方根也有不同的规则)。

x^2 + y^2 = 1 + dx^2y^2 y^2 - dx^2y^2 + x^2 - 1 = 0 (1 - dx^2)y^2 + (x^2 - 1) = 0

现在让a = (1 - dx^2)，b = 0，和c = (x^2 - 1) (所以我们有ay^2 + by + c = 0，也就是一个二次方程)。请注意，您还可以在上面的方程中移动一些项，最后得到相同的结果。

y = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} y = \frac{-0 \pm \sqrt{0 - 4(1 - dx^2)(x^2 - 1)}}{2(1 - dx^2)} y = \frac{\pm \sqrt{-4(1 - dx^2)(x^2 - 1)}}{2(1 - dx ^2)} y = \pm \sqrt{\frac{1 - x^2}{1 - dx^2}}

现在用x和d代替。请注意，该方程有两个解。如果x坐标没有某种编码来指示应该使用哪个y值，就不可能恢复“正确”的y，因为这两个值都会产生不同的有效点。