Implementation
DSA/ECDSA/Schnorr 乘法的查找表
有共同點
$$ EC $$DSA 和 Schnorr 等相關簽名方案是簽名中最昂貴的部分是計算 $ r = g^k $ 在組中進行一些簽名 $ k $ 長度 $ b $ 位。但這總是需要同一台發電機供電。 因為它總是相同的基數，我們可以預先計算 $ {g^1, g^2, g^4, … g^{2^{b-1}}} $ 成一張桌子。然後計算 $ g^k $ 乘以表中對應的條目 $ 1 $ 位 $ k $ . （總是做乘法，但丟棄結果，因為 $ 0 $ 位來停止計時和功率攻擊。）
這似乎可以節省時間，因為不是做 $ b $ 正方形和 $ b $ 倍增，你只會做 $ b $ 倍增。
這對於簽名最有用。為了驗證，您需要第二個預先計算好的公鑰平方表 $ y $ . 但是，如果密鑰長度不是問題，這可以儲存為公鑰的一部分。
現有的實現似乎沒有做這種優化。為什麼不？（或者也許我錯了，他們會……？）
其實，做 $ k-1 $ 乘法並不比使用更複雜的冪算法（例如，基 $ 2^w $ , 對於適當選擇的 $ w $ ) - 這些算法不需要預先計算的表。
另一方面，有更複雜的預計算算法，它們大大減少了乘法的數量（有時也縮小了表的大小）。
現在，在處理有限域組時，我還沒有看到這種優化（ $ \mathbb{Z}_p^* $ ); 根據我的經驗，一般電源程序（或可能針對以下情況進行優化） $ g=2 $ ) 似乎是常態。
但是，在處理橢圓曲線組時很常見。
至於我為什麼會這樣的猜測：
- 這 $ \mathbb{Z}_p^* $ 慣例往往更老；也許沒有人認為更新它們以使用預先計算的表是值得的。
- 表為 $ \mathbb{Z}_p^* $ 會更大（因為每個預先計算的元素都會更大）。
- 使用 ECC，您可以有效地計算逆——我們可以利用這一點在一定程度上改進我們的預計算算法，使預計算優勢更大一些。