如果你能猜到挑戰，如何偽造 Schnorr 簽名
Schnorr 簽名的基礎是一個辨識協議：讓 $ G $ 是一個循環組，其中離散對數是“硬”的並選擇 $ g $ 作為生成器 $ G $ . 現在讓 Alice 選擇一個隨機（秘密）指數 $ s $ 並發布 $ v=g^s $ .
為了向 Bob 表明自己的身份，它是這樣的：
- Alice 選擇一個隨機指數 $ r $ 並發送 $ g^r $ （送出 $ r $ )
- Bob 發送隨機指數 $ e $ （挑戰 $ e $ )
- 愛麗絲發送 $ r + se $
- 鮑勃確保 $ g^r = g^{r + se}v^{-e} $
這一切都很好，但是如果作弊證明者可以猜到怎麼辦 $ e $ ? 那麼他是如何愚弄鮑勃的呢？
在其他答案中，如果您知道，您將找到如何模擬證明 $ e $ . 這個答案旨在為其他答案提供一些**“顏色評論”**。這是一個伴侶片。
符號
- 在步驟 1 中，Alice 發送 $ g^r $ . 呼叫這個值 $ a=g^r $ .
- 在步驟 3 中，Alice 發送 $ r+se $ . 呼叫這個值 $ b=r+se $ .
- 在步驟 1-3 中，每一步發送一個值：{ $ a,e,b $ }。我們將這三個值稱為公鑰的副本 $ v $ .
- 在第 4 步中，Bob 使用新符號檢查： $ a=g^bv^{-e} $ .
基本問題
使用這種符號，可能更容易看出如何知道 $ e $ 能夠幫助。隨機生成 $ b $ 然後計算 $ a $ 使得等式成立並且{ $ a,e,b $ } 會接受。
還有一點需要注意
其他答案指出，由於您選擇 $ a $ 直接，你並不真正了解 $ r $ 這樣 $ a=g^r $ （由離散對數問題）。這是將真實證明與模擬證明區分開來的一件事。
需要注意的第二件事非常重要，即要模擬證明，您首先要計算（選擇） $ b $ 然後你計算 $ a $ 使用 $ b $ 和 $ e $ . 在實際執行中，您按順序計算所有內容。
唯一的鍛造方式？
其他答案顯示了一種模擬證明的方法。這是唯一的方法嗎？
例如，是否可以選擇一個 $ a $ 了解價值 $ e $ 然後計算右邊 $ b $ 使{ $ a,e,b $ } 接受（不知道 $ s $ )? 答案是不。
假設你有一個可以做到這一點的黑匣子：它需要 { $ a,e $ } 作為輸入並返回正確的 $ b $ 不知道 $ s $ . 如果存在這樣的框，您可以查詢{ $ a,e_1 $ ) 並得到 $ b_1 $ , 然後查詢 { $ a,e_2 $ } 同 $ a $ 和不同的 $ e $ ，並得到 $ b_2 $ . 但是，可以驗證這足以計算 $ s $ ： 實際上， $ s=\frac{b_1-b_2}{e_1-e_2} $ . 所以有一個矛盾：盒子不知道 $ s $ 根據定義，但它確實“知道” $ s $ （從某種意義上說它可以計算它）。因此，矛盾的是，這樣的盒子不可能存在，偽造品也不可能存在{ $ a,e,b $ } 在哪裡 $ a $ 和 $ e $ 被選中。
只執行真實的成績單
如果我們將以上所有內容放在一起，它基本上就是說如果{ $ a,e,b $ } 接受，它必須是由真正知道的人計算的 $ s $ ，或者它是通過選擇/知道向後計算的 $ b $ 和 $ e $ 在計算之前 $ a $ .
我們可以消除第二種情況嗎？一種方法是成為鮑勃。另一個可能是親自去那裡看看 $ a $ 之前發送 $ e $ : 但是你真的知道愛麗絲不知道嗎 $ e $ ? 你真的能確定嗎？
答案是肯定的。
如果你能確保 $ a $ 之前計算 $ e $ ，那麼我們就完成了。一種簡單的技術（稱為 Fiat-Shamir）是設置 $ e=\mathcal{H}(a) $ ， 在哪裡 $ \mathcal{H} $ 是一個散列函式（技術上是一個隨機預言機）。如果您選擇/知道 $ e $ 首先，你找不到 $ a $ 這將散列到它（通過原像抗性）。