DSA：如果簽名被接受，那麼簽名是正確的
在我的一個課程中，我有以下練習：
證明，在DSA簽名方案中，如果一個DSA簽名被接受，也是正確的。
我將如何證明這一點？在密碼學中，當說簽名正確時，通常指的是什麼？這是否意味著如果驗證者接受簽名，那麼它是用正確的私鑰簽名的？
這不是完全標準的術語，因此您應該檢查講義中的精確定義。但我想不出其他的練習應該是什麼。
你有一個 DSA 簽名過程的定義：給定一些參數 $ (p,q,g) $ , 一個私鑰 $ x $ 和一條消息 $ m $ , 生成一個隨機數 $ k $ 併計算 $ (r,s) $ 由某個公式給出。您還定義了 DSA 驗證過程：給定一些參數 $ (p,q,g) $ , 一個公鑰 $ y $ ， 一個消息 $ m $ 和候選人簽名 $ (r,s) $ ，進行一定的計算並輸出“接受”或“拒絕”。這是一個簽名方案，如果簽名過程的每個輸出都被驗證過程接受，也就是說，如果你取 $ (r,s) $ 通過簽名給出並對其執行驗證過程，輸出為“接受”。
這個練習要求你證明一個雙重屬性，它是實際必要的，但不足以保證安全性：給定參數 $ (p,q,g) $ , 一個密鑰對 $ (x,y) $ 和一條消息 $ m $ ，如果驗證過程為 $ y $ , $ m $ 和簽名候選人 $ (r,s) $ 輸出“接受”，則存在一個隨機數 $ k $ 這樣的簽名過程 $ x $ 和 $ m $ 產生輸出 $ (r,s) $ .
計算本身很簡單：取 $ k = s^{-1} (m + x,r) $ , 反轉用於計算的公式 $ s $ 從 $ k $ 和 $ r $ 在簽名過程中。驗證過程基本上檢查 $ g^k = r $ ，所以如果簽名被接受，這意味著它是簽名過程的輸出 $ k $ .
這個屬性實際上是安全所必需的，因為如果對手可以有效地找到 $ (r,s) $ 這不是簽名過程的輸出，這意味著他們可以製作無效簽名。我不確定僅僅存在一個沒有人能有效找到的有效簽名是否會取消簽名方案的資格。