3
$\begingroup$

Are there any available formulas to determine a $Y$ coordinate given only an $X$ for the Ed25519 curve? The closest thing I've come to find is the recover_x(y, sign) function in the EdDSA RFC at https://www.rfc-editor.org/rfc/rfc8032.html#section-6


Edit: Using @kelalaka 's steps, I implemented this python code, but it seems to be missing something as its incorrect:

p = 57896044618658097711785492504343953926634992332820282019728792003956564819949 # 2**255 -19
d=(121665 * pow(121666, -1, p)) # had to mod inverse parts of d

def get_y(x):
   a = 1 + x**2 # top line
   b = 1 + d*(x**2) # bottom line
   c = a * pow(b, -1, p) # calculation
   return math.isqrt(c) % p # finding y

f = G * 2

print(f.y) # this is correct
# Output is 15549675580280190176352668710449542251549572066445060580507079593062643049417
print(get_y(f.x)) # this is incorrect
# Output is 25882070986792651040465013186999776942933444728837758367190487200702647909051
$\endgroup$
3
  • $\begingroup$ @kelalaka I'm aware of the curve equation but it leaves a square of y on both sides that I'm not exactly sure how to solve... $\endgroup$
    – J Medeiros
    Sep 20 at 10:02
  • $\begingroup$ @kelalaka that was my second guess, but if you read carefully the y co-ordinate is recovered from clearing the first bit of the encoded point, not from an x value. My situation is that I have an X, and want to find it's Y. $\endgroup$
    – J Medeiros
    Sep 20 at 10:25
  • 4
    $\begingroup$ At least the code fragment math.isqrt(c) % p # finding y is wrong. See e.g. this or this for a simple mathematical method. While your way to post your code (as a single block at the end of the question) is OK to me, I want to point the possibility of instead posting it as a link to tio.run [python 3.8 (pre-release)] or a similar website, preferably in a state such that it can run. Often, that even fits a comment. $\endgroup$
    – fgrieu
    Sep 20 at 11:33

1 Answer 1

6
$\begingroup$
  1. Get the curve equation $$-x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2$$

  2. Call $d = \frac{121665}{121666}$ $$-x^2 + y^2 = 1 - dx^2y^2$$

  3. Take $y^2$ to left $$y^2 + dx^2y^2 = 1 + x^2$$

  4. Take $y^2$ out of parenthesis $$y^2( 1+ dx^2) = 1 + x^2$$

  5. Divide $$y^2 = \frac{1 + x^2}{( 1+ dx^2)}$$ this is possible since $1+ dx^2$ is not zero.

    take $-1 = dx^2$. Since $p \equiv 1 \pmod 4$ then $-1$ is a $QR$. $d$ is chosen to be non-square $(QNR)$ therefore equality is impossible.

  6. Plug $x$ and $d$ to find $y^2$

  7. Find $y$ by taking square roots modulo $2^{255}-19$. this will leave out one or two possible solutions.

Square root when modulus congruent to 5 modulo 8

Since $2^{255}-19 \equiv 5 \pmod{8} $ instead of Tonelli-Shanks we can use special formula for $r^2 = a$;

  1. compute the square root of $-1$

    • $u \equiv (2a)^{(p-5)/8} \pmod{2^{255}-19}$
    • $i \equiv 2au^2 \pmod{2^{255}-19}$
  2. compute the square root

    • $ r = \pm au(i-1)\pmod{2^{255}-19}$

Sagemath for calculation $Y$ given $X$ coordinate

p = 2^255-19

#d = 121665 * 121666
dd =  inverse_mod(121666, p)
d = mod(121665 * dd,p)

x = mod(15112221349535400772501151409588531511454012693041857206046113283949847762202,p)
y = mod(46316835694926478169428394003475163141307993866256225615783033603165251855960,p)

a = mod( (1 + x^2) / (1 +d*x^2), p)


v = mod((p-5)/8,p-1)
u = mod( (2*a)^(v) ,p) 
i = mod( 2*a*u^2, p)

yp = mod( a*u*(i-1),p)
yn = mod( -yp ,p)

print("yp= ", yp)
print("yn= ", yn)
print("y = ", y)

This code calculates for the base point, and the output is

yp=  46316835694926478169428394003475163141307993866256225615783033603165251855960
yn=  11579208923731619542357098500868790785326998466564056403945758400791312963989
y =  46316835694926478169428394003475163141307993866256225615783033603165251855960

The corrected Python code ( version >= 3.8 )

import math

def get_y(x,p,d):
        
   a = (1 + x**2 ) * pow((1 + d*(x**2) ), -1, p)
   
   %Modulo square root part
   v = (p-5)//8 % (p-1)

   u = pow( 2*a,v, p) 
   i = 2*a*u**2 % p

   yp = a*u*(i-1) %p
   yn = -yp %p

   return (yp,yn)# finding y


x = 15112221349535400772501151409588531511454012693041857206046113283949847762202

p = 2**255 -19

d =(121665 * pow(121666, -1, p)) % p# had to mod inverse parts of d

print("X = " , get_y(x,p,d))

$\endgroup$
5
  • $\begingroup$ I'll write a sample Sagemath code (later!)! $\endgroup$
    – kelalaka
    Sep 20 at 10:45
  • 1
    $\begingroup$ view my edited question for my code attempt, I wasn't able to put my code in a comment, sorry $\endgroup$
    – J Medeiros
    Sep 20 at 11:10
  • $\begingroup$ @JMedeiros I'm not sure if pow(x, -1, p) calculates the multiplicative inverse in finite field, but if you want to be sure, use pow(x, p-2, p) (per Fermat's theorem) $\endgroup$
    – DannyNiu
    Sep 20 at 13:19
  • 1
    $\begingroup$ @DannyNiu: you are right not to be sure: pow(x, -1, p) calculates the multiplicative inverse of x modulo p, or not, depending on the version of Python. In the official build, that's starting with version 3.8, per the doc for pow. $\endgroup$
    – fgrieu
    Sep 20 at 15:45
  • $\begingroup$ @JMedeiros with a little work, I've corrected your code... $\endgroup$
    – kelalaka
    Sep 20 at 18:53

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.