具有仿射/投影座標的蒙哥馬利階梯

所以我試圖理解為什麼蒙哥馬利算術很快以及蒙哥馬利階梯是什麼。

通過這篇文章，我了解了基本的仿射算術和梯形圖。

所以這並不比常見的weierstrass方程的算術快。在Montgomery的原始論文中，他定義了加法和加倍的投影算術。

我的第一個問題是：由於沒有除法，投影算術是否更快？梯子是否有恆定的時間，因為沒有劃分？這是否意味著具有仿射座標的梯子沒有恆定的時間？（我的想法是，欄位中的除法是乘以逆。為了計算逆，你需要 euklidiean 算法。這種算法不是最快的，不能在恆定時間內計算）

然後我正在研究伯恩斯坦的工作。在這篇論文和他的 Curve25519中，他描述了一個優化的雙加公式。它看起來像這樣：

當我做對時，您可以使用蒙哥馬利梯子進行仿射算術的仿射座標和投影座標的投影座標。因此，Bernstein 製作了投影蒙哥馬利階梯圖，以提供優化的實現，其中再次使用已經計算的結果。所以我嘗試將圖形寫入虛擬碼：

R0 = (0,0)
R1 = (x,y)
x1 = 
   for i from m downto 0 do:
       if xi = 0 then:
           x,z,x',z' =  R0[0], R0[1], R1[0], R1[1]
           tmp1, tmp2 = x, x'

           x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

           x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
           tmp1, tmp2 = x, x'

           x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

           z = z*( tmp1 + ((A-2)/4)*z )
           x' = x' * x'
           z' = z' * z' * x1

           R0[0], R0[1], R1[0], R1[1] = x, z, x' , z'
       else
           x,z,x',z' =  R1[0], R1[1], R0[0], R0[1]
           tmp1, tmp2 = x, x'

           x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

           x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
           tmp1, tmp2 = x, x'

           x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

           z = z*( tmp1 + ((A-2)/4)*z )
           x' = x' * x'
           z' = z' * z' * x1

           R0[0], R0[1], R1[0], R1[1] = x',z',x, z
return R0

這讓我想到了下一個問題：x1 是從哪裡來的，它是如何計算的？我在他的論文中看到 x1/z1 = X(Q - Q’)，但仍不清楚如何減去這些點。

下一個問題是：這個虛擬碼邏輯是否正確（至少除了 x1 之外的所有內容）？

我希望這不是太多問題！

也許有一天有人再次找到這個文章並且有同樣的問題。致你：我希望你今天過得愉快！

1. 問題：投影算術更快，因為只有乘法，平方，加法要做。仿射 Artihmetic 較慢，因為計算除法需要大量時間。特別是對於現代密碼學中使用的大數字。但是：這不是恆定時間階梯的答案。是的，除法的仿射座標不能用常數時間計算，但投影梯的原因是不同的。您可以將不同類型的橢圓曲線轉換為射影形式，但對於它們，您不能總是使用蒙哥馬利階梯。很長一段時間（至少在 montgomery 發表他的作品時），weierstraß 上的橢圓曲線標量乘法只能使用雙倍和相加算法。這些算法將標量轉換為二進制形式，並對 1 和 0 進行不同的操作。因此，可以估計出 1 和 0 的數量。蒙哥馬利階梯對兩者都有相同的操作。所以時間上沒有區別。
2. 問題：對於投影座標，只能添加/加倍同一點的倍數。蒙哥馬利階梯以給定的標量開始 $ n $ 和點 $ P $ . 在每個步驟中計算兩個結果 $ R0 $ 和 $ R1 $ . 這裡重要的一點是，這些結果要麼是以下形式 $ (n’)R0 $ , $ (n’+1)R1 $ 或者 $ (n’+1)R0 $ , $ (n’)R1 $ . 這意味著它們之間的差異始終為 1。（當您查看射影算術的定義時，很清楚這意味著什麼）。對於梯子，這意味著， $ x1 $ 始終是起點的 x 座標 $ P $ . 因此它總是相同的，不能計算！

注意：我仍然不能說我的虛擬碼是否正確。

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