Implementation
在 ECDSA 中，有多少個欄位操作用於簽名驗證？
我想知道ECDSA簽名驗證的計算成本，就基欄位中的乘法而言；並且，順便說一句，就（更便宜的）添加而言。為了使事情具體化，假設 ECDSA 在一個領域 $ GF(p) $ 根據FIPS 186-3（指ANSI X9.62:2005 (webstore)），使用附錄 D.1.2 中的參數。
我首先對最直接的遵守標準的方法感興趣，而且成本在正確的範圍內；然後在最有價值的改進中。我已經確定（按名稱，但不是數量效應，尤其是第一個）：
- 投影座標系，據說允許通過比標準反演算法更少的操作來替換基場中的反演（如用於橢圓曲線組中的直線加法），例如 $ x\mapsto x^{p-2}\bmod p $ （或更有效的擴展歐幾里得，但這與我的“基域乘法”評估標準不太匹配）；
- 沙米爾的詭計，在哪裡 $ aP+bQ $ 通過添加任一計算 $ P $ , $ Q $ 或者 $ P+Q $ （在橢圓曲線群上）掃描整數被乘數的位時 $ a $ 和 $ b $ ;
- 掃描被乘數位時的滑動視窗技術。
我對引入公鑰的證書的驗證成本或散列成本不感興趣；並且僅通過預先計算或僅適用於 $ GF(2^n) $ ，或使用特殊形式 $ p $ 參數（允許加速模組化減少 $ \bmod p $ ，但保持基本欄位中的操作數不變）。
通常，wNAF 的交錯比 Shamir 的同時點乘技巧更快。使用視窗大小為 5（固定）和 4（隨機）的交錯，操作總數大致為（取自 Hankerson 等人的 ECC 指南）
$ (0.37t + 3)A + (t + 1)D $
其中 t 是標量的位長（應與標準曲線的欄位大小的位長相同），A 是混合點加法（投影 + 仿射），D 是點加倍。
對於標準素數曲線 $ a=-3 $ ，使用雅可比座標，我們有（來自 EFD）：
$ A = 7M + 4S $ ,
$ D = 3M + 5S $ ,
在哪裡 $ M $ 是域乘法和 $ S $ 是一個域平方。所以，
$ M = (5.59t + 24) $ ,
$ S = (6.48t + 17) $ .
對於 128 位級別的安全性，如果我做對了， $ t=256, M = 1455, S = 1675 $ .