Elliptic-Curves
ECDSA 簽名生成和驗證延遲
我正在對 P256 ecdsa 簽名生成和驗證延遲進行一些測量，我預計簽名驗證會比簽名生成更快，但事實並非如此。是什麼讓簽名生成更快？簽名驗證中計算量最大的操作是什麼？
我期待簽名驗證會比簽名生成更快
因為RSA中的簽名驗證更快？好吧，正如你所見，RSA != ECDSA; 簽名和驗證所涉及的操作完全不同。
是什麼讓簽名生成更快？
因為簽名生成只涉及一個點乘法（加上一個模逆；相當便宜，但不是微不足道的成本），而簽名驗證涉及兩個點乘法。
當然，如果您深入了解教科書的定義，那麼雙方都有可用的優化：
在簽名方面：
- 點乘法 $ k \times G $ （我將使用維基百科頁面上的符號）使用固定（由橢圓曲線定義定義）點；有許多方法可以通過基於 $ G $ .
- 此外，簽名操作所涉及的昂貴操作不依賴於被簽名的消息。因此，如果您的實現有一些空閒時間，它可能會預先生成 $ k $ 和 $ r $ 價值觀；當它收到消息時，它可以使用這些值以非常低的延遲對消息進行簽名。
- 另外，警告一句：如果您正在考慮使用相同的 $ k, r $ 簽署多條消息的值，不要去那裡 - 這會洩露你的私人簽名密鑰。你真的需要新鮮的 $ k $ 為每個簽名消息隨機選擇的值。
在驗證方面，昂貴的操作是計算 $ u_1 \times G + u_2 \times Q_A $
- 可以使用預先計算的表來計算 $ u_1 \times G $ 迅速地; 這意味著計算時間 $ u_2 \times Q_A $ 是大部分時間（如果您知道您將使用特定的公鑰進行驗證 $ Q_A $ 很多時候，您可以基於此預先計算表 - 我還沒有聽說有人會這樣做，因為您需要驗證來自該公鑰的數千個簽名才能使其值得）。
- 或者，還有 Shamir 的技巧，這是一種計算方法來計算 $ a \times P + b \times Q $ 比計算單點乘法花費的時間不多。但是，您會從預先計算的表中失去速度。
但是，這些想法都沒有產生與使用預計算表進行簽名一樣快的驗證方法。
使用那裡的符號，ECDSA 簽名生成需要一個橢圓曲線點乘法， $ k\times G $ . 樸素的簽名驗證使用兩個，計算 $ u_1\times G $ 和 $ u_2\times Q_A $ 在添加它們之前。點乘法通常是迄今為止簽名生成/驗證中最慢的操作，除了散列（這對於簽名生成和驗證來說很常見）。這可以解釋觀察到的時間差異。
然而，情況並非總是如此，還有其他原因可以逆轉或至少減輕這種情況：
- 各種技術，如Shamir 技巧或 wNAF 交錯允許計算 $ u_1\times G+u_2\times Q_A $ 必須比兩點乘法少。在某些 CPU 上，可以進行並行化。
- 隨機生成 $ k $ 僅對生成是必需的，並且在某些平台上可能會很慢。
- 在生成而不是驗證時會操縱秘密數據，這可以激發減緩事情的對策（並且可能需要更多隨機性）。特別是，一種常見的安全做法是在顯示生成的簽名之前對其進行驗證，這會反過來。