標量 EC 乘法的 Strauss-Shamir 技巧
我正在研究 ECDSA，幾乎所有比較詳細的文章都談到了在驗證步驟中使用 Strauss-Shamir 技巧。
然後我搜尋，找到了這個算法的解釋（更像是一個陳述），然後是另一個pdf（第 7 頁），它更詳細地解釋了它。但他們都沒有解釋為什麼它會起作用。
我想逐步進行某種展示或範例嗎？從Shamir-Straus 的假人到正式展示或對我的任何作品的引用，數學都不應該成為問題。
我將描述適用於ECDSA 簽名驗證上下文的標準 Shamir 技巧。刪除一些索引，其中計算成本高的部分是計算 $$ u\cdot G+v\cdot Q $$ 在哪裡 $ u $ 和 $ v $ 是（我們假設，嚴格為正）整數， $ G $ 和 $ Q $ 是橢圓曲線點，並且 $ + $ 是點加法（為簡化起見，我認為是一個黑匣子，其執行支配了計算成本）。回想一下，根據定義，$$ u\cdot G=\underbrace{G+G+\ldots+G+G}_{u\text{ terms}} $$
好注意 $ \mathbin|u\mathbin| $ 整數位數 $ u $ ， 那是 $ \left\lfloor\log_2(u)+1\right\rfloor $ ; 同樣的 $ \mathbin|v\mathbin| $ .
一種常見的計算方式 $ u\cdot G $ 是
放 $ R:=G $
為位 $ b $ 從二進製表示複製 $ u $ , 從索引開始 $ \mathbin|u\mathbin|-1 $ （最左邊右邊的第一位 $ 1 $ 位）下降到 $ 0 $ （最右邊的位）
- 放 $ R:=R+R $
- 如果 $ b=1 $ ， 放 $ R:=R+G $
計算的基本方法 $ u\cdot G+v\cdot Q $ 將是計算 $ u\cdot G $ ， 然後 $ v\cdot Q $ 用同樣的方法，然後將兩個結果相加。Shamir 的技巧改進了這一點：
- 放 $ H:=G+Q $
- 如果 $ \mathbin|u\mathbin|>\mathbin|v\mathbin| $ ， 放 $ R:=G $ ;
- 否則如果 $ \mathbin|u\mathbin|<\mathbin|v\mathbin| $ ， 放 $ R:=Q $ ;
- 否則（即如果 $ \mathbin|u\mathbin|=\mathbin|v\mathbin| $ ）， 放 $ R:=H $ ;
- 為位 $ b $ （分別。 $ c $ ) 從二進製表示複製 $ u $ （分別。 $ v $ )，表示為 $ u $ 或者 $ v $ 必要時用零填充，在索引處 $ \max(\mathbin|u\mathbin|,\mathbin|v\mathbin|)-1 $ 向下 $ 0 $
- 放 $ R:=R+R $
- 如果 $ b=1 $ 和 $ c=0 $ ， 放 $ R:=R+G $
- （否則）如果 $ b=0 $ 和 $ c=1 $ ， 放 $ R:=R+Q $
- （否則）如果 $ b=1 $ 和 $ c=1 $ ， 放 $ R:=R+H $
這個陳述幾乎等同於這個答案中以 Strauss-Shamir 技巧（當我知道這個技巧為 Shamir 的技巧時）給出的那個。我給出的變體避免了需要知道組中立，但需要 $ \max(u,v)>0 $ .
標準點乘法和 Shamir 的技巧的正確性可以通過歸納來正式證明。
對於大隨機 $ u $ 和 $ v $ 的 $ k $ 位，計算的樸素算法 $ u\cdot G+v\cdot Q $ 表現平均 $ \approx3k $ 點加法，沙米爾的把戲減少到 $ \approx1.75k $ ，比如減少 42%（成本效益較低，很大程度上是因為點數翻倍 $ R:=R+R $ 是最快的一種點加法，也是最減少的一種）。可能還有進一步的改進，例如將位分組為兩個或稍多一些，可能在使用“滑動視窗”時 $ b=0=c $ .
請注意，在簽名驗證的上下文中， $ u $ , $ v $ , $ G $ 和 $ Q $ 所有這些都是公共的，因此側通道（時序、功耗、發射、記憶體……）不是安全問題，因為它們在簽名生成中。
我不知道問題的其他參考的 Strauss-Shamir 技巧，但隱約懷疑它通過有時執行減法而不是加法來進一步改進，和/或與點加法的加速技術更兼容。