使用投影座標的安全橢圓曲線點加法：如何判斷點是否相同？
我正在嘗試在硬體中為 NIST p256 和 p384 曲線實現橢圓曲線點加法。我注意到建議的 NIST 常式存在以下問題：
考慮http://www.nsa.gov/ia/_files/nist-routines.pdf的常式 2.2.7 ：加點 $ R = S + T $ 對案件無效 $ S = T $ （這將是一個點加倍）。
- 是否說在進行加點之前必須先檢查兩個點是否為同一點，如果它們是同一點則執行點加倍而不是？如果是這樣，您如何測試點是否相同？
- 我使用雅可比座標進行中間計算，因此給定點可能有大量全等表示： $ (x,y) \mapsto (x/Z^2,y/Z^3,Z) $ ，例如 $ (16,64,1) \equiv (4,4,2) \equiv (p+16, p+64,1)\equiv\dots $ .
如果兩個點有大量可能的表示，如何確定它們是否相同？
一種天真的方法可能是在執行點加法之前轉換回仿射座標並將所有座標減少到範圍 $ 0 \leq x < p $ 所以兩個點都有一個唯一的表示，但這違背了使用投影座標的目的，即在中間計算期間避免模逆。在這種情況下，最好在仿射座標中進行所有計算。必須有一種更簡單的方法來測試是否 $ S \equiv T $ 不這樣做，但我沒有找到很多關於這個問題的參考資料。這在現實世界中是如何處理的？
除了使用雅可比座標之外，我所有的中間結果都不受 $ 0 \leq n < p $ 而是以 $ 0 \leq n < M*p $ 在哪裡 $ 1 \leq M < 2^r $ 這是因為我的模乘算法沒有造成問題，除非試圖確定兩點是否一致。這將仿射座標中的搜尋空間增加到 $ M $ 可能的一致點。
是否存在用於廣義曲線的安全加法算法？
Inb4 使用 Edwards 曲線：我需要支持 NIST p256 和 p384 曲線，所以我不能選擇任意曲線。
您連結到的常式已經在執行該檢查（第 15-17 行）：它返回 $ (0,0,0) $ 什麼時候 $ S $ 和 $ T $ 是相等的，呼叫者應該通過呼叫加倍常式來處理這個問題。
相等性驗證是通過檢查是否
$$ X_1Z_2^2 - X_2Z_1^2 = 0 $$ $$ Y_1Z_2^3 - Y_2Z_1^3 = 0 $$ 很容易看出，因為 $ x = X/Z^2 $ 和 $ y = Y/Z^3 $ ，上述等式僅在點相等時成立。確實，如果兩個點都不是無窮大，
$$ X_1/Z_2^2 - X_2/Z_1^2 = \frac{X_1Z_1^2-X_2Z_2^2}{(Z_1Z_2)^2}, $$ $$ Y_1/Z_2^3 - Y_2/Z_1^3 = \frac{Y_1Z_1^3-Y_2Z_2^3}{(Z_1Z_2)^3}. $$ 我們可以放心地忽略分母，因為結果是 $ 0 $ 當且僅當分子是 $ 0 $ .
雖然這個實現是正確的，但我不認為它是安全的；時間或功率使用資訊可用於學習密鑰。這是對可能發生的事情以及應對它的可用選項的一個很好的概述。
對於我的軟體“學術簽名”，這裡的程式碼片段解釋了這種必要的相等性檢查。對比 Bernstein 和 Lange 的陳述，這種檢查可以很容易地以一種非常有效的方式完成。
如果您查看開原始碼並在模組“elliptic1.cpp”中搜尋常式“int proj_jacobian::add(proj_jacobian* summand, ellipse* ewp)”，您可以查看我實現的完整常式。