RFC-6090 點倍增公式在齊次座標中的適用性

我正在參考RFC-6090來實現橢圓曲線密碼學的愛好者。

我選擇了一個無異常（答案指向本文）的公式來添加和思考——我只使用生成器點和經過驗證的公鑰的點加倍，我可以使用高效但不是非常通用的方法點倍增公式。

作為不熟悉高等數學的人，想必也有人想知道，問：3.1節的倍增公式的適用性是什麼？RFC-6090？它可以與a）不是無限遠點的所有有效曲線點，b）在所有可以表示為的曲線上工作 $ y^2 = x^3 + ax + b $ ?

b) 在所有可以表示為的曲線上 $ y^2 = x^3 + ax + b $ ?

橢圓曲線的形式 $ y^2 = x^3 + ax + b $ 稱為短 Weierstrass 方程（形式）。這個簡短的形式是從（一般 Weierstrass 方程 ）$$ Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6 $$通過變數的變化（轉換）如果特徵 $ p $ 領域的 $ p>3 $ . 通過這樣做，我們得到一條同構曲線，並且操作是可逆的。

3.1節中的點倍增公式的適用性是什麼。RFC-6090？它可以與所有不是無限遠點的有效曲線點一起工作嗎？

射影座標的算術

在投影座標中，方程為 $ E $ 是

$$ Y^2 Z = X^3 + AXZ^2 + BZ^3. $$

• 一個點 $ (X_1 : Y_1 : Z_1 ) $ 上 $ E $ 對應於仿射點 $ (X_1/Z_1,Y_1/Z_1) $ 什麼時候 $ Z_1 \neq 0 $
• 什麼時候 $ Z_1 $ 我們有無窮遠點 $ P_\infty = (0:1:0) $ 它在仿射座標上沒有表示。
• 點的相反（負） $ (X_1 : Y_1 : Z_1 ) $ 是 $ (X_1 : -Y_1 : Z_1 ) $

讓 $ P_i = (X_i : Y_i : Z_i ), i = 1, 2 $ , 是均質化橢圓曲線上的點

然後 $$ (X_1 : Y_1 : Z_1 ) + (X_2 : Y_2 : Z_2 ) = (X_3 : Y_3 : Z_3 ). $$

橢圓和超橢圓曲線密碼學手冊中的公式

• 加法公式 $ P_1 \neq \pm P_2 $ 12M+2S；

  • $ A = Y_2 Z_1 − Y_1 Z_2, $
  • $ B = X_2 Z_1 − X_1 Z_2, $
  • $ C = A^2 Z_1 Z_2 − B^3 − 2B^2 X_1 Z_2, $ 然後

  $$ X_3 = BC, \quad Y_3 = A(B^2 X_1 Z_2 − C) − B^3 Y_1Z_2, \quad Z_3 = B^3 Z_1 Z_2 $$

• 倍增公式 $ P_1 = P_2 $ 7M+5S；

  • $ A = a Z_1^2 + 3X_1^2, $
  • $ B = Y_1 Z_1, $
  • $ C = B X_1 Y_1, $
  • $ D = A^2 − 8 C, $

  $$ X_3 = 2BD, \quad Y_3 = A(4C − D) − 8Y_1^2 B^2 , \quad Z_3 = 8 B^3. $$

RF9060 公式

RFC 顯示了一個用於添加和加倍的虛擬碼（有一個勘誤表，這裡表示了更正的版本）；

令 P1=(X1,Y1,Z1) 和 P2=(X2,Y2,Z2) 是橢圓曲線上的點，並且讓 u = Y2 * Z1 - Y1 * Z2 和 v = X2 * Z1 - X1 * Z2。

我們觀察到點 P1 和 P2 相等當且僅當 u 和 v 都等於 0。否則，如果 P1 或 P2 等於無窮遠點，則 v 為零且 u 非零（但相反的含義不成立）。

if P1 is the point at infinity,
   P3 = P2
else if P2 is the point at infinity,
   P3 = P1
else if P1=-P2 as projective points
   P3 = (0,1,0)
else if P1 does not equal P2
   X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
   Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
   Z3 = v^3 * Z1 * Z2
else    // P2 equals P1, P3 = P1 * P1
    w = 3 * X1^2 + a * Z1^2
   X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
   Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
   Z3 = 8 * (Y1 * Z1)^3

必須使用方程式來了解特殊情況 $ P_\infty $ 是需要的。而且，是的，它適用於除 $ P_\infty $ . 這是在虛擬碼的前兩個步驟中處理的。

---

注 1：此 RFC 使用產品來進行必須注意的點添加。橢圓曲線中沒有積，我們有點加法和標量乘法。這些點在點加法和通常的標量乘法下形成一個阿貝爾群，我們只能有 Z-Module。

注 2：RFC6090 公式的成本與手冊相同。

注 3：兩個公式都經過 SageMath 驗證，根據 SageMath 的公式它們是正確的。在測試 Curve25519 時使用。使用neuromancer的程式碼可以很容易地改變這一點

注 4：刪除特殊情況 $ P_\infty $ 然後看到結果不正確（大多數時候由於結果不是曲線上的點而失敗）

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