I'm making a demonstration cryptosystem using ECC ElGamal. I've currently got a working implementation of Edward's Curve operations and a basic ElGamal implementation (Encrypts only points on the curve), and in order to perform the mapping operation described in this answer, I need to determine the $y$ value of a point on an Edward's curve $g$ given an $x$. I have a basic understanding of the way an Edward's curve works but the finite fields are a bit much for me to be confident in properly implementing this based on intuition. Any help is appreciated.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
The equation for an Edwards curve is $x^2 + y^2 = 1 + dx^2y^2$. Assuming you know the curve parameters then, given that you know $x$, you are solving the above equation for one unknown, namely $y$. We can rewrite this as a quadratic equation in one unknown and solve it. Note that all operations are $\bmod{p}$ where $p$ is the characteristic of the field the curve is defined over (remember that dividing by $z$ is equivalent to multiplying by $z^{-1}\bmod{p}$, square roots also have different rules).
$$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$$
Now let $a = (1 - dx^2)$, $b = 0$, and $c = (x^2 - 1)$ (so we have $ay^2 + by + c = 0$ i.e. a quadratic equation). Note that you can also move some terms around in the upper equation and end up at the same result.
$$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}}$$
Now substitute in $x$ and $d$. Note that there are two solutions to the equation. Without your x coordinate having some sort of encoding that indicates which y value should be used it is impossible to recover the "correct" y as both values result in distinct valid points.
answered Oct 9 '18 at 22:59
-
$\begingroup$ Thank you! When you say all operations are mod p, does that mean every operation I do in the final equation has to be mod p $\endgroup$ – ThePlasmaRailgun Oct 9 '18 at 23:05
-
$\begingroup$ This doesn't appear to be an appropriate solution for extremely large values of d or x, Python's sqrt operator returns an overflow error. $\endgroup$ – ThePlasmaRailgun Oct 10 '18 at 1:17
-
$\begingroup$ Well in this case the square root is a modular square root (since it's in a field), which is different than pythons sqrt function (which additionally operates on floats not integers, the max value that a float can represent is usually much less than the values numbers take in a cryptographic context). Use Tonelli-Shanks to find square roots in the context of modular arithmetic. $\endgroup$ – puzzlepalace Oct 10 '18 at 5:51
-
$\begingroup$ Thanks, just figured that out before you posted. However, it's currently very slow because I'm calulating for each x value what the y value is if it exists. Is there a similar check to just see if a y value exists in a way that is faster than calculating the y value? $\endgroup$ – ThePlasmaRailgun Oct 10 '18 at 18:42
-
1$\begingroup$ It'll boil down to finding out whether the term $\frac{1 - x^2}{1 - dx^2}$ has a modular square root. See this math SE answer for more details. $\endgroup$ – puzzlepalace Oct 11 '18 at 20:44
