Signature
通過選擇消息攻擊破壞 Rabin 簽名系統的無雜湊變體
我聽說我們可以使用選擇消息攻擊來破壞 Rabin 簽名系統。留言 $ M $ 這是一個二次餘數模 $ N $ ，簽名為 $ x $ 這樣 $ x^2 \equiv M \pmod N $ . 我找不到要求籤名以欺騙我的消息的消息 $ M $ .
有什麼建議麼？
以下是攻擊的工作原理：
- 選擇一個隨機值 $ y $
- 計算 $ a = y^2 \bmod n $
- 要求籤名 $ a $ ， 那是 $ x $ 和 $ x^2 = a $
- 如果 $ x \ne y $ 和 $ x + y \ne n $ ， 然後 $ \gcd(n, x+y) $ 是一個適當的因素 $ n $
最後一步有可能成功 $ \approx 0.5 $ . 如果您選擇一個，您可以將其設為機率 1 $ y $ 帶有雅可比符號 -1。
你聽錯了。Rabin 在他1979 年的論文中提出的簽名包括消息的（隨機）散列，在合理選擇散列函式的情況下完全防止攻擊。
沒有消息散列的方案從未被提出，應該被稱為“過度簡化的類 Rabin 簽名”以避免混淆。我推薦 Bernstein 的論文“ RSA signatures and Rabin–Williams signatures: the state of the art ”，它直接記錄了歷史。這不是一個小警告：如果我們要忽略在提出該方案的論文或標準中明確說明的使用方案的條件，那麼我們也可以通過相同的論點說 RSA、ECDSA、EdDSA 和在選擇的消息攻擊下（在許多情況下，在較弱的攻擊模型下），所有其他常用的簽名算法都會被破壞。