從 X 座標找到 Ed25519 Y 座標

是否有任何可用的公式來確定 $ Y $ 座標僅給出 $ X $ 對於 Ed25519 曲線？我找到的最接近的東西是https://www.rfc-editor.org/rfc/rfc8032.html#section-6recover_x(y, sign)的 EdDSA RFC 中的函式

---

編輯：使用@kelalaka 的步驟，我實現了這個python程式碼，但它似乎缺少一些不正確的東西：

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

1. 得到曲線方程$$ -x^2 + y^2 = 1 - \frac{121665}{121666}x^2y^2 $$
2. 稱呼 $ d = \frac{121665}{121666} $ $$ -x^2 + y^2 = 1 - dx^2y^2 $$
3. 拿 $ y^2 $ 向左 $$ y^2 + dx^2y^2 = 1 + x^2 $$
4. 拿 $ y^2 $ 括號外 $$ y^2( 1+ dx^2) = 1 + x^2 $$
5. 劃分$$ y^2 = \frac{1 + x^2}{( 1+ dx^2)} $$這是可能的，因為 $ 1+ dx^2 $ 不為零。

拿 $ -1 = dx^2 $ . 自從 $ p \equiv 1 \pmod 4 $ 然後 $ -1 $ 是一個 $ QR $ . $ d $ 被選為非正方形 $ (QNR) $ 因此平等是不可能的。 6. 插頭 $ x $ 和 $ d $ 去尋找 $ y^2 $ 7. 尋找 $ y $ 通過取平方根模 $ 2^{255}-19 $ . 這將遺漏一兩個可能的解決方案。

模數等於 5 模 8 時的平方根

自從 $ 2^{255}-19 \equiv 5 \pmod{8} $ 我們可以使用特殊公式代替 Tonelli-Shanks $ r^2 = a $ ;

1. 計算平方根 $ -1 $

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

2. 計算平方根

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

---

用於計算的 Sagemath $ Y $ 給定 $ X $ 協調

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)

此程式碼計算基點，輸出為

yp=  46316835694926478169428394003475163141307993866256225615783033603165251855960
yn=  11579208923731619542357098500868790785326998466564056403945758400791312963989
y =  46316835694926478169428394003475163141307993866256225615783033603165251855960

更正後的 Python 程式碼（版本 >= 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))

引用自：https://crypto.stackexchange.com/questions/101961