Shamir’s Trick 能否破解 ECDSA 的加密強度？
最近無意中在論壇上討論
沙米爾的訣竅是乾什麼用的？
有沒有這樣的例子？
不，Shamir 的伎倆並沒有破壞 ECDSA。驗證 ECDSA 簽名涉及評估標量乘法的總和 $ [h s^{-1}]G + [r s^{-1}]P $ . 您可以計算標量乘法 $ [h s^{-1}]G $ 和 $ [r s^{-1}]P $ 分別然後將結果相加，但 Shamir 的技巧將其作為組合計算更有效。
評估產品總和的這個技巧 $ [\alpha]P + [\beta]Q $ 是通過二進制展開 $ \alpha = \sum_i \alpha_i 2^i $ 和 $ \beta = \sum_i \beta_i 2^i $ 從 msb 到 lsb，如果位都為 0，則不加總和， $ P $ 要是 $ \alpha_i = 1 $ , $ Q $ 要是 $ \beta_i = 1 $ ， 或者 $ P + Q $ 如果兩個位都是 1；然後將總和加倍並繼續下一位。
注意：如果選擇要添加的點或算術不是在恆定時間內完成，則此過程可能會洩漏標量 $ \alpha $ 和 $ \beta $ 通過定時側通道。在驗證簽名時，這通常不是問題（除非由於某種原因簽名必須保密），但其他應用程序可能涉及兩個標量乘法之和，其標量是保密的。
沙米爾的把戲：給定 $ N, x, z, e, F $ 英石 $ x^e = z^F \mod N $ 和 $ e, F $ 是相對素數，你可以有效地找到 $ z^{1/e}\mod N $ . 訣竅是計算整數 $ a,b $ 英石 $ a.e + b.F = 1 $ .
RSA 說：給定 $ N, y, e $ , 很難計算 $ y^{1/e}\mod N $ .
使用 shamir 的技巧，您可以證明以下內容： $ N, y, F, e $ 英石 $ F,e $ 是相對素數，那麼很難計算 $ y^{F/e}\mod N $ .