給定 Edward 曲線和 x 的參數，確定 a 值（如果存在）
我正在使用 ECC ElGamal製作展示密碼系統。我目前有一個愛德華曲線操作的工作實現和一個基本的 ElGamal 實現（只加密曲線上的點），為了執行這個答案中描述的映射操作，我需要確定 $ y $ 愛德華曲線上一點的值 $ g $ 給定一個 $ x $ . 我對愛德華曲線的工作方式有一個基本的了解，但是有限域對我來說有點太多了，我有信心根據直覺正確地實現這一點。任何幫助表示讚賞。
愛德華茲曲線的方程是 $ 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，因為這兩個值都會導致不同的有效點。