ECDSA 簽名是強 EUF-CMA 嗎？
我在這裡讀到ECDSA 簽名是 EUF-CMA 但不是 SUF-CMA，也稱為 sEUF-CMA（在自適應選擇的消息攻擊下具有強大的存在不可偽造性；參見那裡的術語）。
具體來說，斷言是給定消息的 ECDSA 簽名，可以將其轉換為通過同一消息驗證的不同簽名。
有沒有這樣的問題，它到底在哪裡？
- 數學定義
- 某些版本的ANS X9.62（付費專區）、SEC-1或FIPS 186中籤名的標準化定義
- 一些實現
從 SEC1 v2.0（第 4.1 節，第 43-47 頁）開始，公鑰是一個點 $ Q \in E $ ，以及消息上的簽名 $ m $ 是一對整數 $ (r, s) $ 滿足簽名方程（由幾個步驟濃縮而成）：
$$ \begin{equation*} r \stackrel?= f\bigl(x([H(m) s^{-1}]G + [r s^{-1}]Q)\bigr), \end{equation*} $$
在哪裡 $ f\colon \mathbb Z/p\mathbb Z \to \mathbb Z/n\mathbb Z $ 將表示座標域元素的最小非負整數投影到標量環上. 這裡 $ G $ 是標準基點，並且 $ H $ 是將消息映射到標量的雜湊函式。
這個方程在變換下是不變的 $ \phi\colon (r, s) \mapsto (r, -s) $ 因為 $ (-s)^{-1} = -(s^{-1}) $ , $ [-\alpha]P = -[\alpha]P $ , $ (-A) + (-B) = -(A + B) $ ， 和 $ x(P) = x(-P) $ . 在變換下也是明顯不變的 $ \psi\colon (r, s) \mapsto (r, s + n) $ 因為 $ s $ 僅用作標量。
規定了三個附加要求：
- $ r $ 和 $ s $ 必須在區間 $ [1, n - 1] $ ， 在哪裡 $ n $ 是組的順序。
- 如果 $ H $ 返回無效，則簽名驗證必須失敗。
- $ [H(m) s^{-1}]G + [r s^{-1}]Q $ 不能是無窮遠點。
與強不可偽造性相關的唯一要求是（1），因為它排除了轉換 $ \phi $ 和 $ \psi $ 分別。但不排除，例如， $ \psi \mathbin\circ \phi $ ， 相當於 $ (r, s) \mapsto \bigl(r, (-s) \bmod n\bigr) $ .
可以想像，簽名方案可能要求 $ s $ 像在 ANSI X9.62 點壓縮中一樣選擇“均勻”，或者選擇在間隔的下半部分 $ [1, n - 1] $ . 但是這些要求不是由驗證者強加的，因此 ECDSA 不能提供強大的不可偽造性。
還有其他明顯的方式可能導致實現無法提供 sEUF-CMA：
- 實現可能無法檢查 $ r $ 和 $ s $ . （但是，我不知道有什麼。）
- 該實現可以允許對單個整數進行許多不同的編碼。例如，它可以允許使用某些 ASN.1 格式的 BER 或 DER 編碼——因為標準沒有指定整數的字節編碼；簽名方案實際上是根據整數定義的，這是 EdDSA 避免的一個錯誤。
這是比特幣中報告的交易延展性的第一個來源，促使實現僅接受簽名的唯一 DER 編碼並拒絕其他編碼，直到一年半後有人注意到否定向量。（為渴望一趟兔子洞之旅的讀者準備的練習：記錄 MtGox 中交易延展性的傳奇故事，並弄清楚這些天的破產程序是怎麼回事。）