0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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

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.