基於蒙哥馬利階梯的標量乘法的優點
我不太明白使用蒙哥馬利梯形算法進行標量乘法的最大優勢是什麼？
有人可以幫我嗎？
綜合來說，蒙哥馬利梯的優點是簡單快速。
如果您查看 X25519，即應用於 Curve25519 並在RFC 7748中描述的 Diffie-Hellman 算法，您將看到對於n位蒙哥馬利曲線，將一個點與一個n位標量相乘，您將需要計算大約10n 次乘法欄位元素。更詳細地說，一個循環有n次迭代，每一次迭代都意味著：
- 具有兩個不同欄位元素值的 4 次乘法
- 4個平方
- 1 乘以一個固定且通常很小的常數（
a24在 RFC 中稱為）- 1 與基點“u”座標相乘（在整個算法中固定，但在呼叫之間可能會有所不同）
為此，必須添加最終欄位反轉，這通常通過模冪運算完成。如果場模數選擇得當，則該反轉將添加多於n次平方。所以上面給出的“10”的值是一個估計值，它取決於如何優化常數的平方和乘法；在實踐中，總成本將在8n和12n之間。
現在，對於帶有 Weierstraß 方程 y 2 = x 3 - 3x + b的“經典”曲線（對於某些常數b），通常的實現方法是使用雅可比座標，其中一個點 ( x , y ) 由三元組表示( X , Y , Z ), 有:
- x = X / Z 2
- y = Y / Z 3
使用這種表示法，點加倍需要 8 次乘法（其中 4 次是平方），而不是加倍的點加法需要 16 次乘法（其中 4 次是平方）。然後，一個基本的加倍算法將需要平均每個乘法器位 16 次乘法，但如果您想要一個恆定時間實現（推薦），實際上需要 24 次，因此不會洩漏有關哪些標量位為 0 以及哪些位為 0 的資訊是 1。總共要添加額外的n次乘法，以使**Z的最終反轉返回仿射座標（再次，經典地使用模冪）。
可以通過視窗優化來加快速度，對於基點P ，您可以預先計算**P的小倍數；例如，對於一個 5 位的視窗，您計算從 0 到 31的所有k的**kP（這涉及 15 次加倍和 15 次加法），然後每 5 次加倍只進行一次加法。這需要一些額外的實現注意（例如，如果需要恆定時間執行，則在視窗中進行恆定時間查找），但可以將總成本降低到大約13n場乘法，即比蒙哥馬利曲線多 30%。當預先知道基點時，可能會進一步加速，例如 Diffie-Hellman 的前半部分（使用傳統的基曲線），因為當一個點具有Z = 1時，投影座標中的加法公式（稱為“混合加法”）稍微簡單一些（11 次乘法而不是 16 次）。
因此，在實踐中，蒙哥馬利曲線獲得了速度優勢，但並不是因為它們是蒙哥馬利曲線：
- 如上圖所示，優勢微乎其微（約 30%）。但是，必須說，蒙哥馬利曲線的實現要容易得多，而且它顯示為更小的程式碼和更少的棘手錯誤空間。
- Curve25519 比 NIST 曲線 P-256 更大的加速來自基場的定義。NIST P-256 使用整數模p = 2 256 - 2 224 + 2 192 + 2 96 - 1。Curve25519 使用p = 2 255 - 19。兩者都是整數，因為它們允許更快的模減少；但是，NIST 的選擇針對 1980 年代後期的電腦硬體進行了優化，而 Curve25519 則針對 2000 年代中期的硬體進行了優化，具有更便宜的乘法操作碼和超標量架構。在現代硬體（包括現代“小型”嵌入式 CPU）上，後一種選擇似乎比 NIST 的模數快大約兩倍。
- Curve25519 的一個額外有趣的特性是它不是一條曲線，而是兩條曲線。“u”座標的每個可能的源值都將定義曲線上的一個點，或者定義“扭曲”曲線上的一個點，這在密碼學上也很好（它的順序是一個大素數乘以一個非常小的輔因子）。這允許 X25519 是安全的，無需對傳入點執行任何驗證，這再次使程式碼更簡單、更短。同樣，該特徵不是蒙哥馬利曲線所固有的。簡而言之 Weierstraß 形式的經典曲線可以表現出相同的屬性，但 NIST 曲線卻沒有。
- 相反，蒙哥馬利曲線有一個複雜性，那就是它們的階必須是 8 的倍數；因此，它不能是素數。這意味著一個有效的曲線點不一定是我們執行大多數操作的素數階子群上的一個點。X25519 規範通過強制標量為 8 的倍數來解決該問題。當 Curve25519（或其派生 edwards25519）用於其他更複雜的加密協議時，此屬性可能會出現問題，必須適當地迴避（通常由相同的將事物乘以 8 或強制乘數為 8 的倍數的方法）。在某種程度上，這是一種權衡：實現更簡單，但代價是協議中的一些額外複雜性.
**總而言之：**蒙哥馬利階梯使算法更快，更容易實現，特別是如果您的目標是恆定時間程式碼。但是現代標準曲線，即蒙哥馬利曲線，也帶有一些非常好的額外特徵，並且產生更大的加速；這些額外的功能並非保留給蒙哥馬利曲線，但 NIST 曲線不提供它們，因為它們當時還沒有被發明或至少沒有被注意到。
作為歷史記錄：蒙哥馬利曲線首先被發明並用於橢圓曲線分解方法，其中原始速度至關重要，但曲線本身沒有任何實際的密碼相關性。