Elliptic-Curves

有限域上橢圓曲線的加法:如果 X_1 = X_2 和 Y_1 != Y_2 會怎樣?

  • June 15, 2022

給定以下曲線:

$$ y^3 = x^2 - 7x $$

在有限域上 $ GF(271) $ .

我們有 $ P = (201, 247) $ 屬於曲線:

$$ 247^2 \equiv 201^3 - 7 \cdot 201 \equiv 34 \mod 271 $$

我們還有 $ Q = (201, 24) $ 屬於曲線:

$$ 24^2 \equiv 201^3 - 7 \cdot 201 \equiv 34 \mod 271 $$

那麼,如何添加 $ R = P+Q $ ? 據我所知,擁有 $ m=271 $ :

  • 如果 $ P=Q $ , 然後 $ t = (3x^2+a)/(2y) \mod m $ , 在哪裡 $ 1/(2y) = (2y)^{-1} \mod m $
  • 如果 $ P \neq Q $ , 然後 $ t = (y_q - y_p)/(x_q - x_p) $ , 在哪裡 $ 1/(x_q - x_p) = (x_q - x_p)^{-1} \mod m $

然後

$$ x_r = t^2 - x_p - x_q \mod m $$

和:

$$ y_r = t(x_p-x_r) - y_p \mod m $$

但是,在這種情況下,我們將除以零,因為 $ P \neq Q $ 和 $ x_p = x_q $ . 如何進行?

明顯的錯誤是坡度。兩點在同一垂直線上。的確, $ P = -Q $ 他們的總和就是群體身份。

這需要仿射座標的特殊情況;

  • 如果 $ x_1 = x_2 $ 和 $ y_1 = - y_2 $ , 那是 $ Q =(x_2,y_2)=(x_1,−y_1)=−P $ , 然後$$ P+Q = P + (-P) = \mathcal{O} $$

在你的情況下 $ 247 + 24 = 271 $ 所以 $ x_1 = x_2 $ 和 $ y_1 = -y_1 $ .


附錄

下面是這條曲線的圖表;

在此處輸入圖像描述

正如我們所見, $ P $ 和 $ Q $ 在同一條垂直線上,到中心線的距離相同(黑色)

用於驗證和繪製曲線的 Sagemath 程式碼。

p = 271
a = -7
b = 0

K = GF(p)
E = EllipticCurve(K,[a,b])
print(E)

P = E(201,247)
Q = E(201,24)
R = P+ Q
print(R)

plotE = E.plot()
plotE += line([(0,136),(272,136)],color='black')
plotE += line([(201,24),(201,247)],color='blue')
plotE += point([201,247], color='red')
plotE += point([201,24], color='red')
plotE += text("P",(201,255), color='red')
plotE += text("Q",(201,18), color='red')

plotE

引用自:https://crypto.stackexchange.com/questions/100587